Research On Global Biological Network Alignment Based On Discrete Particle Swarm Optimization

Biological network alignment aims at identifying the similar region of different molecular interaction networks by comparative analysis. Biological network alignment is of great significance to understand the relationship of networks, identify the poorly characterized node with the help of the well-studied one and get insight into the mechanism of human disease. The network alignment problem is known to be NP-hard. For this reason, the approximate optimization method, such as particle swarm optimization, is a suitable option to address the network alignment problem. Particle Swarm Optimization(PSO) is a swarm intelligence method simulating the collaboration behavior of bird flocking. PSO has the advantage of simple implementation, fast convergence and no requirement of problem-specific information. Our main work in this thesis is that adopting the PSO method which is coupled with the characters of the biological networks to solve the network alignment problem. The main work can be concluded as follows:(1)Through our deep study of PSO theory, a discrete PSO algorithm based on 3-Opt is proposed. In this algorithm, we introduce a novel discrete particle status updating rule based on permutation to fit network alignment problem. Because the hub nodes play an important role in keeping the network structure and function, a initialization method based on node degree is introduced. Due to the swap feature of matches in the alignment, a local search operation based on 3-Opt is designed to speed up the efficiency of the algorithm. The alignment obtained by this algorithm can reach a high topological quality and a large largest common connected subgraph.(2)There are nodes with a relationship of function orthologs in different biological network. Matching the edges between networks can compensate for the matches with low node similarity in an alignment. By using these features, a strategy based on seed-and-extend is introduced to optimize the network similarity step by step. Applying this strategy into PSO, a discrete PSO algorithm based on seed-and-extend strategy is proposed to optimize the network alignment. An initialization method based on sequence similarity and a local search operation based on perturbation are introduced in this algorithm. The alignment produced by this algorithm can reach a high function consistence in biology, and can get a good balance in topological quality and biological quality.