**ReTrace example run**. Example ReTrace run for query

*m*_{1 }→

*m*_{10 }with

*k *= 3 in a database of 9 reactions and 10 metabolites. Atoms numbered from top to bottom as shown in figure. Dashed arrows indicate edges connecting

*v*_{Δ }and

*v*_{U }to atom nodes. Otherwise atom graph edges are not drawn; instead, arrows indicate substrates and products in reactions and atoms are mapped in linear fashion. For example, in reaction

*r*_{9}, atom nodes

*v*_{7,1},

*v*_{8,1 }and

*v*_{8,2 }are connected to nodes

*v*_{9,1},

*v*_{9,2 }and

*v*_{9,3}, respectively. At first,

*U *= {

*m*_{10,1},

*m*_{10,2},

*m*_{10,3}} are the unresolved nodes. Top: algorithm state after first call to Procedure FindPath. The three shortest atom paths found are

= (

*v*_{Δ},

*v*_{1,1},

*v*_{8,1},

*v*_{9,2},

*v*_{10,2},

*v*_{U}),

= (

*v*_{Δ},

*v*_{1,2},

*v*_{8,2},

*v*_{9,3},

*v*_{10,3},

*v*_{U}) and

= (

*v*_{Δ},

*v*_{1,2},

*v*_{4,2},

*v*_{7,1},

*v*_{9,1},

*v*_{10,1},

*v*_{U}), with path length ties broken arbitrarily. Choosing to process

first, the reaction set corresponding to the atom path is

*P' *= {

*r*_{3},

*r*_{8},

*r*_{9}}. Tracing back from

*v*_{U}, ReTrace finds that

*v*_{10,2 }and

*v*_{10,3 }can be traced back to

*v*_{Δ}, while

*v*_{7,1 }is added to

*U*. Procedure FindPath is then called recursively. Bottom: algorithm state after second call to Procedure FindPath. Edges to

*v*_{U }are updated to reflect

*U *= {

*v*_{7,1}}. Shortest paths from

*v*_{Δ }to

*v*_{U }are computed. However, only two paths are found:

= (

*v*_{Δ},

*v*_{1,2},

*v*_{4,2},

*v*_{7,1},

*v*_{U}) and

= (

*v*_{Δ},

*v*_{1,2},

*v*_{3,1},

*v*_{7,1},

*v*_{U}). Choosing arbitrarily

to process next, ReTrace finds out that the reaction set

*P' *= {

*r*_{2},

*r*_{6}} resolves the remaining atom in

*U *and a complete pathway {

*r*_{2},

*r*_{3},

*r*_{6},

*r*_{8},

*r*_{9}} has been discovered.

## PubMed Commons