Oral Candidacy - Vipin Vijayan
|Start:||8/13/2015 at 8:00AM|
|End:||8/13/2015 at 11:00AM|
|Location:||258 Fitzpatrick Hall|
Faculty and students are welcome to attend the presentation portion of the defense.
August 20, 2015 8:00 am 258 Fitzpatrick Hall
Adviser: Dr. Tijana Milenkovic
Dr. Danny Chen Dr. Collin McMillan Dr. Aaron Striegel Dr. Tim Weninger
"Novel algorithmic and evaluation framework for network alignment with applications in computational biology"
Networks are used to model a wide variety of real-world systems. Network alignment (NA) is a popular computational problem in network research. Namely, NA aims to find a node mapping between networks that identifies topologically or functionally similar network regions. As such, NA has applications in many fields, including computational biology, pattern recognition, language processing, and social networks. The focus of my Ph.D. research is on NA in the domain of computational biology, where NA is used to align biological networks of different species. Namely, biological networks such as protein-protein interaction (PPI) networks model interactions between proteins in the cell. Then, NA can be used to align PPI networks of different species and guide the transfer of biological knowledge from well-studied species to poorly-studied species between conserved(i.e., aligned) network regions. As such, NA has the potential to revolutionize our biological understanding, just as genomic sequence alignment has had.
NA is a computationally intractable (or NP-hard) problem. Thus, heuristic yet accurate NA methods need to be sought. Existing NA methods can be categorized into pairwise and multiple ones. Pairwise NA (PNA) aims to align two networks while multiple NA (MNA) can deal with two or more networks. While MNA may lead to deeper biological insights compared to PNA since MNA captures functional knowledge common in multiple species, the complexity of the NA problem increases exponentially with the number of networks to be aligned.
In this context, we first introduce MAGNA++, our novel state-of-the-art PNA method. Second, we introduce our new method called multilane++, 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 in the same NA category, we propose a comprehensive evaluation of PNA against MNA that could guide future NA research on which class of methods to pursue. Finally, in order to improve upon the state-of-the-art in NA research, we propose a novel algorithmic idea that is expected to further improve alignment quality.