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/.

In der letzten Dekade haben immer mehr Studien gezeigt, dass biologische Netzwerktopologien, zusätzlich zu den bisher verwendeten genomischen Daten, eine wertwolle Ressource darstellen, um die fundamentalen Prozesse und Prinzipien, die in lebenden Organismen involviert sind, zu verstehen. Um Rückschlüsse auf die Organisation, der Funktion und der Evolution solcher Netzwerke zu ziehen werden typischerweise sogenannte Netzwerkalignments berechnet, die Zusammenhänge zwischen zwei oder mehreren Netzwerken identifizieren. Durch den hohen technischen Fortschritt stehen immer mehr Netzwerke und Netzwerkinformationen zur Verfügung. Jedoch zeigt sich, dass die bisherigen Algorithmen schlecht bzw. teilweise gar nicht mit multiplen Netzwerken skalieren. Während dieser Arbeit wurden zwei neue Alignmentalgorithmen entwickelt, die auf multiple Netzwerke angewendet werden können. Der erste Algorithmus ist LocalAli, welcher ein evolutionsbasierter, lokaler Alignmentalgorithmus ist, mit dessen Hilfe funktional konservierte Module zwischen multiplen Netzwerken identifiziert werden können. Dabei wurde eine neue Methode entwickelt um die Evolution von funktionalkonservierten Modulen zu rekonstruieren. Der zweite Algorithmus, namens NetCoffee, berechnet globale Alignments um funktionsorientierte orthologe Gruppen zu erkennen. In der Auswertung konnte gezeigt werden, dass die beiden entwickelten Algorithmen sowohl im Sinne der Skalierbarkeit als auch der Abdeckung und der Konsistent deutlich bessere Ergebnisse liefern als die bisherigen Algorithmen. Die Testdatensätze, sowie die Anwendung und der Quellcode die innerhalb dieser Arbeit entwickelt wurden stehen unter https://code.google.com/p/localali/ und https://code.google.com/p/netcoffee/ zur Verfügung.