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 at cs.yale.edu
Thanks a lot.
Prakash Nadkarni
Yale Medical School
