Comparison of DNA Patterns with Graf Simulation

Year 2018, Volume: 1 Issue: 1, 15 - 19, 25.12.2018

Cantekin Çelikhası Ahmet Sayar Adem Ulu

Abstract

The
aim of this study is to calculate the similarity ratio of the sequences in
different DNA samples. In order to increase the performance and shorten the
transaction volume of the DNA data, DNA sequences were compressed and DNA
motifs were obtained. For this, the LZ Compression algorithm was used. While
each of the obtained motifs was only a graph node, the order of these motifs
was transformed into graphs expressing the edge of the nodes. The obtained
graph from each DNA was used to find the similarity in DNA. According to the algorithms
calculating the similarity ratio on the graphs, we compared both Neighbor
Matching and Cosinus Similarity methods and then we showed that Cosinus
Similarity is more efficient than Neighbor Matching.

Keywords

LZ Compression, Neighbor Matching, Cosinus Similarity, Graph Similarity, DNA pattern exploration

DNA Dizilerinin Graf Benzetim Yolu İle Karşılaştırılması

Abstract

Bu
çalışmanın amacı farklı DNA örneklerindeki dizilimlerin benzerlik oranını
hesaplamaktır. DNA verilerinin büyüklüklerinin getirdiği işlem hacmini
kısaltmak ve performansı arttırmak için,DNA dizileri sıkıştırılıp motif
çıkarımı yapıldı. Bunun için LZ Sıkıştırma algoritması kullanıldı. Elde edilen
motiflerden her biri sadece bir graf düğümünü ifade ederken bu motiflerin
sırası da düğümlerin komşuluklarını ifade edecek şekilde grafa dönüştürüldü.
Her bir DNA’dan elde edilen graf, DNA’lardaki benzerliği bulabilmek için
kullanıldı. Graflar üzerinden benzerlik oranını hesaplayan algoritmalardan, her
iki Komşu Eşleşme ve Kosinüs Benzerliği metotlarını karşılaştırdık. Buna göre Kosinüs
Benzerliği’nin Komşu Eşleşme’ye göre daha performanslı olduğunu gösterdik.

Keywords

Graf Benzerliği, LZ Sıkıştırma, Komşu Eşleşme, Kosinüs Benzerliği, DNA örüntü keşfi

References

• [1] R Shamir, Bioinformatics for Biologists, California: Cambridge, 2014.
• [2] M SÜLÜ, Graf Tabanlı Biyolojik Dizilerde Örüntü Keşfi, Elazığ, 2011.
• [3] GenBank, Pan paniscus mitochondrial DNA, complete sequence, 26 7 2016. [Çevrimiçi]. Available: https://www.ncbi.nlm.nih.gov/nuccore/D38116. [Erişildi: 15 4 2018].
• [4] Elkan, Timothy L Bailey and Charles ,Fitting a mixture model by expectation maximization to discover motifs in biopolymers, Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology, pp. 28-36, 1994.
• [5] CE Lawrence, SF Altschul, MS Boguski, JS Liu, AF Neuwald, JC Wootton, Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment, Science, p. 262, 1993.
• [6] U B BALOĞLU, Dna Sıralarındaki Tekrarlı Örüntülerin Ve Potansiyel Motiflerin Veri Madenciliği Yöntemiyle Çıkarılması, Fırat Üniverstesi, Elazığ, 2006.
• [7] A Lempel, J Ziv, On the Complexity of Finite Sequences, IEEE Transactions on Information Theory, p. 22, 1976.
• [8] M Nikolic, Measuring Similarity of Graph Nodes by Neighbor Matching, IOS Press, pp. 865-878, 2012.
• [9] M Gallo, Implementing and Understanding Cosine Similarity, 29 07 2016. [Çevrimiçi]. Available: https://masongallo.github.io/machine/learning,/python/2016/07/29/cosine-similarity.html [Erişildi: 10 04 2018].
• [10] A Madylova, Kosinüs Benzerliğini Kullanarak Belgeler Arası Anlamsal Benzerliği Kavramsal Sözlüğe Dayalı Hesaplama Yöntemi, İTU, İstanbul, 2009.
• [11] B Anderson, H.Sapiens mitochondrial genome, 14 7 2016. [Çevrimiçi]. Available: https://www.ncbi.nlm.nih.gov/nuccore/V00662. [Erişildi: 15 04 2018].