Herramientas Personales
Usted está aquí: Inicio / ICC / Grupos de Investigación / Kapow / Algorithms and software

Algorithms and software

Maximal repeats


  • V. Becher, A. Deymonnaz and  P. Heiber. "Efficient computation of all perfect repeats in genomic sequences of up to half a Gigabyte, with a case study on the Human genome.", Bioinformatics 25(14):1746-1753, 2009.  doi  pdf 
For the full proof of correctness and time complexity see
  • V. Becher,  A.Deymonnaz and P. Heiber. Efficient repeat finding via suffix arrays. ArXive 1304.0528
Maximal repeats in a set 
  • P. Barenbaum, V. Becher, A. Deymonnaz, M. Halsband and P. Heiber. "Efficient repeat finding in sets of strings via suffix arrays", Discrete Mathematics and Theoretical Computer Science 15(2), 2013.   DMTCS link

Extended de Bruijn words
  • V. Becher and P. Heiber. "On extending de Bruijn sequences", Information Processing Letters 111: 930--932, 2011. doi  pdf
Absolutely normal numbers in just above quadratic time
  • V. Becher, P. Heiber and T. Slaman. "A polynomial-time algorithm for computing absolutely normal numbers", Information and Computation, 232: 1--9, 2013. doi pdf
Measure of string complexity in linear time
software (run it as ./runk_onefile [alphabet size])   plotter
  • V. Becher and P. Heiber. "A linearly computable measure of string complexity", Theoretical Computer Science, 438: 62--73, 2012. doi pdf