Complexity and approximation of the minimum recombinant haplotype configuration problem

DOI10.1016/j.tcs.2007.02.036zbMath1113.92049OpenAlexW2065694619MaRDI QIDQ2371806

Tao Jiang, Lan Liu, Jing Xiao, Chen Xi

Publication date: 9 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.036

zbMATH Keywords

pedigreecomplexityapproximationSNPchildrensingle nucleotide polymorphismhaplotypingbounded numberL-reductionmatesnegative resultpositive resultrecombinant

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Genetics and epigenetics (92D10)

Related Items (1)

Beyond evolutionary trees

Cites Work

• Unnamed Item
• Optimization, approximation, and complexity classes
• On the power of unique 2-prover 1-round games
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• The complexity of satisfiability problems

This page was built for publication: Complexity and approximation of the minimum recombinant haplotype configuration problem