Parallel Implementation of Smith Waterman Sequence Alignment Algorithm

Abstract

Local sequence alignment is widely used to discover structural and hence, functional similarities between biological sequences. Sequence database alignment is among the most important and challenging tasks in bioinformatics. This paper presents a parallel algorithm that finds all occurrences of a pattern string in a subject string in O(log n) time, where n is the length of the subject string. The number of processors employed is of the order of the product of the two string lengths. It also presents advanced computer architectures that utilize parallelism via multiple processing units. While parallel computing, in the form of internally linked processors, was the main form of parallelism, advances in computer networks has created a new type of parallelism in the form of networked autonomous computers. . The right choice of sequence alignment algorithm is that of Smith- Waterman. To get high quality results in a short time is to use parallel processing.