@article{M28477BE3,
title = "Parallel Algorithms for Finding Consensus of Circular Strings",
journal = "Journal of KIISE, JOK",
year = "2015",
issn = "2383-630X",
doi = "",
author = "Dong Hee Kim,Jeong Seop Sim",
keywords = "CUDA,consensus,multiple string alignment,Hamming distance,circular strings,Fast Fourier Transform",
abstract = "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."
}