Multi-core parallel substring matching algorithm using BWT

被引：0

作者：

Wang J.-Y. ^{[1
]}

Wang B. ^{[1
]}

Li X.-H. ^{[1
]}

Yang X.-C. ^{[1
]}

机构：

[1] School of Computer Science & Engineering, Northeastern University, Shenyang

来源：

Dongbei Daxue Xuebao/Journal of Northeastern University | 2016年 / 37卷 / 05期

关键词：

BWT(Burrows-Wheeler transform); Exact matching; Full text index; Multi-core; Parallel;

D O I：

10.3969/j.issn.1005-3026.2016.05.004

中图分类号：

TN11 [电子管];

学科分类号：

摘要：

In order to solve the problem that P-BWT (Burrows-Wheeler transform) could only support short queries, and work on a uniprocessor, a multi-core parallel exact matching algorithm was proposed which any query length could be supposed. Firstly, the search process on P-BWT index was modified. When a query spans multiple data fragments, it first searches on the last segment, then verifies on the other segments. Further, a parallel algorithm was proposed to reduce the iterations in the search and verify process. Finally, the experimental study show that using the proposed algorithm, the substring matching task could be accomplished efficiently in parallel manner. © 2016, Editorial Department of Journal of Northeastern University. All right reserved.

引用

页码：624 / 628

页数：4

共 11 条

[1]

Navarro G., Makinen V., Compressed full-text indexes, ACM Computing Surveys (CSUR), 39, 1, pp. 2-50, (2007)

[2]

Yang X., Wang B., Li C., Et al., Efficient direct search on compressed genomic data, IEEE 29th International Conference on Data Engineering (ICDE), pp. 961-972, (2013)

[3]

Li H., Durbin R., Fast and accurate short read alignment with Burrows-Wheeler transform, Bioinformatics, 25, 14, pp. 1754-1760, (2009)

[4]

Li R., Yu C., Li Y., Et al., SOAP2:an improved ultrafast tool for short read alignment, Bioinformatics, 25, 15, pp. 1966-1967, (2009)

[5]

Wandelt S., Deng D., Gerdjikov S., Et al., State-of-the-art in string similarity search and join, ACM SIGMOD Record, 43, 1, pp. 64-76, (2014)

[6]

Jiang Y., Li G., Feng J., Et al., String similarity joins:an experimental evaluation, Proceedings of the VLDB Endowment, 7, 8, pp. 625-636, (2014)

[7]

Ferragina P., Manzini G., Opportunistic data structures with applications, Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 390-398, (2000)

[8]

Manzini G., Ferragina P., Engineering a lightweight suffix array construction algorithm, Algorithmica, 40, 1, pp. 33-50, (2004)

[9]

Crauser A., Ferragina P., A theoretical and experimental study on the construction of suffix arrays in external memory, Algorithmica, 32, 1, pp. 1-35, (2002)

[10]

Dementiev R., Karkkainen J., Mehnert J., Et al., Better external memory suffix array construction, Journal of Experimental Algorithmics, 12, 1, pp. 3-27, (2008)

← 1 2 →