huang@client2.cs.psu.edu (Xiaoqiu Huang) (11/05/90)
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@bchs.uh.edu (internet) gene-server%bchs.uh.edu@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@cs.mtu.edu