A Practical and Efficient Algorithm for the k-mismatch Shortest Unique Substring Finding Problem
A Practical and Efficient Algorithm for the k-mismatch Shortest Unique Substring Finding Problem
复制标题
一种实用高效的k失配最短唯一子串查找问题算法
DOI：
10.1145/3233547.3233564
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Xu, Bojian
中科院分区：
文献类型：
--
作者：
Allen, Daniel R.;Thankachan, Sharma V.;Xu, Bojian
本文回顾了k-失配最短唯一子串查找问题，并证明了最近在解决k-失配平均公共子串问题的背景下提出的一种技术可以适应并结合现有解决方案的一部分，从而产生一种新的算法，该算法的预期时间复杂度为，同时保持实际的空间复杂度为，其中n为字符串长度。当这是困难的情况时，我们的新建议显著提高了k-失配最短唯一子串查找的先验最佳方法的任意情况时间复杂度。实验研究表明，当k相对于n较小时，我们的新算法是切实可行的，并且与先前最佳解决方案的实现相比，处理时间有了显着改善。例如，我们的方法在0.18秒内处理200KB样本DNA序列，而使用先前最佳解决方案则需要174.37秒。此外，可以观察到，采用的技术的很大一部分可以使用两种不同的简单并发模型并行执行，从而进一步显著提高实际性能。例如，当使用8核时，并行实现在处理10MB样本DNA序列时都比串行实现的处理时间短。在一个拥有数千千兆字节RAM的实例随时可以通过云基础设施提供商使用的时代，为了显著改善处理时间而牺牲额外的内存使用可能是许多用户所希望和需要的。例如，之前最好的解决方案可能需要花费数年时间才能完成200MB的DNA样本，而这个新提议，使用24核，可以在几秒钟内完成处理这个大小的样本，峰值内存使用量为46GB，这对于许多用户来说在云上既容易获得又负担得起。期望这种新的高效实用的k-失配最短唯一子串查找算法将被证明对计算生物学等领域中使用长序列测量的人有用。
This paper revisits the k-mismatch shortest unique substring finding problem and demonstrates that a technique recently presented in the context of solving the k-mismatch average common substring problem can be adapted and combined with parts of the existing solution, resulting in a new algorithm which has expected time complexity of, while maintaining a practical space complexity at, where n is the string length. When, which is the hard case, our new proposal significantly improves the any-casetime complexity of the prior best method for k-mismatch shortest unique substring finding. Experimental study shows that our new algorithm is practical to implement and demonstrates significant improvements in processing time compared to the prior best solution's implementation when k is small relative to n. For example, our method processes a 200KB sample DNA sequence within just 0.18 seconds compared to 174.37 seconds with the prior best solution. Further, it is observed that significant portions of the adapted technique can be executed in parallel, using two different simple concurrency models, resulting in further significant practical performance improvement. As an example, when using 8 cores, the parallel implementations both achieved processing times that are less thanthat of the serial implementation, when processing a 10MB sample DNA sequence with. In an age where instances with thousands of gigabytes of RAM are readily available for use through Cloud infrastructure providers, it is likely that the trade-off of additional memory usage for significantly improved processing times will be desirable and needed by many users. For example, the best prior solution may spend years to finish a DNA sample of 200MB for any, while this new proposal, using 24 cores, can finish processing a sample of this size withinseconds with a peak memory usage of 46GB, which is both easily available and affordable on Cloud for many users. It is expected that this new efficient and practical algorithm for k-mismatch shortest unique substring finding will prove useful to those using the measure on long sequences in fields such as computational biology.
登录
查看更多内容
RMQ 问题的理论和实践改进及其在 LCA 和 LCE 中的应用
DOI：
10.1007/11780441_5
发表时间：
2006
期刊：
Journal of computational biology : a journal of computational molecular cell biology
影响因子：
--
作者：
J. Fischer;Volker Heun
通讯作者：
Volker Heun
一种简单但时间最优的线性空间算法，用于最短唯一子串查询
DOI：
10.1016/j.tcs.2014.11.004
发表时间：
2015
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Atalay Mert Ileri;M. Külekci;Bojian Xu
通讯作者：
Bojian Xu
k-失配平均公共子串问题的一种可证明有效的算法
DOI：
--
发表时间：
2016
期刊：
J. Comput. Biol.
影响因子：
--
作者：
Sharma V. Thankachan;A. Apostolico;S. Aluru
通讯作者：
S. Aluru
关于后缀树高度的注意事项
DOI：
10.1137/0221005
发表时间：
1992
期刊：
SIAM J. Comput.
影响因子：
--
作者：
L. Devroye;W. Szpankowski;Bonita Rais
通讯作者：
Bonita Rais
用于精确和近似最短唯一子串问题的就地算法
DOI：
10.1016/j.tcs.2017.05.032
发表时间：
2017
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
W. Hon;Sharma V. Thankachan;Bojian Xu
通讯作者：
Bojian Xu