Chaining algorithms for multiple genome comparison
Chaining algorithms for multiple genome comparison
复制标题
DOI：
10.1016/j.jda.2004.08.011
复制
发表时间：
2005-06-01
期刊：
影响因子：
--
通讯作者：
Ohlebusch, Enno
中科院分区：
文献类型：
--
作者：
Abouelhoda, Mohamed Ibrahim;Ohlebusch, Enno
给定来自 k > 2 个基因组的 n 个片段，Myers 和 Miller 展示了如何在 O(n log(k) n) 时间和 O(n log(k-1) n) 空间中找到共线非重叠片段的最佳全局链。对于 L1 度量中的间隙成本，我们将其算法的时间复杂度降低了 log(2) n \ log log n 因子，将空间复杂度降低了 log n 因子。对于对和间隙成本，我们的算法将其算法的时间复杂度提高了一个因子 log n / log log n。我们算法的一个变体找到共线非重叠片段的所有重要局部链。这些链接算法可用于比较基因组学中的各种问题：完整基因组的全局比对的计算、相似区域的识别（保守同线性的候选区域）、基因组重排的检测和外显子预测。 (C) 2004 Elsevier B.V. 保留所有权利。
Given n fragments from k > 2 genomes, Myers and Miller showed how to find an optimal global chain of colinear non-overlapping fragments in O(n log(k) n) time and O(n log(k-1) n) space. For gap costs in the L1-metric, we reduce the time complexity of their algorithm by a factor log(2) n \ log log n and the space complexity by a factor log n. For the sum-of-pairs gap cost, our algorithm improves the time complexity of their algorithm by a factor log n / log log n. A variant of our algorithm finds all significant local chains of colinear non-overlapping fragments. These chaining algorithms can be used in a variety of problems in comparative genomics: the computation of global alignments of complete genomes, the identification of regions of similarity (candidate regions of conserved synteny), the detection of genome rearrangements, and exon prediction. (C) 2004 Elsevier B. V. All rights reserved.