#### 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**

1999#####
**Start page**

16

#####
**End page**

23

#####
**Country**

ESTADOS UNIDOS DE AMERICA