Format

Send to

Choose Destination

Inexact Local Alignment Search over Suffix Arrays.

Author information

1
Department of Computer Science, University of Maryland, College Park, MD 20742, USA.

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.

Supplemental Content

Full text links

Icon for PubMed Central
Loading ...
Support Center