MP-Align: alignment of metabolic pathways

Abstract

Background: Comparing the metabolic pathways of different species is useful for understanding metabolic functions and can help in studying diseases and engineering drugs. Several comparison techniques for metabolic pathways have been introduced in the literature as a first attempt in this direction. The approaches are based on some simplified representation of metabolic pathways and on a related definition of a similarity score (or distance measure) between two pathways. More recent comparative research focuses on alignment techniques that can identify similar parts between pathways.

Results: We propose a methodology for the pairwise comparison and alignment of metabolic pathways that aims at providing the largest conserved substructure of the pathways under consideration. The proposed methodology has been implemented in a tool called MP-Align, which has been used to perform several validation tests. The results showed that our similarity score makes it possible to discriminate between different domains and to reconstruct a meaningful phylogeny from metabolic data. The results further demonstrate that our alignment algorithm correctly identifies subpathways sharing a common biological function.

Conclusion: The results of the validation tests performed with MP-Align are encouraging. A comparison with another proposal in the literature showed that our alignment algorithm is particularly well-suited to finding the largest conserved subpathway of the pathways under examination.

Figure 1

Part of the KEGG pathway Arginine and proline metabolism for H. Sapiens. This figure shows the compounds and enzymes directly involved in the Urea cycle.

Figure 2

Hypergraph representation of the Urea Cycle shown in Figure 1. Purple nodes represent compounds and grey nodes are hyperedges representing reactions. They specify the catalyzing enzyme as an attribute. For each reaction, the incoming arrows represent the input compounds and the outgoing arrows represent the output compounds. Note that a reversible reaction (e.g. reaction R00557) is represented by a forward reaction (grey node with label R00557) and a backward one (grey node with label R00557rev).

Figure 3

Two-dimensional projections of the Glycolysis pathways of all organisms in the KEGG database (left) and all organisms up to Bacteria (right). Red points correspond to Animals, green points to Archaea, yellow points to Fungi, pink points to Plants, black points to Protists and blue points to Bacteria. Note that in the projection on the left, Bacteria appears in the whole Glycolysis universe. By removing Bacteria, we can observe, on the right, that Protists are scattered throughout the whole space while Archaea are clearly separated from Animals, Plants and Fungi.

Figure 4

Dendrograms of the hierarchical clustering with partitions into 3 (top left), 8 (top right), 12 (bottom left) and 19 (bottom right) clusters for the Glycolysis pathways of all Animals in the KEGG database.

Figure 5

Dendrogram of the hierarchical clustering with partition into 3 clusters for the Glycolysis pathways of all Animals in the KEGG database having a connected Glycolysis pathway.

Figure 6

NCBI taxonomy of the eight organisms considered (left) and phylogenetic reconstruction obtained by MP-Align using the average score (right).

Figure 7

Phylogenetic reconstruction obtained by MP-Align for the Glycolysis pathway (top left) and for randomly chosen subsets of the common pathways of the selected organisms: 10 pathways (top right), 20 pathways (bottom left) and 30 pathways (bottom right).