Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!samsung!usc!wuarchive!bcm!bionet!mcoiarc.bitnet!TAO%OPUS
From: TAO%OPUS@mcoiarc.bitnet
Newsgroups: bionet.software
Subject: (Too long to write)
Message-ID: <D335331BCE5F003345@MCOIARC.BITNET>
Date: 16 Jan 91 19:56:00 GMT
Sender: daemon@genbank.bio.net
Lines: 55

>Date: 16 Jan 91 17:52:30 GMT
>From: nadkarni-prakash@cs.yale.edu
>Subject: Request for contig building/clone overlap detection algorithms
>
>I am looking for references to published algorithms - or programs
>written in C or C++ - which, given a bunch of clones (of known
>sequence) which are fragments of a larger DNA sequence, perform
>pairwise overlapping clone detection, and possibly go on from there to
>try to build a contig from this clone set. There is such a program
>written for the Cray by D.Tourney at Los Alamos- unfortunately, we
>don't have access to a Cray, and the rest of our software is C-based,
>so a description of the algorithm might be more useful for us.
>
>An algorithm which is reasonably tolerant of experimental error in the
>determination of the sequences of the individual clones would be
>preferred.
>
>I presume the algorithm for overlap detection would be partly based on
>the dynamic programming methods of standard sequence comparison
>algorithms (Smith-Waterman, FASTA etc.) and go on from there- but I'd
>appreciate specifics.
>
>I understand that the program itself will be extremely time-consuming
>(we use a parallel programming environment called C-Linda to run our
>programs on multiprocessor UNIX machines).
>
>Is there anyone at Los Alamos who can help out with this one?
>
>Please send a reply to nadkarni@cs.yale.edu
>
>Thanks a lot.
>
>Prakash Nadkarni
>Yale Medical School
>

I think there is already a program called SIM written in C available.  It was
claimed to be fast, and it is written for the Unix machine.  It might be
obtained by ftp or e-mail request from genbank.bio.net.

Also I think that it is the operating system which is more important than the
language in which the program is written.  The SIM, mentioned above could not
be run on a VAX machine with the VMS operating system would be a good example.

For your specific purpose, I think you need to add something more onto this
SIM, so the sequence comparison results can be aligned and written in a desired
format to faciltate the later editing and compiling.

Please notify me your result.

Good luck!

Tao Tao
Department of Microbiology
Medical College of Ohio at Toledo