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

Doctoral Dissertation

Abstract

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.

Attributes

Attribute NameValues
Author Vipin Vijayan
Contributor Aaron Striegel, Committee Member
Contributor Tim Weninger, Committee Member
Contributor Collin McMillan, Committee Member
Contributor Tijana Milenkovic, Research Director
Degree Level Doctoral Dissertation
Degree Discipline Computer Science and Engineering
Degree Name Doctor of Philosophy
Defense Date
  • 2017-03-24

Submission Date 2017-04-13
Subject
  • Network science

  • Network alignment

  • Network analysis

  • Data science

  • Bioinformatics

  • Computer science

  • Protein interaction networks

  • Temporal networks

  • Dynamic networks

Language
  • English

Access Rights Open Access
Content License
  • All rights reserved

Departments and Units

Files

Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.

VijayanV042017D.pdf

University of Notre Dame

Thumbnail

At the request of the author, this graduate work is not available to the public.

If you have Notre Dame credentials you can view this file after you Log in.

Otherwise, you must request permission to view this file from the Publications Manager of the Graduate School.

Request Access