A LOCAL ALIGNMENT TOOL FOR VERY LONG DNA-SEQUENCES

This paper presents a practical program, called sim2, for building loc al alignments of two sequences, each of which may be hundreds of kilob ases long. sim2 first constructs n best non-intersecting chains of 'fr agments', such as all occurrences of identical 5-tuples in each of two DNA sequences,for any specified n greater than or equal to 1. Each ch ain is then refined by delivering an optimal alignment in a region del imited by the chain. sim2 requires only space proportional to the size of the input sequences and the output alignments, and the same source code runs on Unix machines, on Macintoshes, on PCs, and on DEC Alpha PCs. We also describe an application of sim2 for aligning long DNA seq uences from Escherichia coli. sim2 facilitates contig-building by prov iding a complete view of the related sequences, so differences can be analyzed and inconsistencies resolved Examples are shown using the ali gnment display and editing functions from the software tool ChromoScop e.