Treewidth-Based Algorithms for the Small Parsimony Problem on Networks

DOI10.4230/LIPICS.WABI.2021.6MaRDI QIDQ6133866zbMATH OpenOpenAlexFDO

Authors Celine Scornavacca, Mathias Weller

Publication date 24 July 2023

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

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)

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

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)