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

Content Provider	ACM Digital Library
Author	Keijsper, Judith Oosterwijk, Tim
Copyright Year	2015
Abstract	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 $\textit{k}$ and $\textit{l}.$ Here, $\textit{k}$ denotes the maximum number of ambiguous sites in any genotype, and $\textit{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.
Starting Page	234
Ending Page	247
Page Count	14
File Format	PDF
ISSN	15455963
DOI	10.1109/TCBB.2014.2352031
Volume Number	12
Issue Number	1
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-01-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Drug design Graph Haplotyping Health Hereditary disease Matching problem Path partition Polynomial time algorithm Shortest path
Content Type	Text
Resource Type	Article
Subject	Genetics Biotechnology Applied Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Tractable Cases of $(*,2)$ -Bounded Parsimony Haplotyping

Isomorphism for graphs of bounded distance width.

Pure Parsimony Xor Haplotyping

Isomorphism for graphs of bounded distance width (1997).

Islands of Tractability for Parsimony Haplotyping

Shortest path queries in planar graphs in constant time (2003)

A sequential algorithm to solve next-to-shortest path problem on circular-arc graphs (2006).

The path-partition problem in bipartite distance-hereditary graphs (1998)

Haplotype Inference Constrained by Plausible Haplotype Data

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

Similar Documents

Tractable Cases of $(*,2)$ -Bounded Parsimony Haplotyping

Isomorphism for graphs of bounded distance width.

Pure Parsimony Xor Haplotyping

Isomorphism for graphs of bounded distance width (1997).

Islands of Tractability for Parsimony Haplotyping

Shortest path queries in planar graphs in constant time (2003)

A sequential algorithm to solve next-to-shortest path problem on circular-arc graphs (2006).

The path-partition problem in bipartite distance-hereditary graphs (1998)

Haplotype Inference Constrained by Plausible Haplotype Data

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