Forum Linux.général grep et recherche approximative

Posté par  . Licence CC By‑SA.
Étiquettes : aucune
3
7
août
2019

Bonjour à tous,
Je suis nouveau sur ce forum car je rencontre un problème pour lequel je n'ai pas trouvé de solution sur internet…
Je travaille sur des séquences d'ADN, mais elle sont traitées ici comme du texte avec un alphabet de seulement 4 lettres A, T, G et C. Parmi les millions de séquences obtenues, je recherche celles qui ont un motif très particulier (par exemple CTAAACAGTCTTTTTTT). Avec grep, pas de soucis, j'arrive à extraire ce qui m'intéresse, mais il se trouve que le séquenceur fait parfois des erreurs et je voudrais permettre de retrouver les séquences qui pourraient avoir 1 ou 2 lettres de différent, mais pas plus…
J'ai cherché dans les options de grep, je n'ai rien trouvé qui puisse m'aider. J'ai pensé aux expressions régulières, mais je débute et je ne vois pas comment faire.

Est ce que quelqu'un à une petite idée ? Je sais que Awk peut faire pas mal de chose pour la manipulation de texte, est ce vous pensez que ça pourrait le faire ? (Mais là encore, je suis totalement débutant…)

Merci d'avance si quelqu'un à une piste pour m'aider !

  • # Tu peux utiliser les distances

    Posté par  . Évalué à 2.

    Salut,

    selon moi deux séquences avec 1 ou 2 lettres de différence sont proches de part leur distance : https://askubuntu.com/questions/753608/is-there-any-program-for-fuzzy-string-matching-which-provides-a-match-score

    Après il va te falloir boucler sur tout ton fichier pour extraire chaque motif de même longueur que la séquence que tu cherches, pour les comparer.

    • [^] # Re: Tu peux utiliser les distances

      Posté par  . Évalué à 1.

      Merci Cappir
      cependant, si j'ai bien compris ton lien, ça ne pourra pas me servir, car je n'ai pas été assez clair dans ma demande: la séquence que je recherche fait bien une 15aine lettres (nucléotides en langage biologiste ;) ), mais je la cherche dans des séquences qui peuvent être longues de quelques centaines à quelques milliers de nucléotides…

      • [^] # Re: Tu peux utiliser les distances

        Posté par  . Évalué à 1.

        Ok du coup je dirais que rechercher une nucléotide dans une séquence équivaudrait à rechercher un mot dans une phrase.

        Si je voulais rechercher "nucléotides" dans ta phrase précédente j'essaierais de comparer "nucléotides" (11 caractères) à tous les sous-textes de 11 caractères de ta phrase : "cependant, " puis "ependant, s" puis "pendant, si" etc.
        C'est la boucle dont je parlais.
        Et quand je dis "comparer" c'est calculer la distance.

        Qu'en penses-tu ?

        • [^] # Re: Tu peux utiliser les distances

          Posté par  . Évalué à 1.

          Oui, ce serait ça !
          A tester donc, mais ça s'annonce un peu chaud, je suis loin d'être un spécialiste. je vais donc regarder ton lien un peu plus en détail pour voir comment mettre ça en œuvre !

  • # pas de shell...

    Posté par  . Évalué à 4.

    Désolé, mais je doute fortement que les outils UNIX traditionnels permettent de faire ça… surtout vue la longueur des séquences dont tu parles, ça risque d'être très lent.

    Par contre, depuis que je connais Debian, j'ai toujours été sidéré par le nombre d'outils qui, justement, semblent traiter des séquences ADN. Les debtags, qui sont incomplets, mentionnent une centaine de paquets pour la biologie. Je trouve le nombre étonnamment faible, mais bon: les debtags sont incomplets.

    Je ne connais bien entendu rien à ce domaine, mais par exemple, le paquet "acedb-other" est ainsi décrit par aptitude:

    Description-fr: Récupération d'ADN ou de séquences de protéines
     Ce paquet rassemble toutes les petites applications qu'acedb regroupe sous
     la cible « other » de son Makefile.
     .
     efetch: vraisemblablement le raccourci pour « entry fetch » (collecteur
     d'entrées en base de données), assemble les informations de séquence des
     principales bases de données d'ADN et de protéines.
    

    Si ta distro est dérivée de Debian, tu peux par exemple utiliser la commande suivante pour avoir un aperçu des paquets liés à l'ADN:

    grep '^[^ ].*ADN' /var/lib/apt/lists/deb.debian.org_debian_dists_stable_main_i18n_Translation-fr -B2 | grep Package | cut -f2 -d:
    

    Probable qu'il existe de meilleures solutions pour chercher un paquet dont la description ou le nom contiens le terme ADN, mais le but ici est de demander surtout: as-tu vérifié si dans ces paquets l'un ne fait pas déjà le boulot? Si la seule différence est une question de format, on peut peut-être t'aider à réaliser un outil de conversion.

    • [^] # Re: pas de shell...

      Posté par  . Évalué à 1. Dernière modification le 07/08/19 à 16:17.

      Merci freem,
      Oui, il y a une pelleté de logiciels pour la bio-informatique (dont le traitement de séquences d'ADN). Il y a même des logiciels qui ont été développés pour faire exactement ce que je veux faire, mais je ne suis pas content du résultats avec mes séquences et j'obtiens de bien meilleurs résultats avec grep… sauf que je pourrais encore avoir un peu mieux en tolérant un petit pourcentage d'erreur, d'où ma demande finalement :)
      Idéalement, il faudrait que je développe mon propre outils, mais je n'ai pas encore la compétence pour ça je pense.
      En tout cas merci ! je continue de chercher !

      • [^] # Re: pas de shell...

        Posté par  . Évalué à 4.

        Par curiosité, quels logiciels bioinfo as-tu essayés pour dire que grep est plus puissant pour faire ce que tu veux ?

        A vue de nez, j'aurais rapidement utilisé un outil d'alignement local genre blast, blat et dérivés qui sont optimisés pour la recherche de bouts de séquences par alignement local ou tout autre logiciel implémentant l'algo de Swith et Waterman (qui sera d'ailleurs potentiellement plus précis mais plus lent que les heuristiques de blast ou blat - en passant, l'algo est assez simple à coder si tu veux l'implémenter).

        Ils font a peu près ce que te suggèrent d'ailleurs certains posts pour chercher ton motifs et ses approximations sur la base contenant l'ensemble de tes séquences.

        https://fr.wikipedia.org/wiki/Basic_Local_Alignment_Search_Tool
        https://en.wikipedia.org/wiki/BLAT_(bioinformatics)
        https://fr.wikipedia.org/wiki/Algorithme_de_Smith-Waterman
        https://www.ensembl.org/Help/Faq?id=429
        https://sequencebase.com/smith-waterman-vs-blast/

        Il faut bien paramétrer le logiciel pour favoriser ce que tu cherches coté motif et nombre d'erreurs autorisées (favoriser/pénaliser les mistmatches, les gaps etc).
        Il faudra un peu scripter pour extraire les séquences pertinentes de tes alignements finaux selon le pourcentage de similarité et leur longueur.

        Je ne critique pas l'idée de te servir de grep/agrep/awk/sed et consorts, je les utilise pour fouiller des séquences tout les jours mais les logiciels spécialisés sont quand même plus puissants à grande échelle.

        • [^] # Re: pas de shell...

          Posté par  . Évalué à 1.

          Apparemment, tu t'y connais en bio-info, donc je peux être un peu plus précis :
          J'ai des données de séquençage NGS issues de séquençage MinION (connu pour faire beaucoup d'erreur) et je dois retirer les adaptateurs et démultiplexer mon fichier. Pour ça, j'ai essayé des logiciels dédiés (Cutadapt, Trimmomatic, Sabre, Barcode splitter…), mais j'ai du mal a retrouver mes barcodes (la fameuse séquences de 10 nucléotides), et ça marche carrément mieux avec un simple grep, mais sans pouvoir introduire de tolérance dans les mismatches.

          • [^] # Re: pas de shell...

            Posté par  . Évalué à 3.

            Ah ouais, pas cool si tu as du mal à retrouver tes barcodes.
            Tu veux donc démultiplexer tes reads… ma réponse précédente est un peu à coté de la plaque alors :)

            Je suis plutôt du coté séquençage court (avec effectivement avec moins d'erreurs - on autorise en général une seule base en simple index) et je n'ai pas d'expérience récente avec les techno long reads. Du coup, pas trop à la page et pas trop sûr de pouvoir t'aider précisément.

            D'un point de vue méthodo, je dirais qu'on nettoie les séquences après le démultiplexage : on risque de perdre des index (à moins que ce soit recommandé dans le cas des longs reads). Les outils que tu cites permettent de faire les deux en une seule passe (je connais cutadapt et trimmomatic) mais je ne m'en suis jamais servi pour démultiplexer.

            Nanopore ne fournit pas une suite logicielle par défaut pour ses séquenceurs (ou bien ce n'est qu'avec leur partie serveur maison à base de GPU) ?

            Par curiosité, je viens de faire un petit tour rapide coté biblio et howto sur le net pour la techno nanopore.

            Les recherches renvoient rapidement vers le populaire https://nanoporetech.com/resource-centre/deepbinner-demultiplexing-barcoded-oxford-nanopore-reads-deep-convolutional-neural vendu pour être très sensible -> https://github.com/rrwick/Deepbinner (le readme donne pas mal de pistes notamment en couplant deepbinner avec un second demultiplexeur). Par contre, il a l'air d'être assez lourd à faire tourner et à des prérequis sur les formats d'entrée et les index utilisés.

            Il semble aussi avoir plein d'autres softs de demultiplexage pour les nanopore (liste non exhaustive) :

            L'utilisation ds index customs semblent parfois être un frein pour l'utilisation de certains de ces démultiplexeurs… A voir si c'est le cas dans tes échantillons.

            Un tuto de Nanopore cite aussi albacore https://denbi-nanopore-training-course.readthedocs.io/en/latest/basecalling/basecalling.html (mais si j'ai bien compris, il faut le récupérer avec un compte chez Nanopore)

            En as-tu essayé certains, as-tu regardé les paramètres (en général, on peut en général augmenter le taux d'erreurs autorisé dans les index) ?

            Sinon, d'expérience (et encore une fois surtout en short reads et en séquençage plutôt profond), autoriser trop d'erreurs dans les index n'aide pas forcément pour l'analyse secondaire des séquences.
            Si tu restes le plus strict possible, tu as vraiment beaucoup de séquences non reconnues ? Si oui, ce qu'il te reste n'est pas suffisant pour la suite de tes travaux ?.

            • [^] # Re: pas de shell...

              Posté par  . Évalué à 1.

              Normalement, le MinION fait 10% d'erreur (oui, une base sur 10… Si tu es un habitué d'Illumina, c'est à ce moment que tu dois crier au scandale…), donc sur un barcode de 10 nucléotides, on devrait s'attendre a retrouver 90% des données. En pratique, avec grep, j'arrive a retrouver environ 50% de mes reads. Et beaucoup moins avec les outils dédiés que j'ai cité (ou que tu as cité et que j'ai testé aussi).
              Après, effectivement, il reste pas mal de données, et ça assemble a priori mieux avec peu de données à vrai dire, mais il y a toujours le risque de passer à côté de séquences très faiblement représentées, et c'est souvent celles-ci qui nous intéresse le plus.

              Quant aux outils que tu cites (Porechop, Albacore), il sont adaptés aux barcodes Oxford nanopore, et du coup, pas utilisable dans mon cas, car j'ai fais le choix d'utiliser mes propres barcodes pour économiser 600€. Mais honnêtement, d'après ce que j'ai vu, je ne suis pas sur que j'aurai obtenu de meilleurs résultats avec les barcode ON…

              • [^] # Re: pas de shell...

                Posté par  . Évalué à 2.

                Je vais pas crier au scandale, c'est l'ordre de grandeur connu pour les long reads, mais bon, la finalité n'est pas la même en général et les erreurs dans la séquence utile sont normalement corrigeables par l'assemblage.

                Donc les barcodes customs font galérer un peu.
                Dans ce cas, quitte à bricoler, pourquoi ne pas générer pour chacun de tes barcodes customs une liste de séquences dégradées (ou regex un peu sioux si tu restes sur grep ou agrep comme déjà cité) - à toi de fixer d'erreurs max, de les assigner à l'échantillon et de refaire tourner démultiplexeur ou grep en mode strict. Tu devrais ainsi attraper des reads en plus à associer à tes échantillons.
                En plus cela te permettra de contrôler que chacun des barcodes avec des erreurs restent bien des identifiants uniques de séquences.

                A coté de ça, tu semble trouver que le taux d'erreurs dépasse largement les 10 % : ton séquençage est-il considéré comme de bonne qualité par le séquenceur/ logiciels de qc ?
                Si ce n'est pas le cas, c'est peut être normal que tu ais des difficultés à retrouver toutes tes barcodes.

            • [^] # Re: pas de shell...

              Posté par  (site Web personnel) . Évalué à 2.

              Ce commentaire devrait être promu en dépèche : « Séquencer profond pour les nuls ».

  • # Jeux de lettres

    Posté par  . Évalué à 4.

    Les joueurs de Scrabble ou de mots croisés ont des tripotées d'outils (parfois même en ligne) pour les aider. Ce serait peut-être une piste à creuser ?

    Sinon si tu veux coder ton propre outil, on peut te conseiller sur l'algorithme, voire te coder un petit truc. J'ai déjà ma petite idée : fenêtre glissante, à chaque étape on compte le nb de différences avec le motif recherché… bourrin mais efficace !).

    En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.

    • [^] # Re: Jeux de lettres

      Posté par  . Évalué à 1. Dernière modification le 12/08/19 à 13:48.

      Oui, c'est un peu ce que proposait cappir je crois. Je n'ai pas encore eu le temps de me pencher la dessus, mais ça semble être une piste intéressante.
      Merci !

  • # agrep

    Posté par  . Évalué à 10.

    Agrep devrait faire ce que tu veux. Sous Debian, le paquet c'est tre-agrep.

    • [^] # Re: agrep

      Posté par  . Évalué à 1.

      Mais oui, ça semble être ça !!
      Je ne vais pas pouvoir le tester immédiatement car il n'est pas installé sur la plateforme que j'utilise, mais je vais demander son installation !
      Merci Tetraf !

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.