Calcul efficace d'un minimizer : par Aho ?
Ce qui est dans !76 (merged) pour #2643 (closed) fonctionne : kaa.minimize(const KmerAffect &affect, int margin, int width)
retourne la position (hors de margin
sur les bords) tel que le k-mer de longueur width
soit minimal (maximal en fait). Idéalement on n'aimerait pas avoir de paramètre width
, juste minimize(const KmerAffect &affect, int margin)
.
Mais le code actuel est trivial, c'est du O(n * width)
, et on utilise tools.dna_to_int
(qui ne sert pas ailleurs, c'était une tentative il y a longtemps..., dev-dead-code ?). Si on se met à faire cela pour chaque read reconnue par SEG_METHOD_ONE (par exemple des CDs dans du RNA-seq #1801), c'est perdu.
Il y a sûrement des moyens de faire O(n)
... voir #915 (closed) ?
@mikael-s, ne serait-ce pas possible, de coder simplement et efficacement minimize
? Par exemple l'état final avec affect
telle que son adresse mémoire soit minimale ? Si on joue avec cela, serait-ce reproductible d'un lancer à l'autre ? Si non reproductible, stocker un autre int
dans chaque état d'Aho sur lequel on trie ?