PHYSICAL MAPPING OF CHROMOSOMES - A COMBINATORIAL PROBLEM IN MOLECULAR-BIOLOGY

被引：34

作者：

ALIZADEH, F ^{[1
]}

KARP, RM ^{[1
]}

NEWBERG, LA ^{[1
]}

WEISSER, DK ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY, DIV COMP SCI, BERKELEY, CA 94720 USA

来源：

ALGORITHMICA | 1995年 / 13卷 / 1-2期

关键词：

CLONE; DNA; LOCAL SEARCH; MAXIMUM LIKELIHOOD; OLIGONUCLEOTIDE; PHYSICAL MAPPING; PROBE; TRAVELING-SALESMAN PROBLEM;

D O I：

10.1007/BF01188581

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper is concerned wth the physical mapping of DNA molecules using data about the hybridization of oligonucleotide probes to a library of clones. In mathematical terms, the DNA molecule corresponds to an interval on the real line, each clone to a subinterval, and each probe occurs at a finite set of points within the interval. A stochastic model for the occurrences of the probes and the locations of the clones is assumed. Given a matrix of incidences between probes and clones, the task is to reconstruct the most likely interleaving of the clones. Combinatorial algorithms are presented for solving approximations to this problem, and computational results are presented.

引用

页码：52 / 76

页数：25

共 8 条

[1]

BLUM A, 1991, 23RD P ACM S THEOR C, P328

[2] OPTIMIZING RESTRICTION FRAGMENT FINGERPRINTING METHODS FOR ORDERING LARGE GENOMIC LIBRARIES [J].

BRANSCOMB, E ;

SLEZAK, T ;

PAE, R ;

GALAS, D ;

CARRANO, AV ;

WATERMAN, M .

GENOMICS, 1990, 8 (02) :351-366

[3] CONSTRUCTING CHROMOSOME-SPECIFIC AND REGION-SPECIFIC COSMID MAPS OF THE HUMAN GENOME [J].

CARRANO, AV ;

DEJONG, PJ ;

BRANSCOMB, E ;

SLEZAK, T ;

WATKINS, BW .

GENOME, 1989, 31 (02) :1059-1065

[4]

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

[5]

LANDER E S, 1988, Genomics, V2, P231

[6]

LIN S, 1973, OPERATIONS RES, V21

[7] APPROXIMATION ALGORITHMS FOR THE SHORTEST COMMON SUPERSTRING PROBLEM [J].

TURNER, JS .

INFORMATION AND COMPUTATION, 1989, 83 (01) :1-20

[8] ASSEMBLY AND ANALYSIS OF COSMID CONTIGS IN THE CEA-GENE FAMILY REGION OF HUMAN CHROMOSOME-19 [J].

TYNAN, K ;

OLSEN, A ;

TRASK, B ;

DEJONG, P ;

THOMPSON, J ;

ZIMMERMANN, W ;

CARRANO, A ;

MOHRENWEISER, H .

NUCLEIC ACIDS RESEARCH, 1992, 20 (07) :1629-1636

← 1 →