Contig selection in physical mapping

Heber S, Stoye J, Frohme M, Hoheisel J, Vingron M (2000)
Journal of Computational Biology 7(3-4): 395-408.

Journal Article | Published | English
; ; ; ;
In physical mapping, one orders a set of genetic landmarks or a library of cloned fragments of DNA according to their position in the genome. Our approach to physical mapping divides the problem into smaller and easier subproblems by partitioning the probe set into independent parts (probe contigs). For this purpose we introduce a new distance function between probes, the averaged rank distance (ARD) derived from bootstrap resampling of the raw data. The ARD measures the pairwise distances of probes within a contig and smoothes the distances of probes across different contigs. It shows distinct jumps at contig borders. This makes it appropriate for contig selection by clustering. We have designed a physical mapping algorithm that makes use of these observations and seems to be particularly well suited to the delineation of reliable contigs. We evaluated our method on data sets from two physical mapping projects. On data from the recently sequenced bacterium Xylella fastidiosa, the probe contig set produced by the new method was evaluated using the probe order derived from the sequence information. Our approach yielded a basically correct contig set. On this data we also compared our method to an approach which uses the number of supporting clones to determine contigs. Our map is much more accurate. In comparison to a physical map of Pasteurella haemolytica that was computed using simulated annealing, the newly computed map is considerably cleaner. The results of our method have already proven helpful for the design of experiments aimed at further improving the quality of a map.
Publishing Year

Cite this

Heber S, Stoye J, Frohme M, Hoheisel J, Vingron M. Contig selection in physical mapping. Journal of Computational Biology. 2000;7(3-4):395-408.
Heber, S., Stoye, J., Frohme, M., Hoheisel, J., & Vingron, M. (2000). Contig selection in physical mapping. Journal of Computational Biology, 7(3-4), 395-408. doi:10.1089/106652700750050853
Heber, S., Stoye, J., Frohme, M., Hoheisel, J., and Vingron, M. (2000). Contig selection in physical mapping. Journal of Computational Biology 7, 395-408.
Heber, S., et al., 2000. Contig selection in physical mapping. Journal of Computational Biology, 7(3-4), p 395-408.
S. Heber, et al., “Contig selection in physical mapping”, Journal of Computational Biology, vol. 7, 2000, pp. 395-408.
Heber, S., Stoye, J., Frohme, M., Hoheisel, J., Vingron, M.: Contig selection in physical mapping. Journal of Computational Biology. 7, 395-408 (2000).
Heber, Steffen, Stoye, Jens, Frohme, Marcus, Hoheisel, Jörg, and Vingron, Martin. “Contig selection in physical mapping”. Journal of Computational Biology 7.3-4 (2000): 395-408.
Main File(s)
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

22 References

Data provided by Europe PubMed Central.

booth, j comput syst sci 13(), 1976
The use of simulated annealing in chromosome reconstruction experiments based on binary scoring.
Cuticchia AJ, Arnold J, Timberlake WE., Genetics 132(2), 1992
PMID: 1427046
ODS_BOOTSTRAP: assessing the statistical reliability of physical maps by bootstrap resampling.
Wang Y, Prade RA, Griffith J, Timberlake WE, Arnold J., Comput. Appl. Biosci. 10(6), 1994
PMID: 7704661
On the consistency of a physical mapping method to reconstruct a chromosome in vitro.
Xiong M, Chen HJ, Prade RA, Wang Y, Griffith J, Timberlake WE, Arnold J., Genetics 142(1), 1996
PMID: 8770604
CONTIG EXPLORER: interactive marker-content map assembly.
Nadkarni PM, Banks A, Montgomery K, LeBlanc-Stracewski J, Miller P, Krauter K., Genomics 31(3), 1996
PMID: 8838311
Revealing hidden interval graph structure in STS-content data.
Harley E, Bonner A, Goodman N., Bioinformatics 15(4), 1999
PMID: 10320395
Whole-genome shotgun optical mapping of Deinococcus radiodurans.
Lin J, Qi R, Aston C, Jing J, Anantharaman TS, Mishra B, White O, Daly MJ, Minton KW, Venter JC, Schwartz DC., Science 285(5433), 1999
PMID: 10477518
Preliminary ranking procedures for multilocus ordering.
Weeks DE, Lange K., Genomics 1(3), 1987
PMID: 3446584
Physical mapping of chromosomes using unique probes.
Alizadeh F, Karp RM, Weisser DK, Zweig G., J. Comput. Biol. 2(2), 1995
PMID: 7497125
High resolution cosmid and P1 maps spanning the 14 Mb genome of the fission yeast S. pombe.
Hoheisel JD, Maier E, Mott R, McCarthy L, Grigoriev AV, Schalkwyk LC, Nizetic D, Francis F, Lehrach H., Cell 73(1), 1993
PMID: 8462094
Physical mapping of chromosomes: A combinatorial problem in molecular biology
Alizadeh, Algorithmica 13(1-2), 1995
Hybridization mapping of Trypanosoma cruzi chromosomes III and IV.
Hanke J, Frohme M, Laurent JP, Swindle J, Hoheisel JD., Electrophoresis 19(4), 1998
PMID: 9588791
A fast random cost algorithm for physical mapping.
Wang Y, Prade RA, Griffith J, Timberlake WE, Arnold J., Proc. Natl. Acad. Sci. U.S.A. 91(23), 1994
PMID: 7972016
An STS-based map of the human genome.
Hudson TJ, Stein LD, Gerety SS, Ma J, Castle AB, Silva J, Slonim DK, Baptista R, Kruglyak L, Xu SH, Hu X, Colbert AM, Rosenberg C, Reeve-Daly MP, Rozen S, Hui L, Wu X, Vestergaard C, Wilson KM, Bae JS, Maitra S, Ganiatsas S, Evans CA, DeAngelis MM, Ingalls KA, Nahf RW, Horton LT Jr, Anderson MO, Collymore AJ, Ye W, Kouyoumjian V, Zemsteva IS, Tam J, Devine R, Courtney DF, Renaud MT, Nguyen H, O'Connor TJ, Fizames C, Faure S, Gyapay G, Dib C, Morissette J, Orlin JB, Birren BW, Goodman N, Weissenbach J, Hawkins TL, Foote S, Page DC, Lander ES., Science 270(5244), 1995
PMID: 8533086
Algorithms and software tools for ordering clone libraries: application to the mapping of the genome of Schizosaccharomyces pombe.
Mott R, Grigoriev A, Maier E, Hoheisel J, Lehrach H., Nucleic Acids Res. 21(8), 1993
PMID: 8493107
Fine-mapping of shotgun template-libraries; an efficient strategy for the systematic sequencing of genomic DNA.
Scholler P, Karger AE, Meier-Ewert S, Lehrach H, Delius H, Hoheisel JD., Nucleic Acids Res. 23(19), 1995
PMID: 7479026
Bootstrap Methods: Another Look at the Jackknife
Efron, The Annals of Statistics 7(1), 1979
Chapter 22 The Physical Map of the Caenorhabditis elegans Genome
A branch-and-cut approach to physical mapping of chromosomes by unique end-probes.
Christof T, Junger M, Kececioglu J, Mutzel P, Reinelt G., J. Comput. Biol. 4(4), 1997
PMID: 9385538
Building human genome maps with radiation hybrids.
Slonim D, Kruglyak L, Stein L, Lander E., J. Comput. Biol. 4(4), 1997
PMID: 9385541


0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®


PMID: 11108470
PubMed | Europe PMC

Search this title in

Google Scholar