Algorithms to Identify Functional Orthologs And Functional Modules from High- Throughput Data

Abstract

Many studies in the last decade suggest that the biological network topology supplementing the genome is another important source of biological information for understanding the fundamental principle of life processes. A typical approach aiming to gain insights from the network information is network alignment. It provides a promising framework to understand the organization, function and evolution of molecular networks. However, current algorithms encounter their bottlenecks in terms of scalability, speed and so forth when applied to analyze multiple networks. Hence, it is desired to develop novel, efficient strategies to cope with the rapidly growing data in this particular field. In this thesis, we present two new network alignment algorithms, LocalAli and NetCoffee, and their applications in the analysis of biological data. Both of the two algorithms focus on the problem of multiple network alignment, but they run into different directions: local alignment and global alignment. LocalAli is an evolutionary-based local alignment approach that aims to identify functionally conserved modules from multiple biological networks. In this algorithm, a computational framework is firstly proposed to reconstruct the evolution history of functionally conserved modules. NetCoffee is a global alignment approach with a goal to detect function-oriented ortholog groups from multiple biological networks. The two algorithms have been applied to several real-world datasets. The results show that both Localali and Netcoffee provide substantial improvements to current algorithms in terms of several criteria such as scalability, coverage and consistency. All the test datasets, binaries and source code used for this thesis are freely available at https://code.google.com/p/localali/ and https://code.google.com/p/netcoffee/.