arnold at BSCR.UGA.EDU arnold at BSCR.UGA.EDU
Sun Aug 8 11:28:00 EST 1993

TO: Those Interested
FROM: Jonathan Arnold, ARNOLD at BSCF.UGA.EDU

                        DISTRIBUTION INFORMATION ON
                        Ordering DNA Sequences (ODS)

                                 ver 1.3

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


        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. The algorithm has been used
        to map the entire Schizosaccharomyces pombe genome, regions
        of the Aspergillus nidulans genome, and a region of a human
        chromosome 9. 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. (1993). ODS:
        Ordering DNA Sequences, a physical mapping algorithm based on
        simulated annealing. CABIOS 9, 215-219

        Any published use of these programs should cite this reference.

        Simulated annealing allows approximate heuristic 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


        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.


        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.

        The program also outputs a number of statistics useful in
        contig identification, such as the probability that a
        probe hybridizes to a clone and the tail area of an
        exact test for overlap between two clones.

        The program presents a reordered data matrix so that
        a researcher has a graphical display of the map
        and a sense of how the algorithm ordered the clones
        in a library.


        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.


        The program assembled a complete physical map of 809 clones
        probed with 92 probes in 3 1/2 minutes on a VAXstation 4000 (12 MIPS).


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

                    ARNOLD at BSCF.UGA.EDU
                    ARNOLD at BSCR.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; and

        5) a command file, ODS.COM.

        This last 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).


        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 
                    WEISE at BSCF.UGA.EDU


        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 at BSCF.UGA.EDU or
                    ARNOLD at BSCR.UGA.EDU

        If you have questions about
        the programs, please contact Dr. A. Jamie Cuticchia currently located
        at Johns Hopkins University:

                    JAMIE at WELCHGATE.WELCH.JHU.EDU
        or myself.


        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 at BSCF.UGA.EDU                                    |
  | Alternate:   ARNOLD at BSCR.UGA.EDU                                    |
  . - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - .

More information about the Bio-soft mailing list