Abstract
We present a novel fast string matching
technique for special DNA pattern forms and compare performance of recent CPU
architectures on the matching problem. In particular, we consider consensus P53
DNA-binding consensus sequence, which has an important contribution for cancer
treatment. Based on biological findings, consensus P53 pattern may emerge in
various sequence forms and its length is not deterministic. Therefore, classic
string matching algorithms are not able to solve the problem. For efficient
solution, we consider bitwise string matching algorithms with classes and
present a novel search technique which is based on 64-bit packed variables. In
order to prevent obstacles based on variable length of the pattern, we search right
and left side indexes of P53 and reduce search space. For experimental
analysis, we make use of mus musculus DNA sequences with approximately 2.3
billion nucleotides. We compare algorithm performance on three processors with
distinct CPU architecture. Test results show that our search technique introduces
at least 20% efficiency during P53 pattern search in each architecture
platform. Due to its structure, the algorithm also introduces an efficient
solution to similar string matching with class problems.
Keywords
Computer Engineering Computational Biology Text Processing Consensus Sequences Bitwise Matching Hardware Counters
References
- Appel, W. and George, L. (2000) Optimal spilling for CISC machines with few registers, ACM SIGPLAN Notices, Vol 36 No 5, 243-253, doi: 10.1145/378795.378854
- Baeza-Yates, R. and Gonnet, G. H., (1992) A new approach to text searching, Communications of the ACM, 35(10) , 74–82, doi: 10.1145/135239.135243
- Boyer, R.S. and Moore, J.S. (1977 ) A Fast String Searching Algorithm, Communications of the ACM, 20, 10, 762-772, doi: 10.1145/359842.359859
- Browne, S., Dongarra, J., Garner, N., Ho, G. and Mucci, P. (2000) A Portable Programming Interface for Performance Evaluation on Modern Processors, The International Journal of High Performance Computing Applications, 14:3, 189-204, doi:10.1177/109434200001400303
- Durian, B., Holub, J., Peltola, H., and Tarhio, J. (2009) Tuning BNDM with q-grams, Proceedings of the Workshop on Algorithm Engineering and Experiments ALENEX. 29–37, doi: 10.1137/1.9781611972894.3
- El-Deiry W. (1998) Regulation of p53 downstream genes, Semin Cancer Biololgy, 8 :345-357.
- Fan, H., Yao, N., and Ma, H. (2009) Fast variants of the backward-oracle-marching algorithm, Proceedings of the Fourth International Conference on Internet Computing for Science and Engineering, IEEE Computer Society, 56–59
- Faro, S. and Lecroq, T. (2010) The Exact String Matching Problem: A Comprehensive Experimental Evaluation, doi: 10.1145/2431211.2431212
- Fuyao, Z. and Qingwei, L. (2009) A string matching algorithm based on efficient hash function, Information Engineering and Computer Science – ICIECS, doi: 10.1109/ICIECS.2009.5363191
- Horspool, R. N. (1980) Practical fast searching in strings, Software – Practice & Experience, New Jersey, Volume 10 Number 6.
- http://www.boost.org, Erişim Tarihi: 01.01.2013, Konu:C++ Boost Libraries :
- http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html. Erişim Tarihi: 1.1.2011, Konu: Intel Manual
- http://www.ncbi.nlm.nih.gov/pubmedhealth/. Erişim Tatihi: 1.1.2014, Konu: PubMed Health Bethesda (MD): National Library of Medicine, mus musculus DNA sekansları
- Karp, R. M. and Rabin, M. O. (1987) Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, New Jersey Volume 31 Issue 2, doi: 10.1147/rd.312.0249
- Kern, S. E., Kinzler, K. W., Bruskin, A., Jarosz, D., Friedman, P., Prives, C., and Vogelstein B. (1991) Identification of p53 as a sequence-specific DNA-binding protein. Science. 252(5013):1708–11, doi: 10.1126/science.2047879
- Kim, S. (1999) A new string-pattern matching algorithm using partitioning and hashing efficiently, Journal of Experimental Algorithmics (JEA), JEA Homepage archive Volume 4, Article No. 2, doi: 10.1145/347792.347803
- Külekci, O. (2012) On enumeration of DNA sequences, Proceedings of ACM Conference on Bioinformatics, Computational Biology, and Biomedicine, Orlando, doi: 10.1145/2382936.2382993
- Külekci, O. (2008) A method to overcome computer word size limitation in bit-parallel pattern matching, S.-H. Hong, H. Nagamochi, and T. Fukunaga, editors, Proceedings of the 19th International Symposium on Algorithms and Computation, ISAAC, Lecture Notes in Computer Science, Springer-Verlag, Berlin volume 5369, 496–506, doi: 10.1007/978-3-540-92182-0_45
- Knuth, D., Morris, J. H. and Pratt, V. (1977) Fast pattern matching in strings, SIAM Journal on Computing, 6 (2), 323–350, 10.1137/0206024
- Navarro, G., and Raffinot, M. (2000) Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM Journal of Experimental Algorithmics, Volume 5, New York, doi: 10.1145/351827.384246
- Özcan, G., and Ünsal, O. S. (2015) Fast bitwise pattern matching algorithm for DNA sequences on modern hardware, Turk J Elec Eng & Comp Sci, Vol 23 (2015), pp.1405-1417 doi: 10.3906/elk-1304-165
- Patterson, D., Hennessy, J., Arpaci-Dusseau, A. (2007). Computer architecture: a quantitative approach. Morgan Kaufmann,
- Vintan, L. N. "Towards a High Performance Neural Branch Predictor (1999) Proceedings of the Int'l J. Conf. on Neural Networks, doi: 10.1109/IJCNN.1999.831066
- Sunday, D. M. (1990) A Very Fast Substring Search Algorithm. Communications of the ACM, New York. , 33, 8, 132-142, doi: 10.1145/79173.79184
Abstract
Bu
çalışmada özel DNA örüntüleri için yeni ve hızlı bir sekans eşleştirme tekniği
sunulmakta ve yakın geçmişte üretilen CPU mimarileri üzerinde deneysel karşılaştırmalar
yapılmaktadır. Bu çalışmada, bilhassa kanser tedavisinde, önemli bir yere sahip
olan P53 DNA-bağlayan konsensüs sekansı göz önüne alınmıştır. Biyolojik
kazanımlara göre P53 örüntüsü farklı sekans formlarında karşımıza çıkabilmekte
ve sekans uzunluğu değişebilmektedir. Bu nedenle P53 sekansının klasik sekans
eşleştirme algoritmaları ile çözümü mümkün olamamaktadır. Bu çalışmada verimli
çözüm yöntemi sunmak amacıyla, sınıf özellikli bit-tabanlı sekans eşleştirme
algoritması göz önüne alınmıştır. Hedef doğrultusunda, 64-bit paketlenmiş
değişken kullanarak yeni bir arama ve eşleştirme algoritması önerilmiştir. Örüntü
sekansının değişken uzunluk gösterebilmesi nedeniyle karşılaşılması muhtemel
engelleri aşmak için ise veri tabanında P53 sekansının özel kısımlarına dair
aramalar yapılmıştır. Deneysel analiz için yaklaşık 2.3 milyar nükleotidden
oluşan mus musculus DNA sekansı seçilmiştir. Karşılaştırılan algoritmalar üç
farklı bilgisayar mimarisinde test edilmiştir. Deneysel sonuçlar, geliştirdiğimiz
algoritmanın P53 sekans arama konusunda tüm mimari platformlarında en iyi
verimliliği sağladığını göstermektedir. Yapısı
gereği bu algoritma, benzer sekans eşleştirme problemlerinin çözümünde de
verimli olanaklar sunmaktadır.
Keywords
Bilgisayar Mühendisliği Hesaplamalı Biyoloji Metin İşleme Konsensüs Dizileri Bitsel Eşleme Donanım Sayaçları
References
- Appel, W. and George, L. (2000) Optimal spilling for CISC machines with few registers, ACM SIGPLAN Notices, Vol 36 No 5, 243-253, doi: 10.1145/378795.378854
- Baeza-Yates, R. and Gonnet, G. H., (1992) A new approach to text searching, Communications of the ACM, 35(10) , 74–82, doi: 10.1145/135239.135243
- Boyer, R.S. and Moore, J.S. (1977 ) A Fast String Searching Algorithm, Communications of the ACM, 20, 10, 762-772, doi: 10.1145/359842.359859
- Browne, S., Dongarra, J., Garner, N., Ho, G. and Mucci, P. (2000) A Portable Programming Interface for Performance Evaluation on Modern Processors, The International Journal of High Performance Computing Applications, 14:3, 189-204, doi:10.1177/109434200001400303
- Durian, B., Holub, J., Peltola, H., and Tarhio, J. (2009) Tuning BNDM with q-grams, Proceedings of the Workshop on Algorithm Engineering and Experiments ALENEX. 29–37, doi: 10.1137/1.9781611972894.3
- El-Deiry W. (1998) Regulation of p53 downstream genes, Semin Cancer Biololgy, 8 :345-357.
- Fan, H., Yao, N., and Ma, H. (2009) Fast variants of the backward-oracle-marching algorithm, Proceedings of the Fourth International Conference on Internet Computing for Science and Engineering, IEEE Computer Society, 56–59
- Faro, S. and Lecroq, T. (2010) The Exact String Matching Problem: A Comprehensive Experimental Evaluation, doi: 10.1145/2431211.2431212
- Fuyao, Z. and Qingwei, L. (2009) A string matching algorithm based on efficient hash function, Information Engineering and Computer Science – ICIECS, doi: 10.1109/ICIECS.2009.5363191
- Horspool, R. N. (1980) Practical fast searching in strings, Software – Practice & Experience, New Jersey, Volume 10 Number 6.
- http://www.boost.org, Erişim Tarihi: 01.01.2013, Konu:C++ Boost Libraries :
- http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html. Erişim Tarihi: 1.1.2011, Konu: Intel Manual
- http://www.ncbi.nlm.nih.gov/pubmedhealth/. Erişim Tatihi: 1.1.2014, Konu: PubMed Health Bethesda (MD): National Library of Medicine, mus musculus DNA sekansları
- Karp, R. M. and Rabin, M. O. (1987) Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, New Jersey Volume 31 Issue 2, doi: 10.1147/rd.312.0249
- Kern, S. E., Kinzler, K. W., Bruskin, A., Jarosz, D., Friedman, P., Prives, C., and Vogelstein B. (1991) Identification of p53 as a sequence-specific DNA-binding protein. Science. 252(5013):1708–11, doi: 10.1126/science.2047879
- Kim, S. (1999) A new string-pattern matching algorithm using partitioning and hashing efficiently, Journal of Experimental Algorithmics (JEA), JEA Homepage archive Volume 4, Article No. 2, doi: 10.1145/347792.347803
- Külekci, O. (2012) On enumeration of DNA sequences, Proceedings of ACM Conference on Bioinformatics, Computational Biology, and Biomedicine, Orlando, doi: 10.1145/2382936.2382993
- Külekci, O. (2008) A method to overcome computer word size limitation in bit-parallel pattern matching, S.-H. Hong, H. Nagamochi, and T. Fukunaga, editors, Proceedings of the 19th International Symposium on Algorithms and Computation, ISAAC, Lecture Notes in Computer Science, Springer-Verlag, Berlin volume 5369, 496–506, doi: 10.1007/978-3-540-92182-0_45
- Knuth, D., Morris, J. H. and Pratt, V. (1977) Fast pattern matching in strings, SIAM Journal on Computing, 6 (2), 323–350, 10.1137/0206024
- Navarro, G., and Raffinot, M. (2000) Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM Journal of Experimental Algorithmics, Volume 5, New York, doi: 10.1145/351827.384246
- Özcan, G., and Ünsal, O. S. (2015) Fast bitwise pattern matching algorithm for DNA sequences on modern hardware, Turk J Elec Eng & Comp Sci, Vol 23 (2015), pp.1405-1417 doi: 10.3906/elk-1304-165
- Patterson, D., Hennessy, J., Arpaci-Dusseau, A. (2007). Computer architecture: a quantitative approach. Morgan Kaufmann,
- Vintan, L. N. "Towards a High Performance Neural Branch Predictor (1999) Proceedings of the Int'l J. Conf. on Neural Networks, doi: 10.1109/IJCNN.1999.831066
- Sunday, D. M. (1990) A Very Fast Substring Search Algorithm. Communications of the ACM, New York. , 33, 8, 132-142, doi: 10.1145/79173.79184
Details
| Subjects | Engineering |
|---|---|
| Journal Section | Research Articles |
| Authors | |
| Publication Date | December 7, 2016 |
| Submission Date | April 5, 2016 |
| Acceptance Date | November 3, 2016 |
| Published in Issue | Year 2016 Volume: 21 Issue: 2 |
Cite
Cited By
BAŞLICA BİYOİNFORMATİK ALGORİTMALARI İÇİN WEB ARA YÜZÜ VE YENİ OTOMAT TABANLI YAKLAŞIK DESEN EŞLEŞTİRME YAKLAŞIMI
Uludağ University Journal of The Faculty of Engineering
Burak KOCA
https://doi.org/10.17482/uumfd.425094
Announcements:
30.03.2021-Beginning with our April 2021 (26/1) issue, in accordance with the new criteria of TR-Dizin, the Declaration of Conflict of Interest and the Declaration of Author Contribution forms fulfilled and signed by all authors are required as well as the Copyright form during the initial submission of the manuscript. Furthermore two new sections, i.e. ‘Conflict of Interest’ and ‘Author Contribution’, should be added to the manuscript. Links of those forms that should be submitted with the initial manuscript can be found in our 'Author Guidelines' and 'Submission Procedure' pages. The manuscript template is also updated. For articles reviewed and accepted for publication in our 2021 and ongoing issues and for articles currently under review process, those forms should also be fulfilled, signed and uploaded to the system by authors.