ALIGNMENT-FREE PHYLOGENETIC RECONSTRUCTION: SAMPLE COMPLEXITY VIA A BRANCHING PROCESS ANALYSIS
ALIGNMENT-FREE PHYLOGENETIC RECONSTRUCTION: SAMPLE COMPLEXITY VIA A BRANCHING PROCESS ANALYSIS
复制标题
DOI：
10.1214/12-aap852
复制
发表时间：
2013-04-01
影响因子：
1.8
通讯作者：
Roch, Sebastien
中科院分区：
文献类型：
--
作者：
Daskalakis, Constantinos;Roch, Sebastien
我们提出了一种高效的系统发育重建算法，允许插入和删除，该算法可以证明达到了在分类群数量上以多项式增长的序列长度要求(或样本复杂性)。我们的算法是基于距离的，也就是说，它依赖于成对的序列比较。更重要的是，我们的方法在很大程度上绕过了多序列比对这一难题。
We present an efficient phylogenetic reconstruction algorithm allowing insertions and deletions which provably achieves a sequence-length requirement (or sample complexity) growing polynomially in the number of taxa. Our algorithm is distance-based, that is, it relies on pairwise sequence comparisons. More importantly, our approach largely bypasses the difficult problem of multiple sequence alignment.