A SIMD solution to the sequence comparison problem on the MGAP

TitleA SIMD solution to the sequence comparison problem on the MGAP
Publication TypeConference Papers
Year of Publication1994
AuthorsBorah M, Bajwa RS, Hannenhalli S, Irwin MJ
Conference NameInternational Conference on Application Specific Array Processors, 1994. Proceedings
Date Published1994/08/22/24
PublisherIEEE
ISBN Number0-8186-6517-3
KeywordsAT-optimal algorithm, Biological information theory, biology computing, biosequence comparison problem, computational complexity, Computer science, Costs, database size, Databases, DNA computing, dynamic programming, dynamic programming algorithms, fine-grained massively parallel processor array, Genetics, Heuristic algorithms, maximally similar sequence, MGAP parallel computer, Micro-Grain Array Processor, Military computing, molecular biology, molecular biophysics, Nearest neighbor searches, nearest-neighbor connections, Parallel algorithms, pipeline processing, pipelined SIMD solution, sequence alignment problem, sequences
Abstract

Molecular biologists frequently compare an unknown biosequence with a set of other known biosequences to find the sequence which is maximally similar, with the hope that what is true of one sequence, either physically or functionally, could be true of its analogue. Even though efficient dynamic programming algorithms exist for the problem, when the size of the database is large, the time required is quite long, even for moderate length sequences. In this paper, we present an efficient pipelined SIMD solution to the sequence alignment problem on the Micro-Grain Array Processor (MGAP), a fine-grained massively parallel array of processors with nearest-neighbor connections. The algorithm compares K sequences of length O(M) with the actual sequence of length N, in O(M+N+K) time with O(MN) processors, which is AT-optimal. The implementation on the MGAP computes at the rate of about 0.1 million comparisons per second for sequences of length 128
DOI10.1109/ASAP.1994.331791