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)
(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.
PROGRAM INPUT LIMITATIONS:
The length of a binary profile (the number of probes) is limited
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).
OBTAINING THE SOFTWARE:
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).
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
WEISE at 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
University of Georgia
Athens, GA 30602
or by emailing:
ARNOLD at BSCF.UGA.EDU or
ARNOLD at BSCR.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 at WELCHGATE.WELCH.JHU.EDU
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