| Citation |
M. Ghodsi, M. Pop
Inexact local alignment search over suffix arrays
Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine, :83-87 (2009) |
| Abstract |
We describe an algorithm for finding approximate
seeds for DNA homology searches. In contrast to previous
algorithms that use exact or spaced seeds, our approximate seeds
may contain insertions and deletions. We present a generalized
heuristic for finding such seeds efficiently and prove that the
heuristic does not affect sensitivity. We show how to adapt this
algorithm to work over the memory efficient suffix array with
provably minimal overhead in running time.
We demonstrate the effectiveness of our algorithm on two
tasks: whole genome alignment of bacteria and alignment of the
DNA sequences of 177 genes that are orthologous in human and
mouse. We show our algorithm achieves better sensitivity and
uses less memory than other commonly used local alignment
tools. |
| PDF |
http://www.cbcb.umd.edu/publications/files/PID979503.pdf.pdf
|
| Download citation |
|
| GS |
Google Scholar
|
| Notes |
|
