Treewidth-Based Algorithms for the Small Parsimony Problem on Networks

DOI10.4230/LIPICS.WABI.2021.6zbMATH Open1519.92150OpenAlexW4391156430MaRDI QIDQ6133866FDOQ6133866

Authors: Celine Scornavacca, Mathias Weller 

Publication date: 24 July 2023

Full work available at URL: https://hal.science/hal-03287112

Recommendations

• On computing the maximum parsimony score of a phylogenetic network
• Combinatorial Pattern Matching
• Finding a most parsimonious or likely tree in a network with respect to an alignment
• Scanning phylogenetic networks is NP-hard
• Algorithms for phylogeny reconstruction in a new mathematical model

zbMATH Keywords

dynamic programmingparsimonyphylogeneticstreewidthphylogenetic networksparameterized complexity

Mathematics Subject Classification ID

Problems related to evolution (92D15) Dynamic programming (90C39) Computational methods for problems pertaining to biology (92-08)

Cited In (4)

• Finding a most parsimonious or likely tree in a network with respect to an alignment
• On computing the maximum parsimony score of a phylogenetic network
• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
• Bounding the softwired parsimony score of a phylogenetic network

This page was built for publication: Treewidth-Based Algorithms for the Small Parsimony Problem on Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133866)