Global alignment of molecular sequences via ancestral state reconstruction

Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sebastien Roch

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

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.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)3852-3874
عدد الصفحات23
دوريةStochastic Processes and their Applications
مستوى الصوت122
رقم الإصدار12
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - ديسمبر 2012

All Science Journal Classification (ASJC) codes

  • !!Statistics and Probability
  • !!Modeling and Simulation
  • !!Applied Mathematics

بصمة

أدرس بدقة موضوعات البحث “Global alignment of molecular sequences via ancestral state reconstruction'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا