Universität Bremen  
  Universität Bremen FB3 TZI BISS  
  AG BS >
 

Blagoy Genov
 

Software

Addibit is Another Double Description Implementation with BInary Trees. It supports the following adjacency test variants:
  • combinatorial test using bit pattern trees [1,2] (bp-trees),
  • combinatorial test using bit pattern trees and query bits neutralization (bp-qbn-trees),
  • combinatorial test using vantage point trees [3] (vp-trees),
  • algebraic test using the Gauss elimination method, and
  • algebraic test using active set partitioning.
The current version is 0.3.0 (alpha) which may (and surely does) contain a lot of bugs. Check the README-file for instructions of how to compile and run the program. For an overview of the double description method, we refer to [4]. Here is a small study comparing the performance of the different combinatorial test variants.
The archive package contains statically compiled versions of the noncommercial tools four-ti-two, cddr, polco, porta, ppl, skeleton and lrs. Using the script benchmark.sh, you can run addibit and the other tools on a set of arbitrary problems. Prepared problems can be found in the archive (see folder experiments).
[1] M. Terzer and J. Stelling. Accelerating the computation of elementary modes using pattern trees. In Proceedings of the 6th international conference on Algorithms in Bioinformatics, WABI '06, pages 333-343, Berlin/Heidelberg, 2006. Springer-Verlag. [ bib ]
[2] M. Terzer and J. Stelling. Large-scale computation of elementary flux modes with bit pattern trees. Bioinformatics, 24:2229-2235, 2008. [ bib ]
[3] Peter N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, SODA '93, pages 311-321, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics. [ bib ]
[4] K. Fukuda and A. Prodon. Double description method revisited. In Combinatorics and Computer Science, volume 1120 of Lecture Notes in Computer Science, pages 91-111. Springer-Verlag, Berlin/Heidelberg, 1996. [ bib ]

Address:

 
        Dipl.-Inf. Blagoy Genov
E-mail: bgenov@informatik.uni-bremen.de
 
   
Author: bgenov		  
  AG BS 
Last updated: May 23th, 2014   Impressum