Using multiple alignments to improve seeded local alignment algorithms.
Multiple alignments among genomes are becoming increasingly prevalent. This trend motivates the development of tools for efficient homology search between a query sequence and a database of multiple alignments. In this paper, we present an algorithm that uses the information implicit in a multiple alignment to dynamically build an index that is weighted most heavily towards the promising regions of the multiple alignment. We have implemented Typhon, a local alignment tool that incorporates our indexing algorithm, which our test results show to be more sensitive than algorithms that index only a sequence. This suggests that when applied on a whole-genome scale, Typhon should provide improved homology searches in time comparable to existing algorithms.
Flannick
Jason
J
Department of Computer Science, Stanford University, Stanford, CA 94304, USA. flannick@cs.stanford.edu
Batzoglou
Serafim
S
D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D030561:Databases, Nucleic Acid; D023281:Genomics / Q000379:methods*; D006801:Humans; D016415:Sequence Alignment / Q000379:methods*; D012984:Software