TY - Generic T1 - A SIMD solution to the sequence comparison problem on the MGAP T2 - International Conference on Application Specific Array Processors, 1994. Proceedings Y1 - 1994 A1 - Borah, M. A1 - Bajwa, R. S. A1 - Sridhar Hannenhalli A1 - Irwin, M. J. KW - AT-optimal algorithm KW - Biological information theory KW - biology computing KW - biosequence comparison problem KW - computational complexity KW - Computer science KW - Costs KW - database size KW - Databases KW - DNA computing KW - dynamic programming KW - dynamic programming algorithms KW - fine-grained massively parallel processor array KW - Genetics KW - Heuristic algorithms KW - maximally similar sequence KW - MGAP parallel computer KW - Micro-Grain Array Processor KW - Military computing KW - molecular biology KW - molecular biophysics KW - Nearest neighbor searches KW - nearest-neighbor connections KW - Parallel algorithms KW - pipeline processing KW - pipelined SIMD solution KW - sequence alignment problem KW - sequences AB - 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 JA - International Conference on Application Specific Array Processors, 1994. Proceedings PB - IEEE SN - 0-8186-6517-3 ER -