Bit-parallel multiple pattern matching
作者： Tuan Tu Tran , Mathieu Giraud , Jean-Stéphane Varré
DOI: 10.1007/978-3-642-31500-8_30
关键词:
摘要: Text matching with errors is a regular task in computational biology. We present an extension of the bit-parallel Wu-Manber algorithm [16] to combine several searches for pattern into collection fixed-length words. further OpenCL parallelization redundant index on massively parallel multicore processors, within framework searching similarities seed-based heuristics. successfully implemented and ran our algorithms GPU CPU. Some speedups obtained are more than 60×.
springer.com
lifl.fr参考文章(23)
Ricardo A. Baeza-Yates, Gaston H. Gonnet, A New Approach to Text Searching (correction). Sigir Forum. ,vol. 23, pp. 7- ,(1989)
Wataru Matsubara, Hideo Bannai, Akira Ishino, Ayumi Shinohara, Kazunori Hirashima, Bit-parallel algorithms for computing all the runs in a string prague stringology conference. pp. 203- 213 ,(2009)
Albert Y. Zomaya, Mourad Elloumi, Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications ,(2011)
Dan Gusfield, Algorithms on Strings, Trees, and Sequences: Suffix Trees and Their Uses ,(1997) , 10.1017/CBO9780511574931
John L. Hennessy, David A. Patterson, Computer Architecture, Fifth Edition: A Quantitative Approach Computer Architecture, Fifth Edition: A Quantitative Approach 5th. pp. 880- 880 ,(2011)
Maria Charalambous, Pedro Trancoso, Alexandros Stamatakis, Initial Experiences Porting a Bioinformatics Application to a Graphics Processor Advances in Informatics. pp. 415- 425 ,(2005) , 10.1007/11573036_39
Mathieu Raffinot, Gonzalo Navarro, Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences ,(2002)
Daniel G. Brown, A Survey of Seeding for Sequence Alignment John Wiley & Sons, Inc.. pp. 117- 142 ,(2007) , 10.1002/9780470253441.CH6
John L. Hennessy, David A. Patterson, Computer Architecture: A Quantitative Approach ,(1989)
Nadia Pisanti, Mathieu Giraud, Pierre Peterlongo, Filters and Seeds Approaches for Fast Homology Searches in Large Datasets Algorithms in Computational Molecular Biology. pp. 299- 319 ,(2010) , 10.1002/9780470892107.CH15