Parallel Algorithms for Finding Consensus of Circular Strings

Dong Hee Kim, Jeong Seop Sim

http://doi.org/

The consensus problem is finding a representative string, called a consensus, of a given set S of k strings. Circular strings are different from linear strings in that the last symbol precedes the first symbol. Given a set S of circular strings of length n over an alphabet ∑ , we first present an O(｜∑｜nlogn) time parallel algorithm for finding a consensus of S minimizing both radius and distance sum when k=3 using O(n) threads. Then we present an O(｜∑｜n²logn) time parallel algorithm for finding a consensus of S minimizing distance sum when k=4 using O(n) threads. Finally, we compare execution times of our algorithms implemented using CUDA with corresponding sequential algorithms.