TY - CONF
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 - Hannenhalli, Sridhar
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
M3 - 10.1109/ASAP.1994.331791
ER -