Araştırma Makalesi
BibTex RIS Kaynak Göster

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

Yıl 2016, Cilt: 21 Sayı: 2, 269 - 282, 07.12.2016
https://doi.org/10.17482/uumfd.273970

Ö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.

Kaynakça

  • 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

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

Yıl 2016, Cilt: 21 Sayı: 2, 269 - 282, 07.12.2016
https://doi.org/10.17482/uumfd.273970

Ö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.



 

Kaynakça

  • 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
Toplam 24 adet kaynakça vardır.

Ayrıntılar

Konular Mühendislik
Bölüm Araştırma Makaleleri
Yazarlar

Gıyasettin Özcan

Yayımlanma Tarihi 7 Aralık 2016
Gönderilme Tarihi 5 Nisan 2016
Kabul Tarihi 3 Kasım 2016
Yayımlandığı Sayı Yıl 2016 Cilt: 21 Sayı: 2

Kaynak Göster

APA Özcan, G. (2016). P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI. Uludağ Üniversitesi Mühendislik Fakültesi Dergisi, 21(2), 269-282. https://doi.org/10.17482/uumfd.273970
AMA Özcan G. P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI. UUJFE. Kasım 2016;21(2):269-282. doi:10.17482/uumfd.273970
Chicago Özcan, Gıyasettin. “P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI”. Uludağ Üniversitesi Mühendislik Fakültesi Dergisi 21, sy. 2 (Kasım 2016): 269-82. https://doi.org/10.17482/uumfd.273970.
EndNote Özcan G (01 Kasım 2016) P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI. Uludağ Üniversitesi Mühendislik Fakültesi Dergisi 21 2 269–282.
IEEE G. Özcan, “P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI”, UUJFE, c. 21, sy. 2, ss. 269–282, 2016, doi: 10.17482/uumfd.273970.
ISNAD Özcan, Gıyasettin. “P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI”. Uludağ Üniversitesi Mühendislik Fakültesi Dergisi 21/2 (Kasım 2016), 269-282. https://doi.org/10.17482/uumfd.273970.
JAMA Özcan G. P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI. UUJFE. 2016;21:269–282.
MLA Özcan, Gıyasettin. “P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI”. Uludağ Üniversitesi Mühendislik Fakültesi Dergisi, c. 21, sy. 2, 2016, ss. 269-82, doi:10.17482/uumfd.273970.
Vancouver Özcan G. P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASI. UUJFE. 2016;21(2):269-82.

DUYURU:

30.03.2021- Nisan 2021 (26/1) sayımızdan itibaren TR-Dizin yeni kuralları gereği, dergimizde basılacak makalelerde, ilk gönderim aşamasında Telif Hakkı Formu yanısıra, Çıkar Çatışması Bildirim Formu ve Yazar Katkısı Bildirim Formu da tüm yazarlarca imzalanarak gönderilmelidir. Yayınlanacak makalelerde de makale metni içinde "Çıkar Çatışması" ve "Yazar Katkısı" bölümleri yer alacaktır. İlk gönderim aşamasında doldurulması gereken yeni formlara "Yazım Kuralları" ve "Makale Gönderim Süreci" sayfalarımızdan ulaşılabilir. (Değerlendirme süreci bu tarihten önce tamamlanıp basımı bekleyen makalelerin yanısıra değerlendirme süreci devam eden makaleler için, yazarlar tarafından ilgili formlar doldurularak sisteme yüklenmelidir).  Makale şablonları da, bu değişiklik doğrultusunda güncellenmiştir. Tüm yazarlarımıza önemle duyurulur.

Bursa Uludağ Üniversitesi, Mühendislik Fakültesi Dekanlığı, Görükle Kampüsü, Nilüfer, 16059 Bursa. Tel: (224) 294 1907, Faks: (224) 294 1903, e-posta: mmfd@uludag.edu.tr