Network Motifs and Indexing Techniques on Biological Networks

Abstract

Keywords

• -

BİYOLOJİK AĞLARDA AĞ MOTİFLERİ VE İNDEKSLEME TEKNİKLERİ

Abstract

Karmaşık ağlarda rastgele oluşturulmuş ağlara oranda önemli derece daha fazla sıklıkta bulunan alt ağlar ağ motifleri olarak adlandırılır. Söz konusu alt ağlar ilgili karmaşık ağın temel yapı taşlarıdır. Bunlar genellikle ait oldukları karmaşık ağlarda önemli roller oynarlar. Ağ motiflerinin bilgisayar vasıtasıyla tespit edilmesi zor bir problemdir. Ağ motiflerinin tespiti genellikle NP-complete zorluk derecesine sahip alt ağ izomorfizm probleminin çözümünü gerektirir. Bunun yerine, çeşitli yöntemler, biyolojik ağlarda tanımlı oranlardan daha fazla sıklıkta bulunan benzer yapıları tespit etmek için benzerlik sorguları uygularlar. Bu ağlar veritabanlarında saklanıldığından, bu veritabanlarına hızlıca erişebilecek ve veritabanını sorgulayabilecek etkili yöntemlere ihtiyaç duymaktayız. Söz konusu ağlar teorik olarak genelde çizge yapısında tanımlandığı için bu sorguları cevaplamaya yardımcı olacak çeşitli çizge indeksleme teknikleri geliştirilmiştir. Bu çalışmada, biyolojik ağlardaki ağ motifleri ve indeksleme teknikleri hakkında özet bilgi sunulmuştur.

Keywords

• Biyolojik Ağlar, Ağ Motifi, Çizge İndeksleme

References

1. D.A. Benson, I. Karsch-Mizrachi, D.J. Lipman, J. Ostell, B.A. Rapp, and D.L. Wheeler. GenBank. Nucleic Acids Research, 28(1): 15—18, January 2000.
2. A. Bairoch, B. Boeckmann, S. Ferro, and E. Gasteiger. Swiss-Prot: juggling between evolution and stability. Briefings in Bioinformatics, 1:39-55, 2004.
3. Michael Baudis and Michael L. Cleary. Progenetix.net: an online repository for molecular cytogenetic aberration data. Bioinformatics, 17(12): 1228-1229, 2001.
4. H Ogata, S Goto, K Sato,WFujibuchi, H Bono, and M Kanehisa. KEGG: Kyoto Encyclopedia of Genes and Genomes. Nucleic Acids Research, 27(1):29-34, 1999.
5. Peter Damaschke. Graph-Theoretic Concepts in Computer Science, volume 484/1991 of Lecture Notes in Computer Science, pages 72-78. Springer Berlin / Heidelberg, 1991.
6. Wojciech Szpankowski Mehmet Koyuturk, Ananth Grama. An efficient algorithm for detecting frequent subgraphs in biological networks. In ISMB/ECCB (Supplement of Bioinformatics), pages 200-207, 2004.
7. Milo R, Shen-Orr S, Itzkovitz S, et al. Network motifs: simple building blocks of complex networks. Science 2002; 298:824-27.
8. Kashtan N, Alon U. Spontaneous evolution of modularity and network motifs. Proc Natl Acad Sci USA 2005;102:13773-78.

9. Sole' RV, Valverde S. Are network motifs the spandrels of cellular complexity? Trends Ecol Evol 2006;21:419-22.
10. Bottani S, Vergassola M, Mazurie A. An evolutionary and functional assessment of regulatory network motifs. Genome Biol 2005;6:R35.
11. Kashani ZRM, Ahrabian H, Elahi E, et al. Kavosh: a new algorithm for finding network motifs. BMC Bioinformatics 2009;10:318.[
12. Grochow JA, Kellis M. Network motif discovery using sub-graph enumeration and symmetry breaking. Res Comp Mol Biol 2007;4456:92-106.
13. Kuramochi M, Karypis G. Frequent sub-graph discovery. In: Proceedings of IEEE International Conference on Data Mining 2001, San Jose, California, 313-20.
14. Schreiber F, Schwobbermeyer H. Frequency concepts and pattern detection for the analysis of motifs in networks. LectNotes Comput Sci 2005;3737:89-104.
15. Babai, L., Luks, E. M., 1983. Canonical labeling of graphs. In: STOC. pp 171-183.
16. Kuramochi M, Karypis G. Finding frequent patterns in a large sparse graph. Data Mining and Knowledge Discovery 2005, 11(3), 243-271.
17. Baskerville, K., Paczuski, M., 2006. Subgraph ensembles and motif discovery using an alternative heuristic for graph isomorphism. Physical Review E 74 (5), 51903.
18. R. Y. Pinter, O. Rokhlenko, E. Yeger-Lotem, and M. Ziv-Ukelson, Alignment of metabolic pathways, Bioinformatics. 21(16), 3401-3408 (Aug, 2005). doi: 10.1093/bioinformatics/bti554.
19. T. Shlomi, D. Segal, E. Ruppin, and R. Sharan, QPath: a method for querying pathways in a protein-protein interaction network, BMC Bioinformatics. 7, 199 (2006). doi: 10.1186/1471 2105-7-199.
20. F. Ay and T. Kahveci. SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings. In RECOMB, pp. 15-30 (2010)
21. F. Ay, T. Kahveci, and V. de Crecy-Lagard, A fast and accurate algorithm for comparative analysis of metabolic pathways, J. Bioinformatics and Computational Biology. 7(3), 389-428 (2009).
22. Y. Tian, R. C. McEachin, C. Santos, D. J. States, and J. M. Patel, SAGA: a subgraph matching tool for biological graphs, Bioinformatics. 23(2), 232-239 (2007). doi: 10.1093/bioinformatics/btl571.
23. R. Giugno and D. Shasha. GraphGrep: A fast and universal method for querying graphs. In Proc. 16th Int Pattern Recognition Conf, vol. 2, pp. 112-115 (2002). doi: 10.1109/ICPR.2002.1048250.
24. X. Yan, P. S. Yu, and J. Han. Graph indexing: a frequent structure-based approach. In SIGMOD, pp. 335-346, ACM, New York, NY, USA (2004). ISBN 1-58113-859-8. doi: http://doi.acm.org/10.1145/1007568.1007607.
25. X. Yan, P. S. Yu, and J. Han. Substructure similarity search in graph databases. In SIGMOD Conference, pp. 766-777 (2005).
26. H. He and A. K. Singh, Closure-Tree: An index structure for graph queries, International Conference on Data Engineering. 0, 38 (2006).
27. S. Berretti, A. D. Bimbo, and E. Vicario, Efficient matching and indexing of graph models in content-based retrieval, IEEE Trans. Pattern Anal. Mach. Intell. 23(10), 1089-1105 (2001).
28. P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, pp. 426-435, Morgan Kaufmann (1997). ISBN 1-55860-470-7.
29. J. Lee, J.-H. Oh, and S. Hwang. Strg-index: Spatio-temporal region graph indexing for large video databases. In SIGMOD Conference, pp. 718-729 (2005).
30. G. Gulsoy and T. Kahveci, RINQ: Reference-based indexing for network queries, Bioinformatics [ISMB/ECCB]. 27(13), 149{158 (2011).