Biological Network Alignment And Its Application In Disease

The protein-protein interaction(PPI)network contains important biological informa-tion and has an increasing influence on molecular biology.For example,protein function and PPI network evolution can be predicted by extracting the information from the PPI network.Understanding the details of the interaction can provide a reference for the study of diseases and drug targets.At present,the researches based on PPI network mainly include PPI network alignment and related researches based on PPI network.Network alignment is widely used to predict protein functions,identify conserved func-tional modules,and study the evolutionary relationship of species.However,network alignment is an NP-complete problem,and most algorithms are usually slow or less ac-curate when aligning large networks.Therefore,it is necessary to develop an efficient network alignment algorithm.On the other hand,human diseases should be viewed as perturbations of highly connected cellular networks,that is,diseases are not independent of each other,but highly related.We call related diseases as comorbidities.Identifying comorbidities can provide references for understanding disease progression and explor-ing treatment options.The PPI network has been widely used to assess the connection between diseases.In this dissertation,we focus on the PPI network alignment algorithm and the disease correlation research algorithm based on the PPI network.The main contents are arranged as follows:In Chapter 1,we mainly introduce the research background,status and significance of this thesis.In Chapter 2,we have proposed a fast yet accurate method—NAIGO.Specifically,this method first divided the networks into subnets taking advantage of the known prior knowledge,such as gene ontology.For each subnet pair,it transforms the alignment into a target optimization problem by considering both protein orthologous information and their local structural information.After that,this method expands the obtained subnet alignments in a greedy manner locally and globally,then the more biologically meaningful local and global alignment can be obtained.We applied NAIGO to align Human and Saccharomyces cerevisiae S288c PPI network and compared the results with other popular methods like IsoRank,GRAAL,SANA and NABEECO.As a result,our method outperformed the competitors.In Chapter 3,We have proposed and compared 10 PPI-based computational methods to study the connections between diabetes and other diseases,obesity and cancers,among which DIconnectivity-eDMN performs the best.DIconnectivity-eDMN first maps genes in a BP into the PPI network to construct a BP-related subnet,which is expanded(in the whole PPI network)by a random walk with restart(RWR)process to generate a so-called expanded modularized network(eMN).In addition,a RWR process is also performed to generate an expanded disease-related gene list.For each disease pair,their expanded disease-related genes are mapped onto eMNs,and the association between them is measured by the weighted interaction numbers of gene sets on all eMNs.The DIconnectivity-eDMN method can not only predict the connection of diseases,but also reveal important biological processes that connect diseases.The network alignment algorithm and disease connection algorithm proposed in this dissertation have been successfully used on PPI network,but the application of these two algorithms is not limited to PPI network,they can also be extended to other types of biological networks.