Finding All Maximal Contiguous Subsequences of a Sequence of Numbers in O(1) Communication Rounds
C. E. R. Alves, Edson N. Cáceres, Siang Wun Song · IEEE Transactions on Parallel and Distributed Systems · 2012
Given a sequence $(A)$ of real numbers, we wish to find a list of all nonoverlapping contiguous subsequences of $(A)$ that are maximal. A maximal subsequence $(M)$ of $(A)$ has the property that no proper subsequence of $(M)$ has a greater sum of values. Furthermore, $(M)$ may not be contained properly within any subsequence of $(A)$ with this property. This problem has several applications in Computational Biology and can be solved sequentially in linear time. We present a BSP/CGM algorithm that solves this problem using $(p)$ processors in $(O (\vert A\vert/p))$ time and $(O (\vert A\vert/p))$ space per processor. The algorithm uses a constant number of communication rounds of size at most $(O (\vert A\vert/p))$. Thus, the algorithm achieves linear speedup and is highly scalable. To our knowledge, there are no previous known parallel BSP/CGM algorithms to solve this problem.