Global alignment of molecular sequences via ancestral state reconstruction |
| |
Authors: | Alexandr Andoni Constantinos Daskalakis Avinatan Hassidim Sebastien Roch |
| |
Institution: | 1. Microsoft Research Silicon Valley, United States;2. EECS, MIT, United States;3. Bar Ilan University, Israel;4. Google Israel, Israel;5. Department of Mathematics, UW-Madison, United States |
| |
Abstract: | 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. |
| |
Keywords: | Markov models on trees Branching processes Phylogenetic inference |
本文献已被 ScienceDirect 等数据库收录! |
|