EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Jordan Moutet, Eric Rivals, Fabio Pardi iD

PLOS Computational Biology · 2025

DOI: 10.1371/journal.pcbi.1012585 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PLOS Computational Biology, 2025. Verfasst von Jordan Moutet und 2 weiteren Autor:innen. Beteiligte Einrichtung: LIRMM, Université de Montpellier, CNRS, Montpellier, France. Hauptthemen laut MEDLINE: Algorithms, INDEL Mutation, Computational Biology, Models, Genetic. Die Arbeit nennt 43 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: French Ministry of Research (Ministère de l’Enseignement supérieur et de la Recherche), Ministère de l’Enseignement supérieur et de la Recherche.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsINDEL MutationComputational BiologyModels, GeneticEvolution, Molecular

Autor:innen und Institutionen

  • LIRMM, Université de Montpellier, CNRS, Montpellier, France.

ORCID-Profile: Fabio Pardi

Förderung

  • French Ministry of Research (Ministère de l’Enseignement supérieur et de la Recherche)
  • Ministère de l’Enseignement supérieur et de la Recherche

Zitieren

APA

Moutet, J., Rivals, E., & Pardi, F. (2025). Algorithms to reconstruct past indels: The deletion-only parsimony problem. PLOS Computational Biology. https://doi.org/10.1371/journal.pcbi.1012585

Vancouver

Moutet J, Rivals E, Pardi F. Algorithms to reconstruct past indels: The deletion-only parsimony problem. PLOS Computational Biology. 2025. doi:10.1371/journal.pcbi.1012585

BibTeX
@article{Moutet2025,
  author = {Moutet, Jordan and Rivals, Eric and Pardi, Fabio},
  title = {Algorithms to reconstruct past indels: The deletion-only parsimony problem},
  journal = {PLOS Computational Biology},
  year = {2025},
  doi = {10.1371/journal.pcbi.1012585}
}
Kostenlos starten →