Vous commencez votre premier job de bioinformaticien.ne. La personne précédente vous a laissé un code quasi sans commentaire et sans test, et votre chef est biologiste et n'y comprend rien. Il sait seulement que ce code était très pratique pour rechercher des k-mer dans des jeux de données. Vous allez améliorer la situation pour que l'équipe puisse se servir du code de manière pérenne.
- Décrivez à quoi sert
class SimpleBloomFilter. Ecrivez les doctests pour cette classe.
Nous avons la méthode hashes qui prend en paramètre un item et redonne la fonction de hashage de l'éléments grâce à hash_func qui va récupérer le hach, puis va être concaténé à hash_value[] qui va prendre l'indice resultant du modulo par la taille de la fonction de hachage. La class SimpleBloomFilter va permettre ensuite d'entrer dans le filtre de bloom des éléments tels que les k-mers grâce à la méthode add() en remplacant la valeur initiale 0 par 1 signifiant la présence d'un élement. Nous avons ensuite la méthode contain qui permet de verifier si un élément est bien présent dans le filtre de bloom en renvoyant la valeur 1 si il est présent ou 0 dans le cas inverse. Pour finir la méthode merge qui va permettre de combiner deux filtres de bloom en s'assurant que les deux font bien la même taille.
- Décrivez à quoi sert
class StructureNode.
Cette classe est constitué d'un constructeur uniquement avec un paramètre bloom qui est un filtre de bloom si il y en a un déjà existent sinon on prend celui crée dans la classe précédente SimpleBloomFilter(). Nous retrouvons d'autre paramètre comme left et right qui vont correspondres aux arrêtes gauche ou droite d'un arbre. Le dernier est datasets qui est une liste de donnée correspondant aux différentes feuilles. Cette classe permet donc de structurer les noeuds d'un arbre.
- Décrivez à quoi sert
class Structure. Ecrivez les doctests pour cette classe.
La classe structure se divise plusieurs méthodes. Nous avons la méthode build_tree qui est en deux étapes :
La première étape consiste à parcourir nos différents datasets et de leurs cosntruires, pour chaque dataset, un filtre de Bloom. Puis dans la même boucle, on parcour chaque kmer qui se trouve dans le dataset, et on ajoute sa valeur de hachage dans le filtre de bloom. Une fois cela fait, on stocke le filtre de bloom en tant qu'objet dans la classe StructureNode et on stocke les valeurs de dataset dans une liste. L'élément de la liste (feuille de l'arbre) va devenir donc un noeud. Et on ajoute le noeud à la liste nodes.
La deuxième étape consiste à prendre chaque élément de la liste nodes, de fusionner les filtres de Bloom et de faire d'eux des noeuds parents. Ce rpocessus est répétés jusqu'à ce qu'il ne reste qu'un noeaud.
Par la suite, on a la méthode query, qui fait appelle à la méthode query_recursive. Elle permet de rechercher le kmer dans l'arbre et dire dans quel dataset il a été retrouvé. La méthode query_récursive(), permet de parcourir de manière récursif pour vérifier la présence d'un k-mer dans l'arbre.
- Cette structure mélange donc deux structures de données que nous avons vues. Quelles sont elles ?
Dans ce code les deux structures de données vues sont les listes chainées et les arbes.
- D'après vous, que peut-on dire sur la complexité de la requête de cette structure ?
La compléxité de cette strucure est de O(log(n)) avec n qui est le nombre de datasets.
- Quelles sont les différences avec la table basée sur une MPHF que nous avons vu ?
La différence avec la PDHF est que sa complexité est de O(1). De plus le filtre de Bloom peut fournir des faux positives.
- Bonus : Pouvez-vous retracer de quel papier de bioinformatique vient cette idée ?