Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2015 | OriginalPaper | Chapter

13. Network Alignment

Author : K. Erciyes

Published in: Distributed and Sequential Algorithms for Bioinformatics

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Biological networks are dynamic and the measurements can contain errors which results in two networks of the same origin to look different. Alignment of two or more networks is the process of searching for similarities between them. This task requires mapping nodes of one network to another by associating some similarity measure with the aim of pairing nodes that have the highest affinity. Network alignment is needed to compare biological networks to find their phylogenetic relationships and to find approximately conserved subnetworks in them. Since this problem is intractable, various heuristic algorithms are proposed. In the graph domain, the alignment operation can be accomplished by forming a weighted complete k-partite graph with partitions from each network and edge weights showing the similarity. The problem is then reduced to maximal weighted complete k-partite matching problem which has been investigated thoroughly. In this chapter, we first state the relation of the problem to graph isomorphism and the weighted complete k-partite matching and show the metrics for the alignment quality. We then review few sequential algorithms for this problem. Distributed alignment algorithms are scarce and we propose a new algorithm that uses k-partite matching property.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Network Motif Search
next chapter Phylogenetics
Literature
1.
Aladag AE, Erten C (2013) SPINAL: scalable protein interaction network alignment. Bioinformatics 29(7):917–924CrossRef
2.
Altschul S, Gish W, Miller W, Myers E, Lipman D (1990) Basic local alignment search tool. J Mol Biol 215(3):403–410CrossRef
3.
Avis D (1983) A survey of heuristics for the weighted matching problem. Networks 13(4):475–493
4.
Battiti R, Mascia F (2007) Engineering stochastic local search algorithms. designing, implementing and analyzing effective heuristics, An algorithm portfolio for the subgraph isomorphism problem. Springer, Berlin, pp 106–120
5.
Bertsekas DP, Castannon DA (1991) Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput 17:707–732
6.
7.
8.
Catalyurek UV, Dobrian F, Gebremedhin AH, Halappanavar M, Pothen A (2011) Distributed-memory parallel algorithms for matching and coloring. In: 2011 international symposium on parallel and distributed processing, workshops and Ph.D. forum (IPDPSW), workshop on parallel computing and optimization (PCO11), IEEE Press, pp 1966–1975
9.
Clark C, Kalita J (2014) A comparison of algorithms for the pairwise alignment of biological networks. Bioinformatics 30(16):2351–2359CrossRef
10.
El-Kebir M, Heringa J, Klau GW (2011) Lagrangian relaxation applied to sparse global network alignment. In: Proceedings of 6th IAPR international conference on pattern recognition in bioinformatics (PRIB’11), Springer, pp 225-236
11.
Flannick J, Novak A, Srinivasan BS, McAdams HH, Batzoglou S (2006) Graemlin: general and robust alignment of multiple large interaction networks. Genome Res 16:1169–1181
12.
Fortin S (1996) The graph isomorphism problem. Technical Report TR 96-20, Department of Computer Science, The University of Alberta
13.
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York
14.
15.
16.
Kelley BP, Sharan R, Karp RM, Sittler T, Root DE, Stockwell BR, Ideker T (2003) Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc PNAS 100(20):11394–11399
17.
Klau GW (2009) A new graph-based method for pairwise global network alignment. BMC Bioinform 10(Suppl 1):S59CrossRef
18.
Kollias G, Mohammadi S, Grama A (2012) Network Similarity Decomposition (NSD): a fast and scalable approach to network alignment. IEEE Trans Knowl Data Eng 24(12):2232–2243CrossRef
19.
Koyuturk M, Kim Y, Topkara U, Subramaniam S, Szpankowski W, Grama A (2006) Pairwise alignment of protein interaction networks. J Comput Biol 13(2):182–199MathSciNetCrossRef
20.
Kuchaiev O, Milenkovic T, Memisevic V, Hayes W, Przulj N (2010) Topological network alignment uncovers biological function and phylogeny. J Royal Soc Interface 7(50):1341–1354CrossRef
21.
Kuchaiev O, Przulj N (2011) Integrative network alignment reveals large regions of global network similarity in yeast and human. Bioinformatics 27(10):1390–1396CrossRef
22.
23.
Kuramochi M, G. Karypis G (2001) Frequent subgraph discovery. In: Proceedings of 2001 IEEE international conference on data mining, IEEE Computer Society, pp 313–320
24.
Liang Z, Xu M, Teng M, Niu L (2006) Comparison of protein interaction networks reveals species conservation and divergence. BMC Bioinf. 7(1):457CrossRef
25.
Manne F, Bisseling RH, A parallel approximation algorithm for the weighted maximum matching problem. In: Wyrzykowski R, Karczewski K, Dongarra J, Wasniewski J (eds) Proceedings of seventh international conference on parallel processing and applied mathematics (PPAM 2007), Lecture notes in computer science, vol 4967. Springer, pp 708–717
26.
Milenkovic T et al (2010) Optimal network alignment with graphlet degree vectors. Cancer Inf. 9:121–137CrossRef
27.
Memievic V, Pruzlj N (2012) C-GRAAL: common-neighbors-based global GRaph ALignment of biological networks. Integr. Biol. 4(7):734–743
28.
Messmer BT, Bunke H (1996) Subgraph isomorphism detection in polynomial time on preprocessed model graphs. Recent developments in computer vision. Springer, Berlin, pp 373–382CrossRef
29.
Ogata H, Fujibuchi W, Goto S, Kanehisa M (2000) A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucleic Acids Res 28:4021–4028CrossRef
30.
Patro R, Kingsford C (2012) Global network alignment using multiscale spectral signatures. Bioinformatics 28(23):3105–3114CrossRef
31.
Preis R (1999) Linear time 2-approximation algorithm for maximum weighted matching in general graphs. In: C. Meinel, S. Tison (eds) STACS99 Proceeedings 16th annual conference theoretical aspects of computer science, Lecture notes in computer science, vol 1563. Springer, New York, pp 259–269
32.
Przulj N (2005) Graph theory analysis of protein-protein interactions. In: Igor J, Dennis W (eds) A chapter in knowledge discovery in proteomics. CRC Press
33.
Riedyn J (2010) Making static pivoting scalable and dependable. Ph.D. Thesis, EECS Department, University of California, Berkeley
34.
Sathe M, Schenk O, Burkhart H (2012) An auction-based weighted matching implementation on massively parallel architectures. Parallel Comput 38(12):595–614MathSciNetCrossRef
35.
Sharan R, Suthram S, Kelley RM, Kuhn T, McCuine S, Uetz P, Sittler T, Karp RM, Ideker T (2005) Conserved patterns of protein interaction in multiple species. Proc Natl Acad Sci USA 102:1974–1979
36.
Sharan R et al (2005) Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data. J Comput Biol 12:835–846CrossRef
37.
Sharan R, Ideker T (2006) Modeling cellular machinery through biological network comparison. Nat Biotechnol 24(4):427–433CrossRef
38.
Singh R, Xu J, Berger B (2007) Pairwise global alignment of protein interaction networks by matching neighborhood topology. In: Research in computational molecular biology, Springer, pp 16-31
39.
Singh R, Xu J, Berger B (2008) Global alignment of multiple protein interaction networks with application to functional orthology detection. PNAS 105(35):12763–12768CrossRef
40.
41.
Yan X, Han J (2002) Gspan: graph-based substructure pattern mining. In: Proceedings of IEEE international conference on data mining, pp 721–724
Metadata
Title
Network Alignment
Author
K. Erciyes
Copyright Year
2015
Book
Distributed and Sequential Algorithms for Bioinformatics

Print ISBN: 978-3-319-24964-3

Electronic ISBN: 978-3-319-24966-7

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-24966-7_13

Premium Partner

    Image Credits