A LOCAL SEQUENCE ALIGNMENT ALGORITHM USING AN ASSOCIATIVE MODEL OF PARALLEL COMPUTATION

摘要

Local sequence alignment is widely used to discover structural and hence, functional similarities between biological sequences. While the faster heuristic methods like BLAST and FASTA are useful to compare a single sequence to hundreds or even thousands of sequences in genetic databases such as GenBank, EMBL, and DDBJ, this work yields pairwise alignments with a high sensitivity. The heuristic methods are ideal for narrowing down the number of “good” sequences. Rigorous alignment can then be utilized for an in-depth comparison between the query sequence and the newly found sequence subset. A data-parallel algorithm for local sequence alignment based on the Smith-Waterman algorithm has been adapted for an associative model of parallel computation known as ASC. The algorithm finds the best local alignment in O(m + n) time using m + 1 processing elements.