Study On Methods For Predicting And Aligning Metabolic Pathways

Metabolic network(metabolic pathway)is a complex system in which the metabolites are transformed via the enzyme-catalyzed reaction.The research on metabolic pathways is not only of great importance for understanding growth of the orgainisms,but is also an important issue for systems biology,pharmacology and metabolic engineering.Studying metabolic pathways with biological experiments suffers from the high cost and long duration,and it is affected by the experimental conditions,technologies and the experience of the operators.The advantages of studing metabolic pathways using computing methods are high efficiency and low cost.The computing methods can be the only way to automatically identify and analyse the huge metabolic data.The existing pathfinding methods using atom tracking require the user to define the atoms to be tracked.This may lead to failing to predict the pathways that do not conserve the user-defined atoms.The existing pathfinding methods using heuristic search require the user to define the excluding metabolites in advance.In order to find one-to-many reaction mappings between two metabolic pathways,the existing pathway alignment methods exhaustively search reaction sets during the alignment of metabolic pathways.Some existing methods reconstruct phylogenetic trees by using metabolic pathway data.These methods analyze the relations between metabolic pathways by the node mappings between pathways,and use such relations to reconstruct phylogenetic trees.However,the information of the node mappings is limited and it is difficult to get insight into the relationships between pathways depending on node mappings.This thesis focuses on studying the following three important issues by designing effective computing methods.The first one is the prediction and analysis of metabolic pathways,which searches the alternative pathways in the metabolic database.The second one is the alignment and analysis of metabolic pathways,which compares the similarity between metabolic pathways in the metabolic database to infer the unknown function of pathways and reveal similar connecting pattern of metabolic pathways.The third one is the reconstruction of phylogenetic tree by aligning metabolic pathways.This thesis proposes a novel metabolic pathway prediction method,a novel metabolic pathway alignment method and a novel phylogenetic tree reconstruction method by aligning metabolic pathways,and evaluates the experimental performance of the proposed methods.The main contributions of this thesis are as follows:(1)By tracking the movements of atomic groups and using the combined information of reaction thermodynamics and compound similarity,a pathfinding method called AGPathFinder is proposed to find biochemically relevant metabolic pathways between the start and target compounds.In AGPathFinder,we find alternative pathways by tracking the movement of atomic groups through metabolic networks and use combined information of reaction thermodynamics and compound similarity to guide the search towards more feasible pathways for users and better performance.The experimental results show that atomic group tracking enables our method to find pathways without the need of defining the atoms to be tracked,avoid hub metabolites,and obtain biochemically meaningful pathways.Our results also demonstrate that atomic group tracking,when incorporated with combined information of reaction thermodynamics and compound similarity,improves the quality of the found pathways.Compared with other existing methods,in most cases,our method performs better in terms of the average accuracy,sensitivity,positive prediction value,and F-measure of including specific compounds and reactions in the resulting pathways.Additionally,AGPathFinder provides the information of thermodynamic feasibility and compound similarity for the resulting pathways.(2)This thesis shows that connected relation between reactions can be formalized as binary relation of reactions in metabolic pathways,and the multiplications of zero-one matrices for binary relation of reactions can be accomplished in several steps.By utilizing the multiplications of zero-one matrices for binary relation of reactions,we propose an effective metabolic pathway alignment method MPBR exploiting binary relation of reactions.MPBR avoids the exhaustive search of reaction sets,efficiently obtains reaction sets in a small number of steps,and accurately uncovers biologically relevant reaction mappings.Furthermore,we propose a new measure method of topological similarity of nodes by comparing the k-neighborhood subgraphs of the nodes in aligning metabolic pathways.MPBR employs this similarity metric to improve the accuracy of the alignments.The experimental results on the KEGG database show that when compared with other state-of-the-art methods,for the same-domain and across-domains alignments of metabolic pathways,in most cases,MPBR obtains better performance in the node correctness and edge correctness with higher efficiency,returns more correct one-to-many reaction mappings,and reports the many-to-many reaction mappings.(3)A method called MMAL for reconstructing phylogeny is presented by globally aligning multiple metabolic pathways using functional module mapping.MMAL transforms the alignment of multiple metabolic pathways into constructing the union graph of the pathways.Then,by clustering the nodes in the union graph,MMAL identifies the functional modules in the pathways and builds the mappings between these modules simultaneously.MMAL determines the similarities between pathways by comparing the mapped functional modules in the pathways,and infers phylogenetic relationships among the organisms based on such similarities.The construction of union graph simplifies the global alignments of multiple metabolic pathways,and the mappings between the modules provide a way of analyzing the relations between pathways.The experimental results showed that our presented method correctly classified different organisms into the corresponding categories,and our constructed phylogenetic trees are closer to NCBI taxonomy in comparison to the trees produced by other classification methods using metabolic pathway data.