Format

Send to

Choose Destination
See comment in PubMed Commons below
J Comput Biol. 1995 Spring;2(1):139-52.

Four strikes against physical mapping of DNA.

Author information

1
Sandia National Labs, Albuquerque, New Mexico 87185, USA.

Abstract

Physical mapping is a central problem in molecular biology and the human genome project. The problem is to reconstruct the relative position of fragments of DNA along the genome from information on their pairwise overlaps. We show that four simplified models of the problem lead to NP-complete decision problems: Colored unit interval graph completion, the maximum interval (or unit interval) subgraph, the pathwidth of a bipartite graph, and the k-consecutive ones problem for k > or = 2. These models have been chosen to reflect various features typical in biological data, including false-negative and positive errors, small width of the map, and chimericism.

PMID:
7497116
DOI:
10.1089/cmb.1995.2.139
[Indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for Mary Ann Liebert, Inc.
    Loading ...
    Support Center