Inexact Local Alignment Search over Suffix Arrays.
Inexact Local Alignment Search over Suffix Arrays.
复制标题
DOI：
10.1109/bibm.2009.25
复制
发表时间：
2009-11-01
期刊：
影响因子：
--
通讯作者：
Pop M
中科院分区：
文献类型：
--
作者：
Ghodsi M;Pop M
我们描述了一种算法，寻找近似种子DNA同源性搜索。与以前使用精确或间隔种子的算法相比，我们的近似种子可能包含插入和删除。我们提出了一个广义的启发式有效地找到这样的种子，并证明了启发式不影响灵敏度。我们将展示如何适应此算法的工作在内存有效的后缀数组，可证明在运行时的开销最小。我们证明了我们的算法在两个任务上的有效性：细菌的全基因组比对和177个基因的DNA序列的比对，这些基因在人类和小鼠中是同源的。我们表明，我们的算法实现了更好的灵敏度和使用更少的内存比其他常用的本地对齐工具。
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.