A Parallel Algorithm for Finding All Pairs κ-Mismatch Maximal Common Substrings
A Parallel Algorithm for Finding All Pairs κ-Mismatch Maximal Common Substrings
复制标题
查找所有κ-失配最大公共子串对的并行算法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Aluru
中科院分区：
文献类型：
--
作者：
Sriram P. Chockalingam;Sharma V. Thankachan;S. Aluru
给出了一个有效的并行算法来解决以下问题：给定一个输入集合D，其n个序列的总长度为N，长度阈值为f，失配阈值为κ，在D中的所有字符串对上报告所有长度至少为f的κ-失配最大公共子串.这个问题的动机是计算生物学中的聚类和组装应用，其中D是数百万短DNA序列的集合。测序错误和这些数据集的巨大规模，需要高效的并行近似序列匹配算法。我们提出了一种新的分布式内存并行算法，解决了这个近似的序列匹配问题在O（（N/plog N + occ）logkN）的预期时间，只需要O（logk+1 N）预期轮的全球通信，在一些现实的假设下，其中p是处理器的数量和occ是输出大小。据我们所知，这是第一个可证明的次二次时间算法来解决这个问题。我们证明了我们的算法使用大型高通量测序数据集的性能和可扩展性。
We present an efficient parallel algorithm for the following problem: Given an input collection D of n sequences of total length N, a length threshold f and a mismatch threshold κ, report all κ-mismatch maximal common substrings of length at least f over all pairs of strings in D. This problem is motivated by clustering and assembly applications in computational biology, where D is a collection of millions of short DNA sequences. Sequencing errors and massive size of these datasets necessitate efficient parallel approximate sequence matching algorithms. We present a novel distributed memory parallel algorithm that solves this approximate sequence matching problem in O ((N/p log N + occ)logk N) expected time and takes only O(logk+1 N) expected rounds of global communications, under some realistic assumptions, where p is the number of processors and occ is the output size. To our knowledge, this is the first provably sub-quadratic time algorithm for solving this problem. We demonstrate the performance and scalability of our algorithm using large high throughput sequencing data sets.