Fixed-Parameter Tractable Combinatorial Algorithms for Metabolic Networks Alignments

The accumulation of high-throughput genomic and proteomic data allows for the reconstruction of the increasingly large and complex metabolic networks. In order to analyze accumulated data and reconstructed networks, it is critical to identify network patterns and evolutionary relations between metabolic networks. But even finding similar networks is computationally challenging. Based on the property of gene duplication and function sharing in biological network, we have formulated the network alignment problem which asks the optimal vertex-to-vertex mapping allowing path contraction, vertex deletion, and vertex insertions. In this paper we present fixed parameter tractable combinatorial algorithms, which take into account the enzymes´ functions and the similarity of arbitrary network topologies such as trees and arbitrary graphs wit hallowing the different types of vertex deletions. The proposed algorithms are fixed parameter tractable in the liner or square of the size of feedback vertex set respectively for the case of disallowing or allowing the deletions. We have developed the web service tool MetNetAligner which aligns metabolic networks. We evaluated our results by the randomizedP-Value computation. In the computation, we followed two standard randomization procedures and further developed two other random graph generators which keep the more stringent and consistent topology constraints. By comparing their distribution of the significant alignment pairs, we observed that the more stringent constraints in the topology the random graph generator has, the more pairs of significant alignments there exist. We also performed pair wise mapping of all pathways for four organisms and found a set of statistically significant pathway similarities. We have applied the network alignment to identifying pathway holes which are resulted by inconsistency and missing enzymes. MetNetAligner is available athttp://\\alla.cs.gsu.edu:8080/MinePW/pages/gmapping/GMMain.html Two ran- - dom graph generations and the list of identified pathway holes are available online.