NETWORK ALIGNMENT: FROM PAIRWISE TO MULTIPLE

The network alignment has been formulated formally. While there are some variations among the tools, the key idea is similar: to combine gene sequence information and protein-protein interaction (PPI) network information to find conserved interaction regions across species. A biological interpretation of network alignment is to find functional homologues across different organisms. The general problem, known as the problem of finding common subgraphs across multiple networks, is NP-hard. Heuristic methods combining sequence, interaction and functional similarities have been developed to tackle it. In this book, state of the art introduction for network alignment is conducted from pairwise to multiple species. For pairwise alignment,HopMap and Mawish extension algorithms are presented with high specificity and sensitivity comparing to existing tools. For multiple alignment, the HopeMap-M alignment algorithm is able to align 10 networks with tens of thousands of proteins each in less than a few minutes. Then based on the framework of parametrized complexity theory, we derive parameterized complexity of Multi-MCS for various parameters on different classes of graphs.