TY  - JOUR
T1  - Parallel Algorithms for Finding Consensus of Circular Strings
AU  - Kim, Dong Hee 
AU  - Sim, Jeong Seop 
JO  - Journal of KIISE, JOK
PY  - 2015
DA  - 2015/1/14
DO  - 
KW  - CUDA
KW  - consensus
KW  - multiple string alignment
KW  - Hamming distance
KW  - circular strings
KW  - Fast Fourier Transform
AB  - 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.