Haplotype Inferring Via Galled-Tree Networks Is NP-Complete

DOI10.1007/978-3-540-69733-6_29zbMath1148.92306OpenAlexW2096634448MaRDI QIDQ3511338

Ladislav Stacho, Xiaohong Zhao, Ján Maňuch, Arvind Kumar Gupta

Publication date: 10 July 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69733-6_29

Mathematics Subject Classification ID

Problems related to evolution (92D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10)

Related Items (1)

Phylogeny- and parsimony-based haplotype inference with constraints

Cites Work

• Unnamed Item
• Haplotype inferring via galled-tree networks using a hypergraph covering problem for special genotype matrices
• On the computational complexity of the rooted subtree prune and regraft distance
• Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination
• Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
• The Fine Structure of Galls in Phylogenetic Networks

This page was built for publication: Haplotype Inferring Via Galled-Tree Networks Is NP-Complete