Discover Community Create You

Loading publication...

Noodle always counts identifier-free feature events for service operation. With your permission, Google Analytics can also estimate audience and engagement. Search text, publication identifiers, cookies, IP addresses and browser fingerprints are never included in Noodle's first-party event counters.

Privacy details

Article

Islands of tractability for parsimony haplotyping.

Proceedings. IEEE Computational Systems Bioinformatics Conference - 1 Jan 2005

Sharan Roded, Halldósson Bjarni V, Istrail Sorin

Abstract excerpt

We study the parsimony approach to haplotype inference, which calls for finding a set of haplotypes of minimum cardinality that explains an input set of genotypes. We prove that the problem is APX-hard even in very restricted cases. On the positive side, we identify islands of tractability for th...

Read the complete abstract on PubMed

Topics

Share this publication in a Topic to start or enrich a Post.

Share to Algorithms
Share to Base Sequence
Share to Chromosome Mapping

Methodology Data sources Editorial policy Privacy About Contact Helena Bioinformatics

Share to Genomic Islands

Share to Haplotypes

Share to Molecular Sequence Data

Share to Sequence Alignment

Share to Sequence Analysis, DNA

Source

Identifiers

PMID: 16447963
DOI: 10.1109/csb.2005.37

Provenance

PubMed metadata and Literature Corpus relationships. Corpus snapshot updated 2 Sept 2026. Prepared record publication-16447963-2026-09-02.2. Manifest publication-graph-cohort-2026-09-02.2.

Source receipt: PubMed via Helena Literature Corpus, retrieved 2 Sept 2026.

Related research

Semantic proximity does not establish scientific evidence.

Research trail→

Click a neighbor to travelStep 1 · 12 closest

Islands of tractability for parsimony haplotyping.PMID 16447963Read ↗

Islands of tractability for parsimony haplotyping.Semantic proximity Read ↗

Shorelines of islands of tractability: algorithms for parsimony and minimum perfect phylogeny haplotyping problems.Semantic proximity Read ↗

Tractable Cases of (*,2)-Bounded Parsimony Haplotyping.Semantic proximity Read ↗

Haplotype inference constrained by plausible haplotype data.Semantic proximity Read ↗

Haplotype inference by Pure Parsimony: a survey.Semantic proximity Read ↗

Toward an algebraic understanding of haplotype inference by pure parsimony.Semantic proximity Read ↗

Pure parsimony xor haplotyping.Semantic proximity Read ↗

Efficient reconstruction of haplotype structure via perfect phylogeny.Semantic proximity Read ↗

Haplotype inferring via galled-tree networks is NP-complete.Semantic proximity Read ↗

Integer programming approaches to haplotype inference by pure parsimony.Semantic proximity Read ↗

Computational problems in perfect phylogeny haplotyping: typing without calling the allele.Semantic proximity Read ↗

Parameterised algorithms of the individual haplotyping problem with gaps.Semantic proximity Read ↗

⌁Select a neighboring publication to make it the new centre.