Estimation of the number of extreme pathways for metabolic networks

<p>Abstract</p> <p>Background</p> <p>The set of extreme pathways (ExPa), {<b>p</b>_<it>i</it>}, defines the convex basis vectors used for the mathematical characterization of the null space of the stoichiometric matrix for biochemical reaction networks. ExPa analysis has been used for a number of studies to determine properties of metabolic networks as well as to obtain insight into their physiological and functional states <it>in silico</it>. However, the number of ExPas, <it>p </it>= |{<b>p</b>_<it>i</it>}|, grows with the size and complexity of the network being studied, and this poses a computational challenge. For this study, we investigated the relationship between the number of extreme pathways and simple network properties.</p> <p>Results</p> <p>We established an estimating function for the number of ExPas using these easily obtainable network measurements. In particular, it was found that log [<it>p</it>] had an exponential relationship with <inline-formula><m:math name="1471-2105-8-363-i1" xmlns:m="http://www.w3.org/1998/Math/MathML"><m:semantics><m:mrow><m:mi>log</m:mi><m:mo>⁡</m:mo><m:mrow><m:mo>[</m:mo><m:mrow><m:mstyle displaystyle="true"><m:msubsup><m:mo>∑</m:mo><m:mrow><m:mi>i</m:mi><m:mo>=</m:mo><m:mn>1</m:mn></m:mrow><m:mi>R</m:mi></m:msubsup><m:mrow><m:msub><m:mi>d</m:mi><m:mrow><m:msub><m:mo>−</m:mo><m:mi>i</m:mi></m:msub></m:mrow></m:msub><m:msub><m:mi>d</m:mi><m:mrow><m:msub><m:mo>+</m:mo><m:mi>i</m:mi></m:msub></m:mrow></m:msub><m:msub><m:mi>c</m:mi><m:mi>i</m:mi></m:msub></m:mrow></m:mstyle></m:mrow><m:mo>]</m:mo></m:mrow></m:mrow><m:annotation encoding="MathType-MTEF"> MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacyGGSbaBcqGGVbWBcqGGNbWzdaWadaqaamaaqadabaGaemizaq2aaSbaaSqaaiabgkHiTmaaBaaameaacqWGPbqAaeqaaaWcbeaakiabdsgaKnaaBaaaleaacqGHRaWkdaWgaaadbaGaemyAaKgabeaaaSqabaGccqWGJbWydaWgaaWcbaGaemyAaKgabeaaaeaacqWGPbqAcqGH9aqpcqaIXaqmaeaacqWGsbGua0GaeyyeIuoaaOGaay5waiaaw2faaaaa@4414@</m:annotation></m:semantics></m:math></inline-formula>, where <it>R </it>= |<it>R</it>_<it>eff</it>| is the number of active reactions in a network, <inline-formula><m:math name="1471-2105-8-363-i2" xmlns:m="http://www.w3.org/1998/Math/MathML"><m:semantics><m:mrow><m:msub><m:mi>d</m:mi><m:mrow><m:msub><m:mo>−</m:mo><m:mi>i</m:mi></m:msub></m:mrow></m:msub></m:mrow><m:annotation encoding="MathType-MTEF"> MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGKbazdaWgaaWcbaGaeyOeI0YaaSbaaWqaaiabdMgaPbqabaaaleqaaaaa@30A9@</m:annotation></m:semantics></m:math></inline-formula> and <inline-formula><m:math name="1471-2105-8-363-i3" xmlns:m="http://www.w3.org/1998/Math/MathML"><m:semantics><m:mrow><m:msub><m:mi>d</m:mi><m:mrow><m:msub><m:mo>+</m:mo><m:mi>i</m:mi></m:msub></m:mrow></m:msub></m:mrow><m:annotation encoding="MathType-MTEF"> MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGKbazdaWgaaWcbaGaey4kaSYaaSbaaWqaaiabdMgaPbqabaaaleqaaaaa@309E@</m:annotation></m:semantics></m:math></inline-formula> the incoming and outgoing degrees of the reactions <it>r</it>_{<it>i </it>}∈ <it>R</it>_<it>eff</it>, and <it>c</it>_{<it>i </it>}the clustering coefficient for each active reaction.</p> <p>Conclusion</p> <p>This relationship typically gave an estimate of the number of extreme pathways to within a factor of 10 of the true number. Such a function providing an estimate for the total number of ExPas for a given system will enable researchers to decide whether ExPas analysis is an appropriate investigative tool.</p>