A LOCAL SIMILARITY PROGRAM
We have developed a local similarity program (called SIM).
SIM finds k best non-intersecting local alignments between two
sequences or within one sequence. Using dynamic programming
techniques, SIM is guaranteed to find optimal alignments. The
alignments are reported in order of similarity score, with the
highest scoring alignment first. The k best alignments share no
aligned pairs from the same positions in both sequences.
SIM can be used to compare both nucleic acid and protein sequences.
The main strength of SIM is its low space requirement.
SIM requires space proportional to the sum of the
input sequence lengths and the output alignment lengths. Thus
SIM can handle sequences of tens of thousands, even a hundred of
thousands, of base pairs on a workstation. Note that previous
dynamic programming algorithms require space proportional to
the product of the sequence lengths and hence can process only
sequences of a few thousand base pairs.
For the description of the algorithm, please see the paper
"A Time-Efficient, Linear-Space Local Similarity Algorithm"
Xiaoqiu Huang and Webb Miller
(Advances in Applied Mathematics, in press)
An early version of this program is presented in the paper
"A Space-Efficient Algorithm for Local Similarities"
Xiaoqiu Huang, Ross C. Hardison and Webb Miller
(Computer Applications in the Biosciences, in press)
The SIM program is written in C and runs under UNIX systems.
SIM is available free of charge.
To obtain a copy of the program, send electronic mail to
the University of Houston file server at the address:
gene-server at bchs.uh.edu (internet)
gene-server%bchs.uh.edu at CUNYVM (BITNET)
with the Subject line as
Subject: send unix sim.shar
This announcement is posted from Penn State.
I can be reached at the address below.
Xiaoqiu Huang
Department of Computer Science
Michigan Technological University
Houghton, MI 49931
Phone: (906) 487-2123
E-mail: huang at cs.mtu.edu
