TY  - JOUR
T1  - A New Automata Based Approximate String Matching Approach and Web Interface for Bioinformatics Algorithms
TT  - 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
AU  - Özcan, Gıyasettin
AU  - Koca, Burak
PY  - 2018
DA  - December
Y2  - 2018
DO  - 10.17482/uumfd.425094
JF  - Uludağ Üniversitesi Mühendislik Fakültesi Dergisi
JO  - UUJFE
PB  - Bursa Uludağ Üniversitesi
WT  - DergiPark
SN  - 2148-4155
SP  - 91
EP  - 102
VL  - 23
IS  - 3
LA  - en
AB  - Inthis study, we present a new web interface for major bioinformatics algorithms andintroduce a novel approximate string matching algorithm. Our web interface executesmajor algorithms on the field for the use of computational biologists, studentsor any other interested researchers. In the web interface, algorithms comeunder three sections: Sequence alignment, pattern matching and motif finding. Ineach section, we introduce algorithms in order to find best fitting one forspecific dataset and problem. The interface introduces execution time, memoryusage and context specific results of algorithms such as alignment score. Theinterface utilizes emerging open source languages and tools. In order todevelop light and user-friendly interface, all parts of the interface codedwith Python language. On the other hand, Django is used for web interface. Secondcontribution of the study is novel A-BOM algorithm, which is designed forapproximate pattern matching problem. The algorithm is approximate matching variationof Backward Oracle Matching. We compare our algorithm with popular approximatestring matching algorithms. Results denote that A-BOM introduces %30 to %80 shortruntime improvement when compared to current approximate pattern matching algorithmson long patterns.
KW  - Bioinformatics
KW  - A-BOM
KW  - Interface
KW  - Approximate Pattern Matching
N2  - Bu çalışmada temel biyoinformatik algoritmalarıiçin yeni bir web ara yüzü ve özgün bir yaklaşık desen eşleştirme algoritmasısunmaktayız. Web ara yüzümüz biyologlar, öğrenciler ve ilgili araştırmacılariçin bu alandaki temel algoritmaları çalıştırmaktadır. Web ara yüzündealgoritmalar üç bölüm altında toplanmaktadır: Dizilim hizalama, desen eşleştirmeve motif bulma. Her bir bölümde, özgül veri seti ve problemlere en iyi uyanalgoritmanın bulunabilmesi için sonuçlarını karşılaştırabilecekleri algoritmalarsunulmaktadır. Web ara yüzü çalışma süreleri, hafıza kullanımı ve hizalamaskoru gibi konuya özel sonuçları sunmaktadır. Ara yüz yeni geliştirilen açıkkaynak kodlu dilleri ve araçları kullanmaktadır. Hafif ve kullanıcı dostu birara yüz olması amacıyla ara yüzün tüm kısımları Python dili ile kodlanmıştır.Diğer yandan web ara yüzü için Django kullanılmıştır. Çalışmanın ikincikatkısı, yaklaşık desen eşleştirme için tasarlanmış yeni A-BOM algoritmasıdır.Bu algoritma Backwards Oracle Matching algoritmasının yaklaşık varyasyonudur.Algoritmamızı popüler yaklaşık desen eşleştirme algoritmaları ile kıyasladık. Sonuçlar,A-BOM algoritmasını güncel yaklaşık desen eşleştirme algoritmaları ile uzundesenler üzerinde karşılaştırdığımızda, çalışma süresinde %30 ile %80 arasında kısalmagelişimi olduğunu göstermektedir.
CR  - Alluzen, C., Crochemore, M. and Raffinot, M. (1999) Factor Oracle: A New Structure for Pattern Matching, SOFSEM’99: Theory and Practice of Informatics, Lecture Notes in Computer Science, Berlin, 291-306.  doi: 10.1007/3-540-47849-3_18
CR  - Bishop, C. M. (2006) Machine learning and pattern recognition. Information Science and Statistics. Springer, Heidelberg.
CR  - Boyer, R.S., Moore, J.S and Pratt, W.R. (1977) A Fast String Searching Algorithm, Journal of Molecular Biology, Communications of the ACM, New York, 762-772. doi: 10.1145/359842.359859
CR  - Burrows, W. and Wheeler, D. J. (1994) A block-sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, Digital Equipment Corporation, California.
CR  - D'haeseleer, P. (2006) How does DNA sequence motif discovery work?. Nature biotechnology, 24(8), 959-961
CR  - Durbin, R., Eddy, S. R., Krogh, A. and Mitchison, G. (1998) Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press, Cambridge.
CR  - Ji, H. and Shendure, J. (2008) Next-generation DNA sequencing, Nature biotechnology volume 26, Nature Publishing Group, London, 1135-1145. doi: 10.1038/nbt1486
CR  - Knuth, D.E., Morris, J.H and Pratt, W.R. (1977) Fast Pattern Matching in Strings, Journal of Molecular Biology, SIAM Journal on Computing, Philadelphia, 323-350. doi: 10.1137/0206024
CR  - Langmead, B., and Salzberg, S. L. (2012) Fast gapped-read alignment with Bowtie 2. Nature methods, 9(4), 357.
CR  - Navarro, R. and Raffinot, M. (2002) Flexible Pattern Matching in String, The press Syndicate of The University of Cambridge, Cambridge.
CR  - Needleman, S.B. and Wunsch, C.D. (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins, Journal of Molecular Biology, Academic Press Incorporated, London, 443-453.  doi: 10.1016/0022-2836(70)90057-4
CR  - Özcan, G. (2016) Detection of P53 Consensus Sequence: A Novel String Matching With Classes Algorithm, Uludag University Journal of The Faculty of Engineering 21 (2), Bursa, 269-282.
CR  - Özcan, G., and Ünsal, O. S. (2015). Fast bitwise pattern-matching algorithm for DNA sequences on modern hardware. Turkish Journal of Electrical Engineering & Computer Sciences, 23(5), 1405-1417.
CR  - Pevsner, J. (2015) Bioinformatics and functional genomics, John Wiley & Sons, UK
CR  - Smith, T.F. and Waterman, M.S. (1981) Identification of common molecular subsequences, Journal of Molecular Biology, Academic Press Incorporated, London, 40-48. doi: 10.1016/0022-2836(81)90087-5
UR  - https://doi.org/10.17482/uumfd.425094
L1  - http://dergipark.org.tr/tr/download/article-file/562051
ER  -