Skip to main content

2015 | OriginalPaper | Buchkapitel

13. Network Alignment

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat Aladag AE, Erten C (2013) SPINAL: scalable protein interaction network alignment. Bioinformatics 29(7):917–924CrossRef Aladag AE, Erten C (2013) SPINAL: scalable protein interaction network alignment. Bioinformatics 29(7):917–924CrossRef
2.
Zurück zum Zitat Altschul S, Gish W, Miller W, Myers E, Lipman D (1990) Basic local alignment search tool. J Mol Biol 215(3):403–410CrossRef Altschul S, Gish W, Miller W, Myers E, Lipman D (1990) Basic local alignment search tool. J Mol Biol 215(3):403–410CrossRef
3.
Zurück zum Zitat Avis D (1983) A survey of heuristics for the weighted matching problem. Networks 13(4):475–493 Avis D (1983) A survey of heuristics for the weighted matching problem. Networks 13(4):475–493
4.
Zurück zum Zitat 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 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.
Zurück zum Zitat Bertsekas DP, Castannon DA (1991) Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput 17:707–732 Bertsekas DP, Castannon DA (1991) Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput 17:707–732
6.
7.
8.
Zurück zum Zitat 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 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.
Zurück zum Zitat Clark C, Kalita J (2014) A comparison of algorithms for the pairwise alignment of biological networks. Bioinformatics 30(16):2351–2359CrossRef Clark C, Kalita J (2014) A comparison of algorithms for the pairwise alignment of biological networks. Bioinformatics 30(16):2351–2359CrossRef
10.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Fortin S (1996) The graph isomorphism problem. Technical Report TR 96-20, Department of Computer Science, The University of Alberta Fortin S (1996) The graph isomorphism problem. Technical Report TR 96-20, Department of Computer Science, The University of Alberta
13.
Zurück zum Zitat Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York
16.
Zurück zum Zitat 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 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.
Zurück zum Zitat Klau GW (2009) A new graph-based method for pairwise global network alignment. BMC Bioinform 10(Suppl 1):S59CrossRef Klau GW (2009) A new graph-based method for pairwise global network alignment. BMC Bioinform 10(Suppl 1):S59CrossRef
18.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Kuchaiev O, Przulj N (2011) Integrative network alignment reveals large regions of global network similarity in yeast and human. Bioinformatics 27(10):1390–1396CrossRef Kuchaiev O, Przulj N (2011) Integrative network alignment reveals large regions of global network similarity in yeast and human. Bioinformatics 27(10):1390–1396CrossRef
23.
Zurück zum Zitat 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 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.
Zurück zum Zitat Liang Z, Xu M, Teng M, Niu L (2006) Comparison of protein interaction networks reveals species conservation and divergence. BMC Bioinf. 7(1):457CrossRef 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Milenkovic T et al (2010) Optimal network alignment with graphlet degree vectors. Cancer Inf. 9:121–137CrossRef Milenkovic T et al (2010) Optimal network alignment with graphlet degree vectors. Cancer Inf. 9:121–137CrossRef
27.
Zurück zum Zitat Memievic V, Pruzlj N (2012) C-GRAAL: common-neighbors-based global GRaph ALignment of biological networks. Integr. Biol. 4(7):734–743 Memievic V, Pruzlj N (2012) C-GRAAL: common-neighbors-based global GRaph ALignment of biological networks. Integr. Biol. 4(7):734–743
28.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Patro R, Kingsford C (2012) Global network alignment using multiscale spectral signatures. Bioinformatics 28(23):3105–3114CrossRef Patro R, Kingsford C (2012) Global network alignment using multiscale spectral signatures. Bioinformatics 28(23):3105–3114CrossRef
31.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Riedyn J (2010) Making static pivoting scalable and dependable. Ph.D. Thesis, EECS Department, University of California, Berkeley Riedyn J (2010) Making static pivoting scalable and dependable. Ph.D. Thesis, EECS Department, University of California, Berkeley
34.
Zurück zum Zitat Sathe M, Schenk O, Burkhart H (2012) An auction-based weighted matching implementation on massively parallel architectures. Parallel Comput 38(12):595–614MathSciNetCrossRef Sathe M, Schenk O, Burkhart H (2012) An auction-based weighted matching implementation on massively parallel architectures. Parallel Comput 38(12):595–614MathSciNetCrossRef
35.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Sharan R, Ideker T (2006) Modeling cellular machinery through biological network comparison. Nat Biotechnol 24(4):427–433CrossRef Sharan R, Ideker T (2006) Modeling cellular machinery through biological network comparison. Nat Biotechnol 24(4):427–433CrossRef
38.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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
41.
Zurück zum Zitat Yan X, Han J (2002) Gspan: graph-based substructure pattern mining. In: Proceedings of IEEE international conference on data mining, pp 721–724 Yan X, Han J (2002) Gspan: graph-based substructure pattern mining. In: Proceedings of IEEE international conference on data mining, pp 721–724
Metadaten
Titel
Network Alignment
verfasst von
K. Erciyes
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-24966-7_13