The LALIGN program of the FASTA package does this. I quote from the
documentation:
LALIGN Calculates the N-best local alignments using a rigorous
algorithm. (N=10 by default.) The algorithm was
developed by Huang and Miller (X. Huang and W. Miller
(1991) Adv. Appl. Math. 12:337-357), which is a
linear-space version of an algorithm described by M. S.
Waterman and M. Eggert (J. Mol. Biol. 197:723-728).
Like SSEARCH, LALIGN is rigorous, but also very slow.
The FASTA package is available from ftp.virginia.edu
Martijn Huynen wrote:
>> Hi
>> Does anybody have C-code for the modified version of the Smith-Waterman
> algorithm that also gives "non-intersecting similar subsequences"
> (published in J. Mol. Biol. (1987) 197, 723-728 by Waterman and Eggert)
> (the disadvantage of the original Smith-Waterman code is that it only
> gives one "hit" per pair of sequences, Blast does not have this disadvantage
> but is less rigorous/sensitive)
>> many thanks, Martijn
>> Martijn Huynen
> Biocomputing Group, EMBL
> Meyerhofstrasse 1
> 69012 Heidelberg, Germany
> tel: +49-6221-387372
> fax: +49-6221-387517
--
+---------------------------------------------------------------------+
| Henrik Nielsen, hnielsen at cbs.dtu.dk |
| CBS - Center for Biological Sequence Analysis |
| IK - Department of Chemistry |
| DTU - The Technical University of Denmark, Bldg 206, DK-2800 Lyngby |
| phone: (+45) 4525 2470, fax: (+45) 4593 4808 |
| home phone: (+45) 31 39 93 87 |
+---------------------------------------------------------------------+
