Path: utzoo!utgpu!watserv1!watmath!uunet!bionet!uwm.edu!rpi!julius.cs.uiuc.edu!psuvax1!news
From: huang@client2.cs.psu.edu (Xiaoqiu Huang)
Newsgroups: bionet.software
Subject: A local similarity program
Message-ID: <F1an-4$2@cs.psu.edu>
Date: 4 Nov 90 17:42:03 GMT
Sender: news@cs.psu.edu (Usenet)
Organization: Penn State Computer Science
Lines: 49
Originator: huang@client2.cs.psu.edu
Nntp-Posting-Host: client2.cs.psu.edu


	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


Brought to you by Super Global Mega Corp .com