A study on string matching algorithms for bioinformatics sequences

Dizi arama, izinsiz giriş tespit sistemleri, dolandırıcılık tespiti, biyoinformatik sekanslarda örüntü arama gibi dizi eşleştirme algoritmaları bilgisayar biliminin temel alanları arasındadır. Kesin dizi eşleştirme algoritmaları tekli ve çoklu olmak üzere iki kısma ayrılır. Tekli kesin dizi eşleştirme algoritmaları, bir Τ metninde bir Р dizisinin tüm oluşumlarını bulmayı içerir. Bu algoritmalar, öncelikle metin arama ve hesaplamalı biyoloji gibi çeşitli alanlardaki uygulamaları nedeniyle bilgisayar bilimlerinde kapsamlı bir şekilde incelenmiştir. Çoklu kesin dizi eşleştirme algoritmaları, belirli bir Τ metninde |Р| dizi kümesinin elemanlarını bulmayı içerir. Kesin dizi eşleştirme algoritmalarının temel amacı, mümkün olan en kısa zaman çerçevesinde tüm dizi eşleşmelerini doğru bir şekilde bulmaktır. Bu nedenle literatürde var olan kesin dizi eşleştirme algoritmalarındaki eksiklikler tespit edilip daha verimli yeni yaklaşımlar geliştirilmelidir. Bu tez çalışmasında, DNA sekanslarına yönelik tekli ve çoklu kesin dizi eşleştirme algoritmaları geliştirilmiştir. Dizi eşleştirme işlemleri, DNA dizileri için zaman açısından verimli bir şekilde yapılmalıdır. Τ metninin hacmi arttıkça ve aranan dizilerin sayısı arttıkça toplam çalışma süresi artar. Bu arama işlemlerini en kısa sürede gerçekleştirmek için verimli algoritmalar seçilmelidir. Yapılan deneysel çalışmalar sonucu geliştirilen yaklaşımların literatürdeki diğer yaklaşımlara kıyasen performans metrikleri açısından daha başarılı sonuçlar elde ettiği gösterilmiştir.The string matching algorithms are among the essential fields in computer science, such as text search, intrusion detection systems, fraud detection, and pattern search in bioinformatics sequences. The exact string matching algorithms are divided into two parts as single and multiple.Single exact string matching algorithms involve finding all occurrences of a pattern Р in a text Τ. These algorithms have been extensively studied in computer science, primarily because of their applications in various fields such as text search and computational biology. Multiple string matching algorithms involve finding elements of the pattern set |Р| in a given input text Τ. The main goal of exact string matching algorithms is to find all pattern matches correctly within the shortest possible time frame. For this reason, the limitations of exact string matching algorithms in the literature should be determined and more efficient new approaches should be developed. In this thesis, single and multiple exact string matching algorithms for DNA sequences have been developed. String matching processes should be done in a time-efficient manner for DNA sequences. As the volume of the text Τ increases and the number of search patterns increases, the total runtime increases. Efficient algorithms should be selected to perform these search operations as soon as possible. As a result of the experimental studies, it has been shown that the developed approaches have achieved more successful results in terms of performance metrics compared to other approaches in the literature