You are here

Home » Content

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

NETWORK MOTIFS AND INDEXING TECHNIQUES IN BIOLOGICAL NETWORKS

Journal Name:

  • Journal of Naval Sciences And Engineering

Publication Year:

  • 2012

Key Words:

Keywords (Original Language):

Author Name
Abstract (2. Language): 
Subgraphs that occur in complex networks with significantly higher frequency than those in randomized networks are called Network Motifs. Such subgraphs are the basic building blocks of complex networks. They often play important roles on functioning of those networks. Finding network motifs is a computationally challenging problem. Finding network motifs often requires solving subgraph isomorphism problem which is NPcomplete. Instead of this, several methods apply similarity queries on biological networks to find similar patterns that exist frequently according to given threshold values. As these networks are stored in databases, we need efficient methods for accessing and querying these databases. As these networks are generally represented as graphs in theory, several graph indexing methods are developed for answering queries on them. This paper summarizes network motifs and indexing techniques in biological networks.
Bookmark/Search this post with
Abstract (Original Language): 
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.
FULL TEXT (PDF): 
PDF icon arastirmax-biyolojik-aglarda-ag-motifleri-indeksleme-teknikleri.pdf
  • 2
87
102
  • Turkish

REFERENCES

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.[
Yusuf KAVURUCU
102
[12] Grochow JA, Kellis M. Network motif discovery using sub-graph enumeration and symmetrybreaking.
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.
[16] Schreiber F, Schwobbermeyer H. Frequency concepts and pattern detection for the analysis of
motifs in networks. LectNotes Comput Sci 2005;3737:89–104.
[17] Babai, L., Luks, E. M., 1983. Canonical labeling of graphs. In: STOC. pp 171-183.
[18] Kuramochi M, Karypis G. Finding frequent patterns in a large sparse graph. Data Mining and
Knowledge Discovery 2005, 11(3), 243–271.
[19] Baskerville, K., Paczuski, M., 2006. Subgraph ensembles and motif discovery using an
alternative heuristic for graph isomorphism. Physical Review E 74 (5), 51903.
[20] 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.
[21] 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.
[22] F. Ay and T. Kahveci. SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings. In
RECOMB, pp. 15-30 (2010)
[23] 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).
[24] 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.
[25] 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.
[26] 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.
[27] X. Yan, P. S. Yu, and J. Han. Substructure similarity search in graph databases. In SIGMOD
Conference, pp. 766-777 (2005).
[28] H. He and A. K. Singh, Closure-Tree: An index structure for graph queries, International
Conference on Data Engineering. 0, 38 (2006).
[29] 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).
[30] 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.
[31] 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).
[32] G. Gulsoy and T. Kahveci, RINQ: Reference-based indexing for network queries,
Bioinformatics [ISMB/ECCB]. 27(13), 149{158 (2011).

Thank you for copying data from http://www.arastirmax.com