\chapter{Metabolic path finding}

\section{Introduction}

% what can you do with the tool
The metabolic pathfinder enumerates metabolic pathways between a set of start nodes
and a set of end nodes, where start and end nodes may be compounds, reactions or enzymes (which are mapped to the reactions
they catalyze). When choosing the right parameters (which are set by default), the metabolic pathways found are with high
probability biochemically relevant.\\

% strategies and competing tools that deal with hub nodes
The accuracy of path finding in metabolic networks (as in other biological networks) is diminished by the presence of
hub nodes (highly connected compounds such as ATP, NADPH or CO2) in the network.
Path finding algorithms will traverse the network preferentially via the hub nodes,
thereby inferring biochemically irrelevant pathways.
Different strategies have been devised to overcome this problem. Arita introduced the mapping and tracing of atoms
from substrates to products \cite{Arita2003}. This strategy is also applied in the Pathway Hunter Tool available at http://pht.tu-bs.de/PHT/.
Other tools rely on rules to avoid hub nodes, e.g. the pathway prediction system at UMBBD (http://umbbd.msi.umn.edu/predict/).
Didier Croes et al. used weighted graphs to avoid highly connected nodes \cite{croes05},\cite{croes06}.
The functionality of Didier Croes' tool is covered by the metabolic pathfinder (with the weighted reaction network).\\

% metabolic path finder
Metabolic pathfinder relies on a mixed strategy: On the one hand, it makes use of weighted graphs to avoid irrelevant
hub nodes and on the other hand, it integrates KEGG RPAIR annotation \cite{Kotera2004} to favor for each traversed
reaction main over side compounds.
KEGG RPAIR is a database that divides reactions into reactant pairs (substrate-product pairs) and classifies the reactant
pairs according to their role in the reaction. For instance, the cofac reactant pair A00001 couples NADP+ with NADPH.
Main reactant pairs connect main compounds and should be traversed preferentially by path finding algorithms.\\

% rpair graphs
The KEGG RPAIR annotation is integrated by construction of the undirected RPAIR network, which consists of 7,058 reactant pairs,
4,297 compounds and 14,116 edges for KEGG version 41.0. Alternatively, two other networks are available: the directed reaction network evaluated in
\cite{croes06} and an undirected reaction-specific RPAIR network, in which each reaction is divided in its reactant pairs.\\

Note that in more recent KEGG versions, identifiers of reactant pairs start with RP instead of A.\\

% what will be covered in this chapter
In this chapter, we will recover the aldosterone pathway using the RPAIR and the reaction network respectively.
Note that the study case was carried out with data from KEGG LIGAND version 41.0. Results might differ for more recent KEGG versions.

\section{Enumerating metabolic pathways between compounds, reactions or enzymes}

\subsection{Study case}

Aldosterone is a human steroid hormone involved in the regulation of ion uptake in the kidney and of blood pressure.
It is synthesized from progesterone. We aim to recover the aldosterone biosynthesis pathway by providing
its start and end reaction.

\subsection{Protocol for the web server}

\begin{enumerate}

\item In the \neat  menu, select the entry \program{Metabolic path finding}.

  In the right panel, you should now see a form entitled
  ``Metabolic pathfinder''.

\item Click on the button \option{DEMO2} located at the bottom of the form.

  The metabolic pathfinder form is now filled with the start and end reaction of the aldosterone biosynthesis pathway.
  In addition, information on this pathway is displayed.

\item Click on the button \option{GO}.

\item The seed node selection table appears.

		This table lists for each reaction the reactant pair identifier(s) associated to it. Note that reaction
		R02724 is associated to two reactant pairs.\\

		The seed node selection form allows you to select the correct among all compounds matching your query string in case
		you provided a partial compound name.
		If you give KEGG compound identifiers, it displays the name of each compound. For EC numbers, it lists associated
		reactions or reactant pairs.
		The seed node selection form also warns you in case you provide problematic identifiers.

\item Click on the button \option{GO}.

  The computation should take no more than one minute.

  Then, a table is displayed, which lists the found paths in the order of their weight.
  The table may be sorted according to other criteria by clicking the respective column header.
  Each path node is linked to its corresponding KEGG entry for easy inspection of results.\\

  If you set \option{Output format} in the metabolic pathfinder form to ``Graph'', you obtain an image of the inferred
  pathway generated by the program \textbf{dot} of the graphviz tool suite and a link to the pathway in the selected graph format.

\end{enumerate}

To see how results change with the choice of the graph, you can repeat steps 1 and 2.
In the metabolic path finding form, select Reaction graph instead of RPAIR graph (which is selected by default) and
follow step 3 to 5. You will notice in the seed node selection form that the reaction identifiers are no longer mapped to
reactant pairs.

\subsection{Protocol for the command-line tools}

This section assumes that you have installed the RSAT/NeAT command line tools.

The metabolic pathfinder is a web application on top of Pathfinder.
You may run metabolic path finding on command line by launching the Pathfinder command line tool on
the RPAIR and reaction networks, which are provided in the KEGG graph repository reachable from the metabolic
pathfinder manual page.

Type the following command in one line to find paths in the RPAIR network:
	{\color{Blue} \begin{footnotesize}
		\begin{verbatim}
	java -Xmx800m graphtools.algorithms.Pathfinder -g RPAIRGraph_allRPAIRs_undirected.txt -f flat
	     -s 'A02437' -t 'A02894' -b -y rpairs
	\end{verbatim} \end{footnotesize}
	}

To repeat path finding in the reaction network, type in one line:

{\color{Blue} \begin{footnotesize}
		\begin{verbatim}
	java -Xmx800m graphtools.algorithms.Pathfinder -g ReactionGraph_directed.txt -d -f flat
	     -s 'R02724>/R02724<' -t 'R03263>/R03263<' -b -y con
	\end{verbatim} \end{footnotesize}
	}

\subsection{Interpretation of the results}

\subsubsection{Metabolic path finding in the RPAIR network}

The path of first rank does not reproduce exactly the annotated pathway. Instead, it suggests a deviation via 21-hydroxypregnelonone,
bypassing progesterone. This path might be a valid alternative, as it appears on the KEGG map for
C21-Steroid hormone metabolism in human. One of the two second-ranked paths corresponds to the annotated pathway.

First ranked path:\\
\textbf{A02437 (1.14.15.6)} Pregnenolone A03407 (1.14.99.10) 21-Hydroxypregnenolone A00731 (1.1.1.145, 5.3.3.1) 11-Deoxycorticosterone A03469 (1.14.15.4) Corticosterone A02893 (1.14.15.5) 18-Hydroxycorticosterone \textbf{A02894}

Second ranked paths:\\
\textbf{A02437 (1.14.15.6)} Pregnenolone A00386 (1.1.1.145, 5.3.3.1) Progesterone A02045 (1.14.99.10) 11-Deoxycorticosterone A03469 (1.14.15.4) Corticosterone A02893 (1.14.15.5) 18-Hydroxycorticosterone \textbf{A02894}\\

\textbf{A02437 (1.14.15.6)} Pregnenolone A00386 (1.1.1.145, 5.3.3.1) Progesterone A02047 (1.14.15.4) 11beta-Hydroxyprogesterone A03467 (1.14.99.10) Corticosterone A02893 (1.14.15.5) 18-Hydroxycorticosterone \textbf{A02894}

\subsubsection{Metabolic path finding in the reaction network}

The paths of first and second rank traverse a side compound, namely adrenal ferredoxin. None of these paths is therefore biochemically valid.
In the weighted reaction graph all highly connected side compounds such as ATP and water are avoided. However, adrenal ferredoxin
is a rare side compound, thus weighting is not sufficient to bypass it.

First ranked path:\\
\textbf{R02724$<$} Reduced adrenal ferredoxin R03262$>$ 18-Hydroxycorticosterone \textbf{R03263$>$}

Second ranked paths:\\

\textbf{R02724$>$} Oxidized adrenal ferredoxin R02726$<$ Reduced adrenal ferredoxin R03262$>$ 18-Hydroxycorticosterone \textbf{R03263$>$}\\

\textbf{R02724$>$} Oxidized adrenal ferredoxin R02725$<$ Reduced adrenal ferredoxin R03262$>$ 18-Hydroxycorticosterone \textbf{R03263$>$}

\section{Summary}

Metabolic path finder provides k shortest path finding in metabolic networks constructed from KEGG LIGAND and KEGG RPAIR.
The metabolic path finder is coupled with a mirror of the KEGG database to allow quick identification of partial compound
names and to annotate results.

\section{Strengths and Weaknesses of the approach}

\subsection{Strengths}
The metabolic path finder has the following benefits compared to other metabolic path finding tools:
\begin{enumerate}

\item It has been extensively evaluated on 55 reference pathways from three organisms.

\item It supports compounds, reactions, reactant pairs and EC numbers as seed nodes.

\item It can handle sets of start and end nodes.

\end{enumerate}

\subsection{Weaknesses}
The metabolic path finding tool has the following weaknesses:

\begin{enumerate}

\item RPAIR does not cover all compounds in KEGG. Thus, the RPAIR network is less comprehensive than the reaction network.

\item By default, the metabolic path finder cannot infer directions of reactions in pathways because of
the way the networks were constructed (being undirected or treating all reactions as reversible).
However, custom metabolic networks may contain irreversible reactions and
it is therefore possible to infer directed pathways from custom networks.

\item The metabolic path finder can only partly infer cyclic pathways or pathways in which the same enzymes act repeatedly on a growing chain.

\end{enumerate}


\section{Troubleshooting}

\begin{enumerate}

\item A \textbf{Parameter error} occurred.

	By default, the optimal parameter values are set. However, if you set your own values, they might not
	be in the supported value range. Check the Metabolic path finder manual.

\item The seed node selection form displays the message: "You provided invalid identifier(s)!"

     This occurs when you provide identifiers that do not match any KEGG identifier, EC number or KEGG
     compound name. Check your identifiers or in case you provided a compound name, check whether the
     compound is present in KEGG.

\item The seed node selection form displays the message: "The given compound is not part of the sub-reaction graph."

     As stated in the Weaknesses section, the RPAIR network does not contain all KEGG compounds due to incomplete
     coverage of the RPAIR database. Try to search paths for this compound in the reaction network.

\item No path could be found.

	This may happen in the RPAIR network because in this network reactant pairs belonging to the same reaction
	exclude each other. Try the reaction-specific RPAIR network or the reaction network instead.

\item An out of memory error occurred.

 	This may occur when requesting a large number of paths with the reactant subreaction and compound weighting schemes
 	set to unweighted. In general, when setting the weighting schemes to unweighted, biochemically irrelevant paths
 	will be returned. Use another weighting scheme or reduce the number of requested paths to avoid this error.

\end{enumerate}







