Detection of P53 Consensus Sequence: A Novel String Matching With Classes Algorithm

Öz

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.

Anahtar Kelimeler

• Computer Engineering,Computational Biology,Text Processing,Consensus Sequences,Bitwise Matching,Hardware Counters

P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI

Öz

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.

 

Anahtar Kelimeler

• Bilgisayar Mühendisliği,Hesaplamalı Biyoloji,Metin İşleme,Konsensüs Dizileri,Bitsel Eşleme,Donanım Sayaçları

Kaynakça

1. 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
2. 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
3. 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
4. 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
5. 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
6. El-Deiry W. (1998) Regulation of p53 downstream genes, Semin Cancer Biololgy, 8 :345-357.
7. 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
8. Faro, S. and Lecroq, T. (2010) The Exact String Matching Problem: A Comprehensive Experimental Evaluation, doi: 10.1145/2431211.2431212

9. 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
10. Horspool, R. N. (1980) Practical fast searching in strings, Software – Practice & Experience, New Jersey, Volume 10 Number 6.
11. http://www.boost.org, Erişim Tarihi: 01.01.2013, Konu:C++ Boost Libraries :
12. http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html. Erişim Tarihi: 1.1.2011, Konu: Intel Manual
13. 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ı
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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
20. 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
21. Ö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
22. Patterson, D., Hennessy, J., Arpaci-Dusseau, A. (2007). Computer architecture: a quantitative approach. Morgan Kaufmann,
23. 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
24. 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