Using multiple alignments to improve seeded local alignment algorithms |
| |
Authors: | Flannick Jason Batzoglou Serafim |
| |
Institution: | Department of Computer Science, Stanford University, Stanford, CA 94304, USA. flannick@cs.stanford.edu |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|