Research Of Global Alignment Of Paired Biological Networks Based On Functional Module Detection

With the rapid development of high throughput technology,more and more human biological information has been fully mined to form a biological network,and more and more attention has been paid to the research of bioinformatics.Proteins are necessary components for the normal operation of organisms.By aligning protein interactions between different species,knowledge transfer between species can be realized,protein complex prediction,protein function prediction,biological pathway detection,and so on.The data scale of biological network alignment is relatively large.In order to obtain superior alignment results in a more efficient way,this thesis uses functional module detection and seed-and-extend methods to achieve network alignment.In the process of network alignment,the calculation of the similarity between proteins is an important link,which can lay a good foundation for the follow-up alignment.Generally,the similarity between proteins is considered from the perspectives of sequence and topology,but due to the presence of noise in the network,and the sequence information is calculated from the biological system through technical means,there is incompleteness,so only considering the topology or sequence information may lead to misleading alignment,and sequence similarity does not mean functional similarity.This thesis proposes solutions to these two problems: combining sequence information with topological information to reduce the impact of noise and incomplete sequence information on network alignment;Due to the highly modular characteristics of biological network,functional module detection can be integrated into the network alignment,and functional information can be added into the alignment,which makes up for the lack of sequence information and improves the efficiency of alignment.This thesis mainly studies the global alignment of pairwise network,combining functional module detection and network alignment to optimize the network alignment.The main research contents are as follows:(1)In order to improve the efficiency of the seed-and-extend method and the results of alignment,a pairwise network alignment algorithm based on module matching,JAlign algorithm,is proposed,which combines functional module detection with seed screening.If seed nodes are selected only according to the objective function,the lack of functional information will result in the lack of functional similarity between nodes,which will affect the prediction of protein function.JAlign algorithm combines module detection with seed-andextend,uses hierarchical clustering to detect functional module,and selects seed nodes from the module according to the objective function,comprehensively evaluates the topology structure similarity of neighbor nodes,degree and node total similarity,iteratively selects the optimal neighbor nodes for extension alignment,and carries out follow-up alignment for the other nodes that cannot be extended to.Experiments show that the JAlign algorithm makes full use of the topology information of nodes and can achieve a good balance between topology and biological mass.(2)The modules extracted in the detection of functional modules may overlap.In order to make full use of the topological and functional features between modules,this thesis combines the detection of functional modules with the construction of objective functions,and proposes a pairwise network alignment algorithm based on module features and biological information,the Mo Align algorithm.If the same node pair is repeatedly aligned in multiple module pairs,it indicates that this node pair has a high similarity.The Mo Align algorithm first calculates the module similarity according to the module division,associates the module similarity to the similarity of the node,and overlaps the module similarity of the node pairs that are repeatedly aligned.It compares some important nodes in a greedy manner,and uses the Hungarian algorithm to compare the elite part of its neighbor nodes,and finally uses the seed-and-extend method to optimize the alignment.Experiments show that the Mo Align algorithm makes full use of module information and improves the efficiency of the algorithm while obtaining more homologous proteins.(3)The application of network alignment.In this thesis,the pairwise network alignment algorithm,JAlign algorithm,is applied to the two networks of methanogens in the metabolic network in a purely topological manner,namely the MKA(Methanopyrus kandleri)network and MAC(Methanosarcina acetivorans).Through alignment and analysis of the differences in their metabolic pathways,the reasons for the thermophilicity of methanogens are revealed,thereby verifying the application of network alignment in analyzing the functional differences of species.