Search results for "Parallel algorithm"
showing 2 items of 32 documents
Parallel distance transforms on pyramid machines: Theory and implementation
1990
Abstract A distance transform of a binary image is an array each of whose elements gives the distance from the corresponding pixel to the closest ‘1’ in the binary image. Distance transforms have uses in image matching and shape analysis, among other applications. We present a parallel algorithm for weighted distance transforms that runs particularly efficiently on hierarchical cellular-logic machines, a subclass of the architectures known as pyramid machines. The algorithm computes the 3–4 distance transform; however it can be readily adapted to the city-block (‘Manhattan’) and chessboard distance measures. The algorithm runs in O(M) time, for an M × M image. Since it avoids using arithmet…
A fast algorithm for the exhaustive analysis of 12-nucleotide-long DNA sequences. Applications to human genomics
2004
We have developed a new algorithm that allows the exhaustive determination of words of up to 12 nucleotides in DNA sequences. It is fast enough as to be used at a genomic scale running on a standard personal computer. As an example, we apply the algorithm to compare the number of all 12-nucleotide long words in human chromosomes 21 and 22, each of them more than 33 million nucleotides long. Sequences that are chromosome specific are detected in less than 2 minutes, being analyzed any pair of chromosomes at a rate of 45 millions of nucleotides (45 Mb) per minute. The size of the words is long enough as to allow further analyses of all significant sequences using conventional database searche…