Algorithms to reconstruct past indels: The deletion-only parsimony problem.

ABSTRACT: Ancestral sequence reconstruction is an important task in bioinformatics, with applications ranging from protein engineering to the study of genome evolution. When sequences can only undergo substitutions, optimal reconstructions can be efficiently computed using well-known algorithms. However, accounting for indels in ancestral reconstructions is much harder. First, for biologically-relevant problem formulations, no polynomial-time exact algorithms are available. Second, multiple reconstructions are often equally parsimonious or likely, making it crucial to correctly display uncertainty in the results. Here, we consider a parsimony approach where only deletions are allowed, while addressing the aforementioned limitations. First, we describe an exact algorithm to obtain all the optimal sol

SUBMITTER: Moutet J 

PROVIDER: S-EPMC12331173 | biostudies-literature | 2025 Jul

REPOSITORIES: biostudies-literature