Algorithms to reconstruct past indels: The deletion-only parsimony problem.
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, acco...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2025-07-01
|
| Series: | PLoS Computational Biology |
| Online Access: | https://doi.org/10.1371/journal.pcbi.1012585 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849228210569478144 |
|---|---|
| author | Jordan Moutet Eric Rivals Fabio Pardi |
| author_facet | Jordan Moutet Eric Rivals Fabio Pardi |
| author_sort | Jordan Moutet |
| collection | DOAJ |
| description | 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 solutions. The algorithm runs in polynomial time if only one solution is sought. Second, we show that all possible optimal reconstructions for a fixed node can be represented using a graph computable in polynomial time. While previous studies have proposed graph-based representations of ancestral reconstructions, this result is the first to offer a solid mathematical justification for this approach. Finally we provide arguments for the relevance of the deletion-only case for the general case. |
| format | Article |
| id | doaj-art-30ce373fe74442f6b47d9f92d2b35a33 |
| institution | Kabale University |
| issn | 1553-734X 1553-7358 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS Computational Biology |
| spelling | doaj-art-30ce373fe74442f6b47d9f92d2b35a332025-08-23T05:31:12ZengPublic Library of Science (PLoS)PLoS Computational Biology1553-734X1553-73582025-07-01217e101258510.1371/journal.pcbi.1012585Algorithms to reconstruct past indels: The deletion-only parsimony problem.Jordan MoutetEric RivalsFabio PardiAncestral 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 solutions. The algorithm runs in polynomial time if only one solution is sought. Second, we show that all possible optimal reconstructions for a fixed node can be represented using a graph computable in polynomial time. While previous studies have proposed graph-based representations of ancestral reconstructions, this result is the first to offer a solid mathematical justification for this approach. Finally we provide arguments for the relevance of the deletion-only case for the general case.https://doi.org/10.1371/journal.pcbi.1012585 |
| spellingShingle | Jordan Moutet Eric Rivals Fabio Pardi Algorithms to reconstruct past indels: The deletion-only parsimony problem. PLoS Computational Biology |
| title | Algorithms to reconstruct past indels: The deletion-only parsimony problem. |
| title_full | Algorithms to reconstruct past indels: The deletion-only parsimony problem. |
| title_fullStr | Algorithms to reconstruct past indels: The deletion-only parsimony problem. |
| title_full_unstemmed | Algorithms to reconstruct past indels: The deletion-only parsimony problem. |
| title_short | Algorithms to reconstruct past indels: The deletion-only parsimony problem. |
| title_sort | algorithms to reconstruct past indels the deletion only parsimony problem |
| url | https://doi.org/10.1371/journal.pcbi.1012585 |
| work_keys_str_mv | AT jordanmoutet algorithmstoreconstructpastindelsthedeletiononlyparsimonyproblem AT ericrivals algorithmstoreconstructpastindelsthedeletiononlyparsimonyproblem AT fabiopardi algorithmstoreconstructpastindelsthedeletiononlyparsimonyproblem |