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.

IEEE/ACM transactions on computational biology and bioinformatics - 1 Jan 2000

Sharan Roded, Halldórsson 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 the problem, by focusing on instances with specific structure of haplotype sharing among the input genotypes. We exploit...

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 DNA Mutational Analysis

Share to Genomic Islands

Share to Haplotypes

Share to Molecular Sequence Data

Share to Sequence Analysis, DNA

Source

Identifiers

PMID: 17048467
DOI: 10.1109/TCBB.2006.40

Provenance

PubMed metadata and Literature Corpus relationships. Corpus snapshot updated 7 Sept 2026. Manifest publication-graph-cohort-2026-09-07.1.

Source receipt: pubmed, retrieved 7 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 17048467Read ↗

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.