BibTex RIS Cite

Network Motifs and Indexing Techniques on Biological Networks

Year 2012, Volume: 8 Issue: 2, 87 - 102, 01.07.2012

Yusuf Kavurucu

Abstract

Keywords

-

References

  • 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.
  • A. Bairoch, B. Boeckmann, S. Ferro, and E. Gasteiger. Swiss-Prot: juggling between evolution and stability. Briefings in Bioinformatics, 1:39-55, 2004.
  • Michael Baudis and Michael L. Cleary. Progenetix.net: an online repository for molecular cytogenetic aberration data. Bioinformatics, 17(12): 1228-1229, 2001.
  • 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.
  • Peter Damaschke. Graph-Theoretic Concepts in Computer Science, volume 484/1991 of Lecture Notes in Computer Science, pages 72-78. Springer Berlin / Heidelberg, 1991.
  • 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.
  • Milo R, Shen-Orr S, Itzkovitz S, et al. Network motifs: simple building blocks of complex networks. Science 2002; 298:824-27.
  • Kashtan N, Alon U. Spontaneous evolution of modularity and network motifs. Proc Natl Acad Sci USA 2005;102:13773-78.
  • Sole' RV, Valverde S. Are network motifs the spandrels of cellular complexity? Trends Ecol Evol 2006;21:419-22.
  • Bottani S, Vergassola M, Mazurie A. An evolutionary and functional assessment of regulatory network motifs. Genome Biol 2005;6:R35.
  • Kashani ZRM, Ahrabian H, Elahi E, et al. Kavosh: a new algorithm for finding network motifs. BMC Bioinformatics 2009;10:318.[
  • Grochow JA, Kellis M. Network motif discovery using sub-graph enumeration and symmetry breaking. Res Comp Mol Biol 2007;4456:92-106.
  • Kuramochi M, Karypis G. Frequent sub-graph discovery. In: Proceedings of IEEE International Conference on Data Mining 2001, San Jose, California, 313-20.
  • Schreiber F, Schwobbermeyer H. Frequency concepts and pattern detection for the analysis of motifs in networks. LectNotes Comput Sci 2005;3737:89-104.
  • Babai, L., Luks, E. M., 1983. Canonical labeling of graphs. In: STOC. pp 171-183.
  • Kuramochi M, Karypis G. Finding frequent patterns in a large sparse graph. Data Mining and Knowledge Discovery 2005, 11(3), 243-271.
  • Baskerville, K., Paczuski, M., 2006. Subgraph ensembles and motif discovery using an alternative heuristic for graph isomorphism. Physical Review E 74 (5), 51903.
  • 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.
  • 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.
  • F. Ay and T. Kahveci. SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings. In RECOMB, pp. 15-30 (2010)
  • 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).
  • 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.
  • 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.
  • 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.
  • X. Yan, P. S. Yu, and J. Han. Substructure similarity search in graph databases. In SIGMOD Conference, pp. 766-777 (2005).
  • H. He and A. K. Singh, Closure-Tree: An index structure for graph queries, International Conference on Data Engineering. 0, 38 (2006).
  • 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).
  • 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.
  • 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).
  • G. Gulsoy and T. Kahveci, RINQ: Reference-based indexing for network queries, Bioinformatics [ISMB/ECCB]. 27(13), 149{158 (2011).

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

Year 2012, Volume: 8 Issue: 2, 87 - 102, 01.07.2012

Yusuf Kavurucu

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

  • 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.
  • A. Bairoch, B. Boeckmann, S. Ferro, and E. Gasteiger. Swiss-Prot: juggling between evolution and stability. Briefings in Bioinformatics, 1:39-55, 2004.
  • Michael Baudis and Michael L. Cleary. Progenetix.net: an online repository for molecular cytogenetic aberration data. Bioinformatics, 17(12): 1228-1229, 2001.
  • 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.
  • Peter Damaschke. Graph-Theoretic Concepts in Computer Science, volume 484/1991 of Lecture Notes in Computer Science, pages 72-78. Springer Berlin / Heidelberg, 1991.
  • 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.
  • Milo R, Shen-Orr S, Itzkovitz S, et al. Network motifs: simple building blocks of complex networks. Science 2002; 298:824-27.
  • Kashtan N, Alon U. Spontaneous evolution of modularity and network motifs. Proc Natl Acad Sci USA 2005;102:13773-78.
  • Sole' RV, Valverde S. Are network motifs the spandrels of cellular complexity? Trends Ecol Evol 2006;21:419-22.
  • Bottani S, Vergassola M, Mazurie A. An evolutionary and functional assessment of regulatory network motifs. Genome Biol 2005;6:R35.
  • Kashani ZRM, Ahrabian H, Elahi E, et al. Kavosh: a new algorithm for finding network motifs. BMC Bioinformatics 2009;10:318.[
  • Grochow JA, Kellis M. Network motif discovery using sub-graph enumeration and symmetry breaking. Res Comp Mol Biol 2007;4456:92-106.
  • Kuramochi M, Karypis G. Frequent sub-graph discovery. In: Proceedings of IEEE International Conference on Data Mining 2001, San Jose, California, 313-20.
  • Schreiber F, Schwobbermeyer H. Frequency concepts and pattern detection for the analysis of motifs in networks. LectNotes Comput Sci 2005;3737:89-104.
  • Babai, L., Luks, E. M., 1983. Canonical labeling of graphs. In: STOC. pp 171-183.
  • Kuramochi M, Karypis G. Finding frequent patterns in a large sparse graph. Data Mining and Knowledge Discovery 2005, 11(3), 243-271.
  • Baskerville, K., Paczuski, M., 2006. Subgraph ensembles and motif discovery using an alternative heuristic for graph isomorphism. Physical Review E 74 (5), 51903.
  • 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.
  • 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.
  • F. Ay and T. Kahveci. SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings. In RECOMB, pp. 15-30 (2010)
  • 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).
  • 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.
  • 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.
  • 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.
  • X. Yan, P. S. Yu, and J. Han. Substructure similarity search in graph databases. In SIGMOD Conference, pp. 766-777 (2005).
  • H. He and A. K. Singh, Closure-Tree: An index structure for graph queries, International Conference on Data Engineering. 0, 38 (2006).
  • 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).
  • 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.
  • 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).
  • G. Gulsoy and T. Kahveci, RINQ: Reference-based indexing for network queries, Bioinformatics [ISMB/ECCB]. 27(13), 149{158 (2011).
There are 30 citations in total.

Details

Primary Language Turkish
Journal Section Articles
Authors

Yusuf Kavurucu This is me

Publication Date July 1, 2012
Published in Issue Year 2012 Volume: 8 Issue: 2

Cite

APA Kavurucu, Y. . (2012). BİYOLOJİK AĞLARDA AĞ MOTİFLERİ VE İNDEKSLEME TEKNİKLERİ. Journal of Naval Sciences and Engineering, 8(2), 87-102.