Title :
A fast algorithm on average for all-against-all sequence matching
Author :
Baeza-Yates, Ricardo A. ; Gonnet, Gaston H.
Author_Institution :
Dept. de Ciencias de la Comput., Chile Univ., Santiago, Chile
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 average time
Keywords :
biology computing; computational complexity; database theory; dynamic programming; molecular biophysics; string matching; DNA; all-against-all sequence matching; approximate string matching problem; average case analysis; dynamic programming alignment algorithm; fast algorithm; genetic sequences; peptide sequence database; running time; suffix array; Algorithm design and analysis; Computational modeling; DNA; Databases; Dynamic programming; Genetics; Heuristic algorithms; Impedance matching; Peptides; Sequences;
Conference_Titel :
String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware
Conference_Location :
Cancun
Print_ISBN :
0-7695-0268-7
DOI :
10.1109/SPIRE.1999.796573
