Novel Algorithmic Contributions and Evaluation Frameworks for Network Alignment with Applications in Computational Biology

Networks are used to model a wide variety of real-world systems. Network alignment (NA) aims to find a node mapping between networks that identifies topologically or functionally similar network regions. NA has applications in many fields, including computational biology, ontology matching, language processing, and social networks. The focus of this dissertation is on NA in the domain of computational biology, where NA is used to align biological networks of different species, such as the species' protein interaction networks (PINs). Then, NA can guide the transfer of biological knowledge from well-studied species to poorly-studied species between conserved (i.e., aligned) PIN regions. As such, NA has the potential to revolutionize our biological understanding, just as genomic sequence alignment has had.

NA can be categorized into pairwise and multiple. Pairwise NA (PNA) aims to align two networks while multiple NA (MNA) can align more than two networks. It is hypothesized that MNA might lead to deeper biological insights than PNA, because MNA can simultaneously capture conserved regions between more networks than PNA, though at the expense of higher computational complexity. In this context, we make the following contributions. First, we introduce MAGNA++, our novel state-of-the-art PNA method. Second, we introduce our new method called multiMAGNA++, which is MAGNA++'s equivalent for MNA. We also introduce new measures of alignment quality for MNA. Third, since new PNA or MNA methods proposed in the literature are generally compared only to other methods from the same NA category, we perform the first ever evaluation of PNA against MNA, where we shockingly find that in general PNA is both more accurate and faster than MNA, which has many implications for future NA research. Fourth, existing NA methods can only align static networks. However, most of complex real-world systems evolve over time and should thus be modeled as dynamic networks. We hypothesize that aligning dynamic network representations of evolving systems will produce superior alignments compared to aligning the systems' static network representations, as is currently done. For this purpose, we introduce the first ever dynamic PNA method and confirm our hypothesis.