\HeaderA{shortestPath}{Shortest Path Analysis}{shortestPath}
\keyword{manip}{shortestPath}
\begin{Description}\relax
The shortest path analysis was proposed by Zhou et. al. The basic
computation is to find the shortest path in a supplied graph between
two Entrez Gene IDs. Zhou et al claim that other genes annotated along
that path are likely to have the same GO annotation as the two end
points.
\end{Description}
\begin{Usage}
\begin{verbatim}
shortestPath(g, GOnode)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{g}] An instance of the \code{graph} class. 
\item[\code{GOnode}] A length one character vector specifying the GO node of
interest. 
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
The algorithm implemented here is quite simple. All Entrez Gene 
identifiers that are annotated at the GO node of interest are
obtained. Those that are found as nodes in the graph are retained and
used for the computation. For every pair of nodes at the GO term the
shortest path between them is computed using \code{sp.between} from
the RBGL package.

There is a presumption that the graph is \code{undirected}. This
restriction could probably be lifted if there was some reason for it -
a patch would be gratefully accepted.
\end{Details}
\begin{Value}
The return values is a list with the following components:
\begin{ldescription}
\item[\code{shortestpaths }] A list of the ouput from \code{sp.between}. The
names are the names of the nodes used as the two endpoints
\item[\code{nodesUsed }] A vector of the Entrez Gene IDs that were both found
at the GO term of interest and were nodes in the supplied graph,
\code{g}. These were used to compute the shortest paths.
\item[\code{nodesNotUsed}] A vector of Entrez Gene IDs that were annotated at
the GO term, but were not found in the graph \code{g}.
\end{ldescription}
\end{Value}
\begin{Author}\relax
R. Gentleman
\end{Author}
\begin{References}\relax
Transitive functional annotation by shortest-path analysis
of gene expression data, by X. Zhou and M-C J. Kao and W. H. Wong,
PNAS, 2002
\end{References}
\begin{SeeAlso}\relax
\code{\LinkA{sp.between}{sp.between}}
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
library(GO)
library(RBGL)

tst <- unique(unlist(mget(c("GO:0005778"), GOENTREZID)))
set.seed(123)
v1 <- randomGraph(tst, 1:10, .3, weights=FALSE)
## Since v1 is random, it might be disconnected and we need a
## connected graph to guarantee the existence of a path.
c1 <- connComp(v1)
largestComp <- c1[[which.max(sapply(c1, length))]]
v2 <- subGraph(largestComp, v1)

a1 <- shortestPath(v2, "GO:0005779")

\end{ExampleCode}
\end{Examples}

