Zobrazeno 1 - 10
of 100
pro vyhledávání: '"Tiskin, Alexander"'
Autor:
Tiskin, Alexander
Given two equally long, uniformly random binary strings, the expected length of their longest common subsequence (LCS) is asymptotically proportional to the strings' length. Finding the proportionality coefficient $\gamma$, i.e. the limit of the norm
Externí odkaz:
http://arxiv.org/abs/2212.01582
A deterministic BSP algorithm for constructing the suffix array of a given string is presented, based on a technique which we call accelerated sampling. It runs in optimal O(n/p) local computation and communication, and requires a near optimal O(log
Externí odkaz:
http://arxiv.org/abs/1302.5851
Autor:
Krusche, Peter, Tiskin, Alexander
Dot plots are a standard method for local comparison of biological sequences. In a dot plot, a substring to substring distance is computed for all pairs of fixed-size windows in the input strings. Commonly, the Hamming distance is used since it can b
Externí odkaz:
http://arxiv.org/abs/0909.2000
Autor:
Krusche, Peter, Tiskin, Alexander
Computing string or sequence alignments is a classical method of comparing strings and has applications in many areas of computing, such as signal processing and bioinformatics. Semi-local string alignment is a recent generalisation of this method, i
Externí odkaz:
http://arxiv.org/abs/0903.3579
Autor:
Deineko, Vladimir, Tiskin, Alexander
The Metric Traveling Salesman Problem (TSP) is a classical NP-hard optimization problem. The double-tree shortcutting method for Metric TSP yields an exponentially-sized space of TSP tours, each of which approximates the optimal solution within at mo
Externí odkaz:
http://arxiv.org/abs/0711.2399
Autor:
Deineko, Vladimir, Tiskin, Alexander
The Metric Traveling Salesman Problem (TSP) is a classical NP-hard optimization problem. The double-tree shortcutting method for Metric TSP yields an exponentially-sized space of TSP tours, each of which approximates the optimal solution within at mo
Externí odkaz:
http://arxiv.org/abs/0710.0318
Autor:
Tiskin, Alexander
A classical measure of string comparison is given by the longest common subsequence (LCS) problem on a pair of strings. We consider its generalisation, called the semi-local LCS problem, which arises naturally in many string-related problems. The sem
Externí odkaz:
http://arxiv.org/abs/0707.3619
Autor:
Tiskin, Alexander
Assembling a gene from candidate exons is an important problem in computational biology. Among the most successful approaches to this problem is \emph{spliced alignment}, proposed by Gelfand et al., which scores different candidate exon chains within
Externí odkaz:
http://arxiv.org/abs/0707.3409
Autor:
Tiskin, Alexander
Computation on compressed strings is one of the key approaches to processing massive data sets. We consider local subsequence recognition problems on strings compressed by straight-line programs (SLP), which is closely related to Lempel--Ziv compress
Externí odkaz:
http://arxiv.org/abs/0707.3407
Publikováno v:
In Discrete Optimization November 2014 14:147-159
