Skip to content

GitLab

  • Menu
Projects Groups Snippets
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in
  • vidjil vidjil
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 1,697
    • Issues 1,697
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 91
    • Merge requests 91
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Monitor
    • Monitor
    • Incidents
  • Packages & Registries
    • Packages & Registries
    • Container Registry
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • vidjil
  • vidjilvidjil
  • Issues
  • #915

Closed
Open
Created Nov 29, 2016 by Vidjil Team@vidjilteamMaintainer

Calculer valeur entière d'un k-mer à partir de la précédente et non pas recalculer from scratch

non, difficile pour spaced seeds


Même dans le cas d'une graine espacée, cela peut se faire en O(1), en stockant juste un buffer plein, sans les espaces, en faisant évoluer le buffer à chaque caractère, puis en appliquant le masque qu'il faut pour avoir la valeur. On passerait de O(nk) à O(n).


kmerstore.h : getResults (rigolo, actuellement pas du tout la même implémentation pour Map et Array, pourquoi ?)

  • buffer = (buffer << 2) && xx || yy
  • kmer = buffer && zz ... mais après il reste dans kmer des trous à zéro. Enlever ces zéros n'est pas si facile et revient, dans le cas le pire, en O(k). Une autre solution est de laisser ces zéros, ce qui fait juste "gâcher" 4x d'espace par joker pour le ArrayKmerStore (et rien pour le MapKmerStore). Jouable, non ?

Mais seul un esprit supérieurement templatisé réussira à faire cela...


(et le "gâchis" est le même que celui induit par les jokers dans Aho)


kmerstore.h : getResults (rigolo, actuellement pas du tout la même implémentation pour Map et Array, pourquoi ?)

eb031bf2 et f7f1690f


branch spaced Ne marche pas encore Voir par exemple sh should-to-tap.sh multi-short-affects.should_get


@nobody

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking