Inexact Local Alignment Search over Suffix Arrays
| Title | Inexact Local Alignment Search over Suffix Arrays |
| Publication Type | Conference Papers |
| Year of Publication | 2009 |
| Authors | Ghodsi M, Pop M |
| Conference Name | IEEE International Conference on Bioinformatics and Biomedicine, 2009. BIBM '09 |
| Date Published | 2009/11/01/4 |
| Publisher | IEEE |
| ISBN Number | 978-0-7695-3885-3 |
| Keywords | bacteria, Bioinformatics, biology computing, Computational Biology, Costs, DNA, DNA homology searches, DNA sequences, Educational institutions, generalized heuristic, genes, Genetics, genome alignment, Genomics, human, inexact local alignment search, inexact seeds, local alignment, local alignment tools, memory efficient suffix array, microorganisms, molecular biophysics, mouse, Organisms, Sensitivity and Specificity, sequences, suffix array, USA Councils |
| 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. |
| DOI | 10.1109/BIBM.2009.25 |