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

A linear-time algorithm for the perfect phylogeny haplotyping (PPH) problem.

Journal of computational biology : a journal of computational molecular cell biology - 1 Mar 2006

Ding Zhihong, Filkov Vladimir, Gusfield Dan

Abstract excerpt

Since the introduction of the Perfect Phylogeny Haplotyping (PPH) Problem in RECOMB 2002 (Gusfield, 2002), the problem of finding a linear-time (deterministic, worst-case) solution for it has remained open, despite broad interest in the PPH problem and a series of papers on various aspects of it. In this paper, we solve the open problem, giving a practical, deterministic linear-time algorithm based on a simple...

Read the complete abstract on PubMed

Topics

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

Share to Algorithms
Share to Computational Biology
Share to Data Interpretation, Statistical

Methodology Data sources Editorial policy Privacy Delete account & data About Contact Helena Bioinformatics

Share to Genetic Predisposition to Disease

Share to Haplotypes

Share to Phylogeny

Source

Identifiers

PMID: 16597255
DOI: 10.1089/cmb.2006.13.522

Provenance

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

Source receipt: pubmed, retrieved 7 Sept 2026.

Related research

Semantic proximity does not establish scientific evidence. Graph snapshot: 2026-09-29.

Research trail→

Click a neighbor to travelStep 1 · 12 closest

A linear-time algorithm for the perfect phylogeny haplotyping (PPH) problem.PMID 16597255Read ↗

An efficient algorithm for Perfect Phylogeny Haplotyping.Semantic proximity Read ↗

Constructing near-perfect phylogenies with multiple homoplasy events.Semantic proximity Read ↗

The incomplete perfect phylogeny haplotype problem.Semantic proximity Read ↗

Algorithms for efficient near-perfect phylogenetic tree reconstruction in theory and practice.Semantic proximity Read ↗

The undirected incomplete perfect phylogeny problem.Semantic proximity Read ↗

Optimal imperfect phylogeny reconstruction and haplotyping (IPPH).Semantic proximity Read ↗

Perfect phylogeny haplotyper: haplotype inferral using a tree model.Semantic proximity Read ↗

Haplotyping as perfect phylogeny: a direct approach.Semantic proximity Read ↗

Fixed-parameter algorithms in phylogenetics.Semantic proximity Read ↗

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

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

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

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