Detection of P53 consensus sequence: A novel string matching with classes algorithm

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.

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.