Global Biological Network Alignment By Using Memetic Algorithm

High-throughput experimental screening techniques and computer technology have resulted in a large number of biological data, among which protein-protein interactions(PPI) data is one of the most important parts. These data make it possible to analyze the life process from a system perspective. Protein-protein interactions data are usually abstracted as network model for analyzing. And network alignment is one of the comparative analysis methods for analyzing biological networks. Research on PPI networks can identify conserved subgraphs and help us to understand evolutionary trajectories across species. Some evolutionary algorithms have been proposed for coping with PPI network alignment, but most of them are limited by the lower search efficiency due to the lack of the priori knowledge.In this thesis, we propose a Memetic algorithm, denoted as Me Align, to solve the biological network alignment problem. Me Align algorithm takes the advantages of two-step algorithms. It first uses priori knowledge to build a coarse similarity score matrix and this score matrix is conducted to generate an initial population. The local search algorithm absorbs the essential idea of seed-and-extend method and an effective local search operator based on specific neighborhoods is designed. The operator first defines the neighborhood space of a single network node and then search the neighborhood space to find nodes that contribute to the optimized model. In order to comprehensively analyze PPI network alignment problem and to prove the effectiveness of the local search operator in Me Align, this thesis includes two main clues:1) Select two different network optimization models to show the influence of an optimization model on alignment results. Me Align is first used to optimize the topological similarity model of the input networks only and the deficiency of this model is pointed out by analyzing the alignment results. Later then, Me Align optimizes a weighted model that consists of network topology and node sequence similarities. Finally, the alignment results of these two different model are compared and draw a conclusion that the weighted model is better than the topological-only model.2) Me Align algorithm is compared with some classical algorithms in this field to show its effectiveness when the two different model is optimized. Especially, Me Align algorithm is compared with MAGNA and MAGNA++ in detail. MAGNA and MAGNA++ are accomplished by genetic algorithm and it can prove the effectiveness of the local search operator in Me Align when compared to them.