Bonjour,
Merci pour ce cours passionnant.
J’ai une question autours de la complexité de ces algorithme. La construction d’index et d’arbre a un coût. Quel est-il ? A partir de quel moment est-ce que construire l’arbre ou l’index vaut le coup ? Comment choisit-on la longueur de l’index ?
Merci d’avance,
Cordialement
Bonjour,
Oui, la construction d’un index a un coût, variable selon l’algorithme mis en oeuvre et la taille de la donnée indexée (ici une séquence de caractères).
Cet “investissement” doit être amorti sur le nombre de requêtes exécutées ultérieurement sur cette donnée.
Il n’y a pas de réponse générique à votre question, tout à fait pertinente.
À noter tout de même que pour des chaînes de caractères utilisant un alphabet de taille constante (c’est le cas ici, on a juste A,C,G,T et un caractère de fin de chaîne) on peut construire l’arbre des suffixes en temps linéaire par rapport à la taille de la chaîne, c’est-à-dire en O(n) où n est la taille de la chaîne à pré-traiter. C’est donc une solution assez efficace asymptotiquement en nombre d’opérations élémentaires : appliquer l’algorithme sur un génome 10 fois plus grand prendra 10 fois plus de temps, pas 100 fois plus comme ce serait le cas avec un algorithme en O(n^2).
Les considérations pratiques auxquelles on est confrontées sont donc d’une autre nature que la complexité asymptotiques en nombres d’opérations élémentaires. Par exemple, il faut remarquer que l’arbre des suffixes prend beaucoup de place, autant voir plus que la chaîne initiale. Si cette chaîne est énorme, l’arbre le sera aussi. À voir si l’on peut se permettre de stocker des données aussi grandes, et si cela dégrade les performances de l’algorithme. Car même si l’on fait peu d’opérations élémentaires, un algorithme faisant peu d’opérations élémentaires peut être lent si jamais ces opérations élémentaires sont lentes, par exemple lire et écrire sur un disque dur est bien plus lent que de lire et écrire des données en mémoire RAM.
Ces considérations pratiques pointe tout particulièrement leur nez quand on manipule des données immenses : sur mon ordinateur personnel, par exemple, je peux avoir une séquences de quelques Gigabases en mémoire RAM, mais pas une séquence quelques centaines de Gigabases, qui tiendra néanmoins sur mon disque dur. Si je m’amuse à créer un arbre des suffixes d’une séquence aussi longue, je serais également obligé de le stocker sur mon disque dur, ce qui ralentira beaucoup les opérations subséquentes. C’est une des raisons pour lesquelles les laboratoires aiment avoir à leur disposition un ordinateur avec une grosse quantité de mémoire RAM, bien plus grande que dont un particulier a l’utilité.
Je laisse le soin à la communauté et aux enseignants du cours de me corriger si une bêtise s’est glissée dans ce que j’ai dit.
Cordialement,