From: arnold%gandal.dnet@SERVER.UGA.EDU
Newsgroups: bionet.genome.chrom22
Subject: (none)
Date: 11 Oct 92 17:26:09 GMT
Distribution: bionet

TO: Those Interested
FROM: Jonathan Arnold, ARNOLD@BSCF.UGA.EDU
SUBJECT: ODS

                        DISTRIBUTION INFORMATION ON
                        Ordering DNA Sequences (ODS)

                                 ver 1.1

                         (c) 1990 The Univ of GA &
                            A. Jamie Cuticchia

PROGRAM DESCRIPTION:

        Programs are now available to assist in the in vitro
reconstruction of chromosomes or chromosome fragments ("contig mapping")
from a clonal library. The theory behind the ODS program for  "contig mapping"
can be found in:

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

        ODS is a program that orders DNA sequences based on similarity of 
their binary profiles assigned to clones in a library by one of
several experimental approaches. DNA
fragments with a high degree of overlap are expected to show a high degree of
similarity in their profiles.  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 used to minimize this
criterion is a combinatorial optimization method called simulated annealing.
The algorithm is described in:

        Cuticchia, A.J., Arnold, J., and W.E. Timberlake. (1992b). ODS:
Ordering DNA Sequences, a physical mapping algorithm based on
simulated annealing. CABIOS, in press

Any published use of these programs should cite this reference.



        Simulated annealing allows approximate solutions to
Np complete problems in a finite amount of time.  The annealing parameters
in this program are set at the following values:

                        Temperature =          50
                        Maximum Trials =       500000
                        Maximum Successes =    25000
                        Decrease in T =        0.5


PROGRAM INPUT:

        The program requires answers to three questions.  The first
is the name of the file which has the binary profile data (INFILE).  
The second is the name of the file to which the order should be 
written (OUTFILE).  The third is one seed for the random number generator
(IDUM). The program will not prompt you for this input, if
run interactively, to keep it streamlined for use in a batch queue.

PROGRAM OUTPUT:

        The program outputs the inferred minimum linking distance
on the first line, and on succeeding lines, the inferred ordering
of clones in the first column and the linking distance between
successive clones in the second column.

PROGRAM INPUT LIMITATIONS:

        The length of a binary profile (the number of probes) is limited
to 100.

        The number of clones must be between 1 and 1000.

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

        The seed can be any integer between -2147483648 and 2147483647.

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

                    ARNOLD@BSCF.UGA.EDU

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

1) a FORTRAN program, ODS.FOR

2) this documentation file, ODS.DOC

3) a test input file, ODS.DAT

4) an example output file, ODS.OUT

5) a command file, ODS.COM.

This file is what you would use to submit a batch job in
the VAX/VMS operating system to generate ODS.OUT. The values were used
to generate the output in Cuticchia et al. (1992b).


USING THE SOFTWARE WITHOUT THE PROGRAMS: The programs also have been
incorporated into a DNA sequence analysis package (Arnold et al., 1986),
and can be accessed directly on the Biological Sequence/Structure
Computational Facility (BS/SCF). Contact Dr. Weise for a guest account 
at:
                    WEISE@BSCF.UGA.EDU

OBTAINING FURTHER DOCUMENTATION: The best source of documentation
are the papers by Cuticchia  et al. (1992a, 1992b). A reprint can be
obtained by writing:

                    Dr. Jonathan Arnold
                    Genetics Department
                    University of Georgia
                    Athens, GA 30602
or by emailing:
                    ARNOLD%BSCF.UGA.EDU

SOFTWARE SUPPORT IN THE USE OF THE PROGRAMS: If you have questions about
the programs, please contact Dr. A. Jamie Cuticchia currently located
at Johns Hopkins University:

                    JAMIE@WELCHGATE.WELCH.JHU.EDU

HARDWARE LIMITATIONS:

     The programs have been run with minor modification on VAXstations,
a DECstation 3100, and on a Silicon Graphics IRIS 4D70/GT 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:    ARNOLD@BSCF.UGA.EDU                                    |
  . - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - .