Research On Metabolic Network Alignment Algorithm Based On Index-Structures

Along with the human genome project's beginning and the modern biological technology's rapid development, the biology message data's growth presents potential of an explosion, which provided data foundation for opening the mysteries of life; The enhancement of computing capabilities and the development of the Internet provides large-scale data's storage, processing, retrieval and interpretation with a theoretical basis. But the purpose of bioinformatics is how to use the information science and computation technology's method, through the data analysis and processing, to reveal the inner link during mass data and the biology meaning, explain the structure and the functional information they contain, then extract useful biology knowledge. An important tool for analyzing biological networks is the ability to perform homology searches, which is completed through the alignment of networks. In recent years, network comparison techniques promise to take an increasing role in the field of biological research, this problem has been widely and deeply studied and many efficient algorithms are available. In recent years,with the rapid development of biological research methods, the high-throughout quantity of data increase rapidly, there is a growing need for effective and efficient graph querying methods. Due to the noisy and incomplete characteristics of these high throughout biological data and the restricted topology structures, exact graph matching algorithm have limited use and approximate graph matching methods are required.In the context, this paper present a metabolic network alignment algorithm based on index-structures, which introduce index structure into graph alignment. This paper employ a flexible model that allow for the difference of graph structure and characteristic of biological networks when we compute the similarity of query graph and database graphs. We firstly abstract the biological networks as the undirected graph and we modeled the alignment based on pathways. Next, the target graphs and query graphs are broken down into smaller fragments and we employ hierarchical filtering methods to screen them.then, the suitable candidates were assembled into bigger one and the problem is converted to find the maximal cliques. In the end, the proper result can be found. The related experiments demonstrate that our algorithm has a wider range of applicability than the previous restricted approach. So, our algorithm is effective and applicable.