ALIGNMENT-FREE PHYLOGENETIC RECONSTRUCTION: SAMPLE COMPLEXITY VIA A BRANCHING PROCESS ANALYSIS

• 成果类型: Article
• 署名作者: Daskalakis, Constantinos; Roch, Sebastien
• 署名单位: Massachusetts Institute of Technology (MIT); University of California System; University of California Los Angeles; University of California System; University of California Los Angeles
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/12-AAP852
• 发表日期: 2013
• 页码: 693-721
• 关键词: multiple sequence alignment; evolutionary trees; logs suffice; MODEL; RECOVERY; bounds; build

摘要

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.