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: 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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 336-345 |
| Number of pages | 10 |
| Journal | Proceedings of the International Conference on Application Specific Array Processors |
| State | Published - Dec 1 1994 |
| Event | Proceedings of the 1994 International Conference on Application Specific Array Processors - San Francisco, CA, USA Duration: Aug 22 1994 → Aug 24 1994 |
All Science Journal Classification (ASJC) codes
- Hardware and Architecture
- Computer Networks and Communications