A FAST ALGORITHM ON AVERAGE FOR ALL-AGAINST-ALL SEQUENCE MATCHING
Author
Baeza Yates, Ricardo AlbertoGonnet, Gaston H.
Abstract
We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear a...
Ver más
We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.We present an algorithm which attempts to align pairs of
subsequences from a database of genetic sequences. The algorithm
simulates the classical dynamic programming alignment algorithm over a
suffix array of the database. We provide a detailed average case
analysis which shows that the running time of the algorithm is
subquadratic with respect to the database size. A similar algorithm
solves the approximate string matching problem in sublinear average time.
Ver menos
Book's title
IEEE COMPUTER SOCIETY DL
Publication date of the book
1999Start page
16
End page
23
Country
ESTADOS UNIDOS DE AMERICA