Tractable cases of $(*,2)$-bounded parsimony haplotyping

J.C.M. Keijsper, T.S. Oosterwijk

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)
172 Downloads (Pure)


Parsimony haplotyping is the problem of finding a set of haplotypes of minimum cardinality that explains a given set of genotypes, where a genotype is explained by two haplotypes if it can be obtained as a combination of the two. This problem is NP-complete in the general case, but polynomially solvable for $(k,l)$ -bounded instances for certain $k$ and $l$ . Here, $k$ denotes the maximum number of ambiguous sites in any genotype, and $l$ is the maximum number of genotypes that are ambiguous at the same site. Only the complexity of the $(*,2)$ -bounded problem is still unknown, where $*$ denotes no restriction. It has been proved that $(*,2)$ -bounded instances have compatibility graphs that can be constructed from cliques and circuits by pasting along an edge. In this paper, we give a constructive proof of the fact that $(*,2)$ -bounded instances are polynomially solvable if the compatibility graph is constructed by pasting cliques, trees and circuits along a bounded number of edges. We obtain this proof by solving a slightly generalized problem on circuits, trees and cliques respectively, and arguing that all possible combinations of optimal solutions for these graphs that are pasted along a bounded number of edges can be enumerated efficiently. Keywords: Drug design, hereditary disease, health, haplotyping, graph, polynomial time algorithm, shortest path, matching problem, path partition
Originele taal-2Engels
Pagina's (van-tot)234-247
Aantal pagina's14
TijdschriftIEEE/ACM Transactions on Computational Biology and Bioinformatics
Nummer van het tijdschrift1
StatusGepubliceerd - 2015


Duik in de onderzoeksthema's van 'Tractable cases of $(*,2)$-bounded parsimony haplotyping'. Samen vormen ze een unieke vingerafdruk.

Citeer dit