Haplotype Inferring Via Galled-Tree Networks Is NP-Complete
From MaRDI portal
Publication:3511338
DOI10.1007/978-3-540-69733-6_29zbMath1148.92306MaRDI QIDQ3511338
Ján Maňuch, Arvind Kumar Gupta, Xiaohong Zhao, Ladislav Stacho
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
92D15: Problems related to evolution
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
92D10: Genetics and epigenetics
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