Treewidth-Based Algorithms for the Small Parsimony Problem on Networks - Agropolis Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Treewidth-Based Algorithms for the Small Parsimony Problem on Networks

Résumé

Phylogenetic reconstruction is one of the paramount challenges of contemporary bioinformatics. A subtask of existing tree reconstruction algorithms is modeled by the Small Parsimony problem: given a tree T and an assignment of character-states to its leaves, assign states to the internal nodes of T such as to minimize the parsimony score, that is, the number of edges of T connecting nodes with different states. While this problem is polynomial-time solvable on trees, the matter is more complicated if T contains reticulate events such as hybridizations or recombinations, i.e. when T is a network. Indeed, three different versions of the parsimony score on networks have been proposed and each of them is NP-hard to decide. Existing parameterized algorithms focus on combining the number of possible character-states with the number of reticulate events (per biconnected component). Here, we consider the treewidth of the undirected graph underlying the input network as parameter, presenting dynamic programming algorithms for (slight generalizations of) all three versions of the parsimony problem on networks. Our algorithms use a formulation of the treewidth that may facilitate formalizing treewidth-based dynamic programming algorithms on phylogenetic networks for other problems .
Fichier principal
Vignette du fichier
tw.pdf (791.35 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03287112 , version 1 (15-07-2021)

Identifiants

Citer

Celine Scornavacca, Mathias Weller. Treewidth-Based Algorithms for the Small Parsimony Problem on Networks. 21st International Workshop on Algorithms in Bioinformatics (WABI), Aug 2021, Chicago. Due to COVID-19, WABI 2021 will be held online., United States. pp.6:1, ⟨10.4230/LIPIcs.WABI.2021.6⟩. ⟨hal-03287112⟩
76 Consultations
93 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More