Partial enumeration of extreme rays in metabolic networks using bit pattern trees.

Extreme ray analysis of metabolic networks, even though very powerful, is currently limited to smaller metabolic networks. Some approaches to generating partial sets of extreme rays exist, but the computational efficiency of the so-called double-description method is yet to be exploited. Previous work highlighted the possibility of sampling within its iterations, enabling partial enumeration for double-description based methods. However, these approaches severely lack computational efficiency to be a suitable alternative. In this work, the highly efficient bit pattern trees are used within the sampling framework to significantly enhance its output and speed. Combined with the recent revision of the Canonical Basis Approach (CBA), our approach outperforms the other tested methods under the reported benchmark conditions even for a full enumeration study, requiring only half the computation time. In addition, a filter setting allows the memory demand to be scaled down while retaining high efficiency. However, some issues with the combinatorial explosion of candidates still persist and are further investigated. This study therefore puts forward a novel, double description-based alternative to partial enumeration of extreme rays. Further improvements in memory efficiency would allow this promising approach to scale powerful extreme ray-based analyses to genome-scale metabolic networks.