ON THE COMPLEXITY OF DNA PHYSICAL MAPPING

被引：57

作者：

GOLUMBIC, MC ^{[1
]}

KAPLAN, H ^{[1
]}

SHAMIR, R ^{[1
]}

机构：

[1] TEL AVIV UNIV, SACKLER FAC EXACT SCI, DEPT COMP SCI, IL-69978 TEL AVIV, ISRAEL

来源：

ADVANCES IN APPLIED MATHEMATICS | 1994年 / 15卷 / 03期

关键词：

D O I：

10.1006/aama.1994.1009

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The physical mapping problem is to reconstruct the relative position of fragments (clones) of DNA along the genome from information on their pairwise overlaps. We show that two simplified versions of the problem belong to the class of NP-complete problems, which are conjectured to be computationally intractable. In one version all clones have equal length, and in another clone lengths may be arbitrary. The proof uses tools from graph theory and complexity. (C) 1994 Academic Press, Inc.

引用

页码：251 / 261

页数：11

共 33 条

[1]

ALIZADEH F, 1993, 4TH P ANN ACM SIAM S, P371

[2] GENOMIC MAPPING BY ANCHORING RANDOM CLONES - A MATHEMATICAL-ANALYSIS [J].

ARRATIA, R ;

LANDER, ES ;

TAVARE, S ;

WATERMAN, MS .

GENOMICS, 1991, 11 (04) :806-827

[3] THEORETICAL-ANALYSIS OF A PHYSICAL MAPPING STRATEGY USING RANDOM SINGLE-COPY LANDMARKS [J].

BARILLOT, E ;

DAUSSET, J ;

COHEN, D .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1991, 88 (09) :3917-3921

[4] ON THE TOPOLOGY OF THE GENETIC FINE STRUCTURE [J].

BENZER, S .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1959, 45 (11) :1607-1620

[5] CLONING OF LARGE SEGMENTS OF EXOGENOUS DNA INTO YEAST BY MEANS OF ARTIFICIAL CHROMOSOME VECTORS [J].

BURKE, DT ;

CARLE, GF ;

OLSON, MV .

SCIENCE, 1987, 236 (4803) :806-812

[6] TOWARD A PHYSICAL MAP OF THE GENOME OF THE NEMATODE CAENORHABDITIS-ELEGANS [J].

COULSON, A ;

SULSTON, J ;

BRENNER, S ;

KARN, J .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1986, 83 (20) :7821-7825

[7] GENOME LINKING WITH YEAST ARTIFICIAL CHROMOSOMES [J].

COULSON, A ;

WATERSTON, R ;

KIFF, J ;

SULSTON, J ;

KOHARA, Y .

NATURE, 1988, 335 (6186) :184-186

[8]

CRAIG AG, 1990, NUCLEIC ACIDS RES, V18, P2653

[9] STUDIES OF SIMIAN VIRUS-40 DNA .7. CLEAVAGE MAP OF SV40 GENOME [J].

DANNA, KJ ;

SACK, GH ;

NATHANS, D .

JOURNAL OF MOLECULAR BIOLOGY, 1973, 78 (02) :363-+

[10]

FELLOWS MR, 1993, 1ST P EUR S ALG, P157

← 1 2 3 4 →