Global Alignment of Molecular Sequences via Ancestral State Reconstruction
Global Alignment of Molecular Sequences via Ancestral State Reconstruction
复制标题
DOI：
10.1016/j.spa.2012.08.004
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
Alexandr Andoni;C. Daskalakis;Avinatan Hassidim;S. Roch
中科院分区：
文献类型：
--
作者：
Alexandr Andoni;C. Daskalakis;Avinatan Hassidim;S. Roch
我们认为树（TRPT）上的痕迹重建问题：一个二进制序列是通过一个树的通道，我们允许替换，删除和插入广播，我们试图重建原始序列从收到的序列在叶子。TRPT的动机是计算生物学中的多序列比对问题。我们给出了一个简单的递归过程，在低突变率下提供强有力的重建保证。据我们所知，这是第一个严格的跟踪重建结果的树中存在的indels。
We consider the trace reconstruction problem on a tree (TRPT): a binary sequence is broadcast through a tree channel where we allow substitutions, deletions, and insertions; we seek to reconstruct the original sequence from the sequences received at the leaves. The TRPT is motivated by the multiple sequence alignment problem in computational biology. We give a simple recursive procedure giving strong reconstruction guarantees at low mutation rates. To our knowledge, this is the first rigorous trace reconstruction result on a tree in the presence of indels.