Parallelising the Computation of Minimal Absent Words
Parallelising the Computation of Minimal Absent Words
复制标题
最小缺失词的并行计算
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Pissis
中科院分区：
文献类型：
--
作者：
Carl Barton;Alice Héliou;L. Mouchard;S. Pissis
长度为n的单词不存在的单词是y中没有出现的单词。如果其所有适当的因素发生在y中，这是一个最小的缺席单词。在生命的所有领域的生物基因组中，已经计算出最小的缺乏单词。他们的计算还提供了一种快速替代方法，用于测量序列比较。存在（Mathcal {O}（n）） - 时间和（Mathcal {O}（n）） - 用于计算基于固定尺寸字母上所有最小单词的空间算法，基于订阅式阵列的构造（Barton等人） 。，2014年）。作者还提供了该算法的实现，目前是最快的。在本文中，我们提供了一个新的（Mathcal {O}（n）） - 时间和（Mathcal {O}（n）） - 用于计算所有最小缺失单词的空格算法；它具有理想的属性，鉴于手头的索引数据结构，可以并行执行最小缺乏单词的计算。实验结果表明，与最先进的方法相比，该算法的多处理实现可以将整体计算加速超过两个。通过排除索引数据结构构建时间，我们表明实施实现了近乎最佳的加速。
An absent word of a word y of length n is a word that does not occur in y. It is a minimal absent word if all its proper factors occur in y. Minimal absent words have been computed in genomes of organisms from all domains of life; their computation also provides a fast alternative for measuring approximation in sequence comparison. There exists an (mathcal {O}(n))-time and (mathcal {O}(n))-space algorithm for computing all minimal absent words on a fixed-sized alphabet based on the construction of suffix array (Barton et al., 2014). An implementation of this algorithm was also provided by the authors and is currently the fastest available. In this article, we present a new (mathcal {O}(n))-time and (mathcal {O}(n))-space algorithm for computing all minimal absent words; it has the desirable property that, given the indexing data structure at hand, the computation of minimal absent words can be executed in parallel. Experimental results show that a multiprocessing implementation of this algorithm can accelerate the overall computation by more than a factor of two compared to state-of-the-art approaches. By excluding the indexing data structure construction time, we show that the implementation achieves near-optimal speed-ups.