A Study On Biological Networks Layout Based On Particle Swarm Optimization

Network method is an important means for the research of system biology as a whole. While mass biological data is often encoded into a form of network, visualization plays an important role in the exploration of biological networks.Layout is a key issue in biological network visualization. Currently, layout algorithms follow criteria like minimal edge crosses and graphic symmetry to achieve biological significance. However there is little quantitative evaluation for the layout effects. In addition, most of the algorithms are fairly complicated, difficult to implement, and ineffective for large-scale biological network, because they are mostly based on complex graph theory or different optimization principle.As numerical optimization is an effective means for finding reasonable good layout, this study mainly discusses the biological network layout algorithm based on PSO. The presented algorithm is simple, quick convergence, and can also be applied to large-scale network layout with the opposition-based learning strategy.The main work and innovation in the thesis are:(1) Based on the features of biological networks and visual psychological laws, the biological network layout criteria are concluded. Furthermore, two more quantitative evaluation rules in term of edge normalization and the edges cross are achieved, which can be used to evaluate layout effect.(2) The energy function of the FD algorithm is optimized based on basic PSO. Experimental data indicates that the basic PSO layout algorithm is appropriate for the different structure of small to medium-scale networks. But the basic PSO also carries some disadvantages:Firstly, the iterative process is prone to bring about boundary effects which reduce the optimal performance. Secondly, the algorithm performance declines gradually following the increment of network scale. So a clear enough layout can hardly obtained for larger networks, thus a further improvement is required.(3) Two solutions are presented for the boundary effects:first, RPSO based on the improvement of FD energy model is proposed, which reduces the probability of boundary effects significantly. Second, according to the specificities of network layout, a FPSO with free boundary is presented, which completely avoid the boundary effects. To a certain extent, these two algorithms improve the optimal performance.(4) Opposition-based learning strategy and artificial immune theory are further introduced to the algorithm to improve the applicability for larger biological network. And these two strategies can also make the algorithm get rid of local optimum, which is called IO_FPSO.