Subject: (none)

From: [email-masked]
Date: 21 Nov 1994 07:41:25 -0800

A fast random cost algorithm for physical mapping

PROGRAM DESCRIPTION:

        This program is to assist in constructing a physical map
        of a whole chromosome or chromosome fragment from a
        binary clone/probe hybridization matrix.  

	The theory for the physical mapping method can be
        found in

        Cuticchia, A.J., J. Arnold, and W.E. Timberlake (1992).
        The use of simulated annealing in chromosome reconstruction
        experiments based on binary scoring.  Genetics 132: 591-601

        The input data is a binary clone/probe hybridization matrix (with 
        a '1' indicating hybridization and a '0' indicating no hybridization)
        of n clones (rows) and m probes (columns).  Each row of
        the clone/probe hybridization matrix is the digital 'call number'
        of a particular clone.  When clones overlap, they tend
        to hybridize to the same probes, and their digital call numbers
        tend to be similar.  Probes (columns) link together clones
        into contiguous blocks or contigs by their shared pattern
        of clonal hybridization.  This program for ordering cloned DNA
        fragments into 'contig map' does so by permuting the rows
        of the clone/probe hybridization matrix so that clones
        with similar call numbers appear next to each other.
        DNA fragments with a high degree of overlap are expected
        to show a high degree of similarity in their profiles.
        A distance is defined between each clone by counting
        the number of differences in their digital call numbers.
        The ordering process is based on minimizing the sum of the linking
        distances between clones as a function of their ordering along the
        chromosome. 

        The algorithm has been used to map the fourth chromosome of
        Aspergillus nidulans, the whole genome of Schizosaccharomyces
        pombe genome, and a region of human chromosome 9.

	This algorithm used here to minimize the total linking distance
        is a new one called random cost algorithm. It is detailed in 

	Wang, Y., Prade, R. A., Griffith, J., Timberlake, W.E., and Arnold, J.
	(1994) A fast random cost algorithm for physical mapping. PNAS,
	91, 11094-11098

PROGRAM INPUT

	A typical batch file is given as follows:

	$set def [wang.cm.bootstrap]
	$run cost 
	cost.dat
	probe.dat
	cost.map
	rec
	0

	The first line is to set the default directory.

	The second line is to run this program

	The third line is the input file name. In the input hybridization file,
	the first line should be the number of probes, clones  and bootstrap
        run numbers. For all other lines, the first ten columns are reserved
        for the clone name, and the hybridization data should start at any
         column after 10th column. Total length of each 
	line is defined by MAX_BUFFER in the program.

	The fourth line is the probe names file name. It contains the probe
        names in the same order across the columns as in the input file.

	The fifth line is the output file name. The finally reconstructed
        physical map, the statistical confidence statistics from the
        bootstrap run and other statistics are written to this file.

	The sixth line is the name of the file that stores the total linking
        distance for each bootstrap run. This is for tracing how the program
        is running.

	The seven line is the seed for random number generator.

PROGRAM INPUT LIMITATIONS:

        The number of clones must be between 1 and 600 for a DEC VAX
	station 4000.

        Filenames (with directory path, if specified) must be
        no longer than 40 characters.

	If the bootstrap run number is not given in the input binary
        hybridization data file, it will be set to the default number of 1000. 

PROGRAM SPEED:

        The program assembled a physical map of 593  clones
        probed with 115 probes within less than 2 mins on a DEC
	VAX station 4000. Total time for 1000 bootstraps run will take
	30 CPU hours on this workstation.

OBTAINING THE SOFTWARE:

        The software is only distributed via
        Internet using EMAIL. Please send an EMAIL request to:

                    [email-masked]

        if you wish copies of the program. I will EMAIL you:

        1) a C program  cost.c;

        2) this documentation file, cost.DOC;

        3) a test input file, cost.dat;

	4) a test probe name file, probe.dat

        4) an example output file, map.cost ; and

        5) a command file, cost.COM.

        This last file is what you would use to submit a batch job in
        the VAX/VMS operating system to generate cost.MAP.

SOFTWARE SUPPORT IN THE USE OF THE PROGRAMS:

        If you have questions about
        the programs, please contact Yuhong Wang currently located
        at University of Georgia:

                    [email-masked]
        or myself.

HARDWARE LIMITATIONS:

        The programs have been run without modification on VAXstations,
        a DECstation 3100,  a Silicon Graphics IRIS 4D70/GT workstation
        and IBM Risc 6000 workstation.

  . - - - - - - - - - - - Jonathan Arnold - - - - - - - - - - - - - - - .
  |                       Dept. of Genetics,                            |
  |                       University of Georgia                         |
  |                       Athens, Georgia 30602                         |
  | Phone:       (706) 542-1449                                         |
  | messages:    (706) 542-8000                                         |
  | FAX:         (706) 542-3910                                         |
  | Internet:    [email-masked]                                    |
  | Alternate:   [email-masked]                                    |
  . - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - .