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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - דצמ׳ 2012

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2613???
  • ???subjectarea.asjc.2600.2611???
  • ???subjectarea.asjc.2600.2604???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Global alignment of molecular sequences via ancestral state reconstruction'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי