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 -
TY - Generic
T1 - A distributed algorithm for ear decomposition
T2 - Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
Y1 - 1993
A1 - Sridhar Hannenhalli
A1 - Perumalla, K.
A1 - Chandrasekharan, N.
A1 - Sridhar, R.
KW - Asynchronous communication
KW - asynchronous communication network
KW - Automata
KW - Communication networks
KW - computational complexity
KW - Computer networks
KW - Computer science
KW - decomposition graph
KW - distributed algorithm
KW - distributed algorithms
KW - Distributed computing
KW - Ear
KW - ear decomposition
KW - graph theory
KW - message-optimal
KW - network decomposition
KW - sorting
KW - Testing
KW - time-optimal
AB - A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition
JA - Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
PB - IEEE
SN - 0-8186-4212-2
ER -
TY - Generic
T1 - Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs
T2 - Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92
Y1 - 1992
A1 - Chandrasekharan, N.
A1 - Sridhar Hannenhalli
KW - chromatic polynomials
KW - computational complexity
KW - Computer science
KW - graph colouring
KW - graph theory
KW - matching polynomial
KW - Polynomials
KW - series-parallel graphs
KW - Terminology
KW - Tree data structures
KW - Tree graphs
AB - The authors present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Their algorithm for computing the matching polynomial generalizes an existing result from Lovasz, Plummer (1986) and the chromatic polynomial algorithm improves the result given by Hunt, Ravi, Stearn (1988) from O(n4) time
JA - Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92
PB - IEEE
SN - 0-8186-2812-X
ER -