AN EFFICIENT ALGORITHM FOR THE CONSTRUCTION AND VISUALIZATION OF PHYSICAL MAPS

¹ Department of Mathematical Sciences Clemson University Clemson, SC

² INCOGEN 110 Liberty Dr. Ste 104 Clemson, SC

³ Clemson University Genomics Institute Clemson, SC

Comprehensive physical maps containing information about relative positions of clones along a chromosome play a key role by serving as 'road maps' in sequencing efforts. We have developed an efficient algorithm with a Java-based user interface for the construction, analysis and visualization of robust physical maps of whole chromosomes. The program, PM-CAT (Physical Map Construction and Analysis Tool), analyzes data from either restriction digestion fingerprinting experiments, hybridization experiments or a combination of both. Multiple input formats for the hybridization data (such as an unordered hit/no-hit hybridization matrix) and fingerprinting data (such as output from the Sanger Centre fingerprinting gel analysis package Image) are supported. Fingerprinting and multi-level hybridization data is used in a Bayesian statistics approach to generate overlap weights which are used in a maximum spanning tree algorithm to produce an ordered physical map. The physical map can be further reduced to represent a minimum tile coverage of the chromosome. The results are compared to other physical map construction programs.