On Computing the Maximum Parsimony Score of a Phylogenetic Network

DOI10.1137/140959948zbMath1328.68300arXiv1302.2430OpenAlexW2083011587MaRDI QIDQ5251626

Celine Scornavacca, Leo van Iersel, Steven Kelk, Mareike Fischer

Publication date: 20 May 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.2430

zbMATH Keywords

softwarecomplexityparsimonyfixed-parameter tractabilityphylogenetic treesphylogenetic networksapproximability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (9)

Non-essential arcs in phylogenetic networks ⋮ Classes of explicit phylogenetic networks and their biological and mathematical significance ⋮ On the quirks of maximum parsimony and likelihood on phylogenetic networks ⋮ Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks ⋮ Reconciliation of a gene network and species tree ⋮ Finding a most parsimonious or likely tree in a network with respect to an alignment ⋮ Treewidth of display graphs: bounds, brambles and applications ⋮ Heading in the right direction? Using head moves to traverse phylogenetic network space ⋮ On Computing the Maximum Parsimony Score of a Phylogenetic Network

Uses Software

• Dendroscope

Cites Work

• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• Seeing the trees and their branches in the network is hard
• Simple and improved parameterized algorithms for multiterminal cuts
• The Steiner problem in phylogeny is NP-complete
• Locating a tree in a phylogenetic network
• When two trees go to war
• Parametrized complexity theory.
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Locating the vertices of a steiner tree in an arbitrary metric space
• The Complexity of Multiterminal Cuts
• On Computing the Maximum Parsimony Score of a Phylogenetic Network
• Unnamed Item
• Unnamed Item

This page was built for publication: On Computing the Maximum Parsimony Score of a Phylogenetic Network