Discussion :

[fuyo2004]

Bonjour à tous,

je me lance dans un petit projet qui porte sur la recherche de séquences d'ADN qui se répètent autour d'un gène identifié. Prenons tout de suite un petit exemple ça sera plus simple.

Supposons que j'ai le jeu de données suivant :

attcg ttttttt gcaata ccatg
attcg ttttttt ac tagggc
attcg ttttttt tacc
tacc ggcta ttttttt
gtaatcggta ggcta ttttttt
attcagc ggcta ttttttt
tacggacgccga ggcta ttttttt
tacaaagacagcg ggcta ttttttt
gacc at aggc gatt attca gattc catc ttttttt
gacc at aggc gatt attca gattc atgg ttttttt
accg at gg ca ttttttt
accg at agc ccc ttttttt at gcac agt
accg at gat aat ttttttt gaccctagacg
accg gg gat ttga ttagccga agg ttac ttttttt
accg gg gat ttga ttagccga agg acatg ttttttt

J'ai donc des lignes d'ADN composées de séquences (une séquence est une suite de lettres séparée d'une autre suite de lettres par un espace). La séquence ttttttt est mon gène d'intérêt. En regardant rapidement le jeu de données, on s'aperçoit que certains motifs de séquences se répètent autour de mon gène :

- Par exemple, sur les trois premières lignes, la séquence attcg précède immédiatement mon gène.
- Sur les deux dernières lignes, les séquences "accg gg gat ttga ttagccga agg" précèdent une séquence variable puis mon gène d'intérêt.

Mon but est donc de construire un programme en C qui repère ces motifs répétés autour d'un gène dans des milliers de lignes. L'output pour l'exemple donné précédemment serait quelque chose comme :

attcg ttttttt *
* ggcta ttttttt
gacc at aggc gatt attca gattc * ttttttt
accg at * ttttttt
accg gg gat ttga ttagccga agg * ttttttt

où les étoiles représentent les parties les plus variables des lignes, situées entre des séquences répétées et mon gène.

Bon pour y avoir un peu réfléchi déjà, c'est pas si facile que ça à programmer. Pour l'instant, ma seule idée est la façon brutale : je prends la première séquence de la 1ere ligne, je regarde si elle se trouve au même endroit dans d'autres lignes, puis je recherche le gène et je mets une étoile à la place de toutes les autres séquences de la ligne. Ca me donne mon premier output : attcg ttttttt *. Puis je refais la même chose mais en prenant les deux premières séquences de ma 1ere ligne cette fois-ci. Etc, etc...

Avant de commencer à coder tout ça, j'aurais aimé solliciter vos expériences pour savoir si vous ne voyez pas une façon plus maline de coder ça. Ou un algorithme qui existerait déjà et permettrait de faire plus ou moins cela, de la recherche de chaines de caractère répétées dans une liste de chaines de caractères.

J'aurais aussi aimé savoir si un autre langage que C pouvait être plus adapté pour faire ça (du travail sur des chaînes). Mes capacités de programmation sont néanmoins limitées à, outre C, Python et Matlab. Mais je peux apprendre si ça en vaut la peine . Et C sera toujours intéressant pour sa rapidité, vu que j'ai des milliers de lignes à traiter.

Merci d'avance de vos conseils, et n'hésitez pas à me demander des choses si je n'ai pas été clair !

PS : comme le post ne parle pas vraiment de C, vous pouvez le déplacer vers un forum plus approprié, mais je n'en ai pas vraiment vu en cherchant un peu.

[Wizard50]

Ta description est un peu flou pour moi, notamment au niveau de l'output : tu souhaite en sortie tous les patterns de séquences d'ADN qui se répète au moins deux fois autour de ton gène ? Autorise tu les gaps (trou) dans ces patterns ?

Bon déjà pour répérer ton gène dans les séquences, je me lancerais dans un algorithme a graine (seed algorithm) type BLAST (Basic Local Alignement Tool).
Après cela, c'est là que les choses se corsent à mon gout car au final, tu ne sais pas quel pattern tu cherche, ni leur longueur. Il te faut donc imposer une longueur minimale de motif que tu cherche, sinon il va considérer que par exemple "a" ou "c" est un pattern possible. Bref après c'est une question de programmation dynamique : il te faut une distance d'édition minimale pour être sur de ne pas louper des patterns qui ne changent que de un ou deux caractères par rapport a ce que tu as déjà trouvé, mais sa dépend si tu veux des patterns exact ou pas. Je ne sais pas bien comment faire, mais à mon avis, il faudra aussi que tu parte sur une solution à base de clustering sinon tu va te retrouver avec bien trop de solution.

[kwariz]

Bonsoir,

ce n'est pas tant le langage de programmation qui va poser problème que ton expérience en algorithmique, enfin je crois ...
Tu as déja pensé à utiliser des arbres de préfixes dans un premier temps puis une structure type dag ? Avec une structure adéquate et adaptée tu peux facilement obtenir une liste de motifs (soit préfixes soit suffixes, un mélange des deux étant plus compliqué à vue de nez) courants (suivant certains critères).

Ma question est donc principalement, comment juges-tu ton niveau en algo, quelle est la littérature que tu as déjà absorbée sur ce problème ?
Quant au langage ... avec lequel te sens-tu le plus à l'aise ?

[fuyo2004]

Ta description est un peu flou pour moi, notamment au niveau de l'output : tu souhaite en sortie tous les patterns de séquences d'ADN qui se répète au moins deux fois autour de ton gène ? Autorise tu les gaps (trou) dans ces patterns ?

Oui en sortie, tous les patterns de séquences qui se répètent au moins deux fois autour de ce gène, bien que dans l'idéal, ce chiffre "2" devrait pouvoir être modifié.

J'autorise les trous dans ces patterns, si par trou tu veux dire une séquence entière. Par contre à l'intérieur d'une séquence, je n'autorise pas de nucléotide manquant (chaque séquence est une unité indivisible). Du coup je ne suis pas sûr que "a" ou "c" puisse être encore considéré un pattern possible ?

Bien que ce serait mieux, je n'ai pas besoin d'une solution exhaustive : un algo qui me trouverait les motifs répétés les plus courants (par exemple, les motifs de 3 séquences qui sont présents plus de 10 fois dans l'ensemble de mes lignes) me suffirait déjà. Encore plus simple, mais ça serait déjà bien pour un début : rechercher les groupes de 2, 3, 4 ou 5 séquences consécutives (donc pas de trou, les séquences pourront être considérées comme une seule chaine de caractères) qui sont présentes plus de 10 fois avant mon gène (donc uniquement en préfixe, pas de motifs qui entourent le gène) dans l'ensemble de mes lignes.

ce n'est pas tant le langage de programmation qui va poser problème que ton expérience en algorithmique, enfin je crois ...
Tu as déja pensé à utiliser des arbres de préfixes dans un premier temps puis une structure type dag ? Avec une structure adéquate et adaptée tu peux facilement obtenir une liste de motifs (soit préfixes soit suffixes, un mélange des deux étant plus compliqué à vue de nez) courants (suivant certains critères).

Ma question est donc principalement, comment juges-tu ton niveau en algo, quelle est la littérature que tu as déjà absorbée sur ce problème ?
Quant au langage ... avec lequel te sens-tu le plus à l'aise ?

J'ai un niveau débutant en algo, j'ai essayé de lire à droite à gauche des infos sur le sujet, mais ce projet serait ma première application. C'est pour ça que je venais demander des pistes ici, comme celles que tu as données. Je vais approfondir la piste des arbres. Pour le langage, je serai le plus à l'aise en C.

[diogene]

Malgré tes explications, il faudrait, avant de pouvoir passer à un algorithme, définir plus précisément le problème.

-1 ton exemple est structuré en lignes. Cela signifie t'il que chaque ligne forme un groupe autonome, et que la recherche de similitude se fait indépendamment dans chaque groupe ?
Un exemple :

attcg ttttttt ac tagggc
ggcta attcg
ttttttt tacc // ici ttttttt n'est pas considéré précédé de attcg ?

-2 la similitute concerne la séquence qui précède dans ton exemple. Concerne t-elle également la séquence qui suit comme ici ?

attcg ttttttt  tagggc  agg
ggcta  ttttttt tagggc  ac
-> ttttttt tagggc

-3 Tu parles du même endroit. Si je comprend, (j'ai aligné les séquences pour la clarté)

   gat  tag accg at agc ccc ttttttt at          gcac agt
            accg at gat aat ttttttt gaccctagacg agt
->          accg at  *   *  ttttttt

une partie 'commune' (espacée de deux groupements)
et

   gat  tag accg at   agc ccc ttttttt at          gcac agt
                 accg at  gat ttttttt gaccctagacg agt
->                            ttttttt

pas de partie 'commune'
et

   gat  tag accg at agc ccc ttttttt at          agt
   gat  ggg accg at gat aat ttttttt gaccctagacg agt
-> gat   *  accg at  *   *  ttttttt *           agt

3 parties communes

[kwariz]

[...]
J'ai un niveau débutant en algo, j'ai essayé de lire à droite à gauche des infos sur le sujet, mais ce projet serait ma première application. C'est pour ça que je venais demander des pistes ici, comme celles que tu as données. Je vais approfondir la piste des arbres. Pour le langage, je serai le plus à l'aise en C.

Bonjour,

donc avant de commencer à réfléchir sur comment t'y prendre, et pour faire suite aux questions de Diogène, il faut créer les structures de données (sdd) que tu vas manipuler (puisqu'on part en c). Ce ne sera pas tant un langage à apprendre que des techniques d'algorithmie.
Tu as 4 bases A,T,C,G (ton alphabet). Tu construis des séquences qui sont des listes ordonnées de bases (tes mots). On te donne (ton extrait de fichier) des fragments qui sont des listes ordonnées de séquences (les phrases) et une séquence particulière, la cible. Tu définis un pattern un peu comme une expression régulière portant sur les séquences (comme Diogène le fait remarquer, il va falloir préciser un peu la syntaxe).
Le problème est donc de construire des patterns suivant certains critères d'occurence de séquences entourant une séquence cible.
Le volume des données semble très important. La recherche porte non sur les bases mais sur les séquences (à confirmer par toi).

Peux-tu donner une estimation du nombre de séquences ? leur longueur (en nombre de bases) ?
Combien y a-t-il de fragments dans le fichier ? Quelle est la longueur des fragments (en nombre de séquences) ?

[fuyo2004]

-1 ton exemple est structuré en lignes. Cela signifie t'il que chaque ligne forme un groupe autonome, et que la recherche de similitude se fait indépendamment dans chaque groupe ?

-2 la similitute concerne la séquence qui précède dans ton exemple. Concerne t-elle également la séquence qui suit comme ici ?

-3 Tu parles du même endroit. Si je comprend, (j'ai aligné les séquences pour la clarté)

1 - oui tout à fait, une ligne = un groupe autonome

2 - oui elle concerne également la séquence qui suit

3 - c'est tout à fait ça. Sauf que je n'ai droit qu'à une étoile par résultat ; donc, dans le premier exemple, les deux étoiles seraient fusionnées pour donner "accg at * ttttttt" ; dans le troisième exemple, on aurait (idéalement, si on ne peut pas faire si compliqué c'est pas grave) plus de résultats :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
   gat  tag  accg at agc ccc ttttttt at              agt
   gat  ggg accg at gat aat ttttttt gaccctagacg agt
 
-> gat  *  ttttttt   
-> gat      ttttttt *      
-> *  accg at ttttttt 
->  accg at   *  ttttttt
->  accg at  ttttttt * 
->  *   ttttttt  agt
-> ttttttt *  agt

C'est à dire que à partir de ta solution, on conserve une seule séquence répétée, on supprimer toutes les autres sauf le gène et on ajoute l'étoile aux différents endroits possible. Et on répète ça pour chaque séquence répétée.

[fuyo2004]

Peux-tu donner une estimation du nombre de séquences ? leur longueur (en nombre de bases) ?

Combien y a-t-il de fragments dans le fichier ? Quelle est la longueur des fragments (en nombre de séquences) ?

Par ligne, entre 1 et 10 séquences à peu près (c'est très variable, mais je donnerais une moyenne de 4-5 séquences par ligne).

Par séquence, une moyenne de six bases, mais ça va de 2 à 10 environ.

Et 10 000 lignes dans le fichier.

Merci pour votre aide en tout cas à tous les deux !

[diogene]

Je crois comprendre.
Un essai de formalisation :

Soit deux séquences possédant le groupement d'intérêt X et de forme
A1p1 ... A12 A11 X B11 B12 ... B1q1
A2p2 ... A22 A21 X B21 B22 ... B2q2

Etape 1 : Détection des coincidences :

• Compléter les séquences à gauche et à droite par des * pour obtenir autant de termes A et de termes B dans les deux séquences
• Conserver le terme X
• Conservez les termes pour lesquels A1j==A2j . Remplacer les autres par des *
• Conservez les termes pour lesquels B1j== B2j. Remplacer les autres par des *

Etape 2 : Compression

• compression des * : Si plusieurs * se suivent les remplacer par une * .
• compression des groupes : Si plusieurs groupes (différents de X) se suivent , ils sont considérés désormais comme un seul groupe.

On obtient une séquence de la forme (*) Cr * Cr-1 * .... C1 (*) X (*) D1 * D2 *....Ds (*)
où (*) est une étoile optionnelle

Etape 3 :

• Si la séquence obtenue ne comporte que le groupement X et éventuellement des étoiles, c'est terminé.
• Sinon, à partir de cette séquence, former toutes les séquences obtenues en remplaçant tous les Ci et les Di sauf 1 par une *, puis d'une compression des *

ces séquences ont la forme (*1) G1 (*2) G2(*3) où G1 (ou G2) est le groupement de référence X et G2 (ou G1) un autre groupement

Etape 4 : Unicité des * :
Pour chacune de ces séquences, former les séquences :

• Si (*2) est une étoile : G1 * G2
• Si (*1) est une étoile : * G1 G2
• Si (*3) est une étoile : G1 G2 *

Exemple :

     gat  tag accg at agc ccc ttttttt at          agt
     gat  ggg accg at gat aat ttttttt gaccctagacg agt

1    gat   *   accg at  *   *  ttttttt    *   agt
2    gat   *  (accg at)   *    ttttttt    *   agt

3-1  gat :
(2)  gat   *  (accg at)   *    ttttttt    *   agt
     gat   *    *         *    ttttttt    *    *
     gat   *  ttttttt  *
4-1  
->   gat   *  ttttttt
->   gat      ttttttt  *

3-2  (accg at) :
(2)  gat   *  (accg at)   *    ttttttt    *   agt   
     *     *  (accg at)   *    ttttttt    *    *
     * (accg at)  *    ttttttt    *
4-2
->     (accg at)  *  ttttttt
->   * (accg at)     ttttttt
->     (accg at)     ttttttt    *

3-3 agt :
(2)  gat   *  (accg at)   *    ttttttt    *   agt
      *    *    *         *   ttttttt     *   agt
      *  ttttttt  * agt
4-3
->       ttttttt  * agt
->    *  ttttttt    agt

C'est bon ?

[fuyo2004]

Oui c'est tout à fait ça. Merci beaucoup.

Des problèmes ne vont-ils pas émerger néanmoins lorsque je vais comparer plus de deux lignes (problèmes au niveau algorithmique ou juste puissance de calcul) ? Imaginons que l'on fasse le même raisonnement que celui que vous avez proposé mais pour trouver des répétitions sur 10 000 lignes ! Le nombre de combinaisons et de séquences répétées différentes va exploser. Ca devrait être faisable néanmoins ?

[diogene]

D'après les ordres de grandeurs que tu donnes, la quantité de données à traiter n'est pas énorme (10000 lignes, 10 séquences par lignes -> 100000 séquences, 6 bases par séquences-> 600000 bases à stocker). Plutôt que d'optimiser la mémoire utilisée, il vaut sans doute mieux optimiser les traitements.

Des problèmes ne vont-ils pas émerger néanmoins lorsque je vais comparer plus de deux lignes

Ote moi un doute, il s'agit bien de comparer les lignes deux à deux sur un ensemble de l'ordre de 10000 lignes, ce qui fait approximativement 50 millions de couple de lignes à traiter ?

[fuyo2004]

Ote moi un doute, il s'agit bien de comparer les lignes deux à deux sur un ensemble de l'ordre de 10000 lignes, ce qui fait approximativement 50 millions de couple de lignes à traiter ?

Et bien non justement, il s'agirait de retrouver les séquences répétées 2 fois, mais aussi 3 fois, quatre fois, etc... Donc pas seulement comparer les lignes 2 à deux, mais aussi, au maximum, comparer une ligne à l'ensemble des autres.

[ternel]

Ma petite suggestion du matin:

Avec une structure auxilliaire, tu peux garder les résultats intermédiaires. Je te propose une map de séquence vers une liste de ligne.
Sans optimisation, ni prudence, ca donne quelque chose comme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
struct index_node{
	int index;//numéro de la ligne.
	struct index_node* next;
};
 
struct row{
	char* sequence
	struct index_node* liste;
	struct row* next;
};
 
typedef struct row* table;

Ainsi, tu compare une ligne avec chaque suivante, en ajoutant les détections pour les deux lignes dans ta table de comparaisons.

Mais les comparaisons sont bien faites ligne à ligne.

[diogene]

Et bien non justement, il s'agirait de retrouver les séquences répétées 2 fois, mais aussi 3 fois, quatre fois, etc... Donc pas seulement comparer les lignes 2 à deux, mais aussi, au maximum, comparer une ligne à l'ensemble des autres.

C'est ce que je voulais exprimer (je pense), mais pour être sûr qu'on se comprend bien :
Il s'agit de chercher les éléments communs à deux lignes quelconques.
On collecte donc les éléments communs aux lignes 1 et 2 plus ceux communs aux lignes 1 et 3 plus ceux des lignes 1 et 4, ... , 2 et 3 , 2 et 4, ... , 3 et 4 ,...., 4 et ...
Au total, si on a N lignes, on a N(N-1)/2 paires de lignes à traiter

[fuyo2004]

C'est ce que je voulais exprimer (je pense), mais pour être sûr qu'on se comprend bien :
Il s'agit de chercher les éléments communs à deux lignes quelconques.
On collecte donc les éléments communs aux lignes 1 et 2 plus ceux communs aux lignes 1 et 3 plus ceux des lignes 1 et 4, ... , 2 et 3 , 2 et 4, ... , 3 et 4 ,...., 4 et ...
Au total, si on a N lignes, on a N(N-1)/2 paires de lignes à traiter

En fait je crois que non, on ne se comprenait pas bien. J'aimerais aussi collecter les éléments communs aux lignes 1,2 ET 3, 1,2,3 ET 4, etc...

Mais ça ce serait dans l'idéal, comparer juste les lignes 2 à 2 serait déjà pas mal. Surtout que si après on fait le compte des motifs les plus répétés, on devrait avoir une approximation des motifs les plus répétés sur l'ensemble des lignes, pas seulement en comparant les lignes 2 à 2. Non ?

[diogene]

Si je comprend, il s'agit alors (dans l'idéal) de traiter les lignes
(1,2); (1,3); (1,4); (1,5); .... (2,3); (2,4) ; (2,5) ; ... (3,4) ; ...
et aussi
(1,2,3) ; (1,2,4) ; (1,2,5); ... (1,3,4) ; (1,3,5) ;... (1,4,5) ; ... (2,3,4) ; (2,3,5) ...
et aussi
(1,2,3,4) ; ...
etc.

Si N est le nombre de lignes, il y a de l'ordre de 2^N combinaisons de ce genre. C'est infaisable directement par la force brute.

On peut peut être s'orienter vers une possibilité comme :

1- faire les séquences non vides résultant de la comparaison de 2 lignes seulement (pour toutes les lignes) en conservant le nombre d'étoiles.
si je compare les lignes a et b, soit (a,b) la séquence obtenue.

2- Pour les séquences résultant de la comparaison de 3 et 4 lignes, on peut partir des séquences obtenues en 1 (qui donnent les (a,b) non vides pour tout a et tout b) en les comparant 2 à 2 :
-- la partie commune aux lignes a , b et c, (a,b,c), doit être la partie commune de (a,b) et (a,c) : (a,b,c) = ((a,b),(a,c)) = ((a,b),(b,c)) = ((a,c),(b,c)) (Les (a,b) (a,c) et (b,c) ont été obtenu en 1). On obtient 3 fois le même résultat.
-- la partie commune aux lignes a,b,c et d, (a,b,c,d), doit être la partie commune de (a,b) et (c,d) : (a,b,c,d)= ((a,b),(c,d)) = ((a,c),(b,d)) =((a,d),(b,c)). On obtient 3 fois le même résultat.
-- On purge les redondances.

3- On reprend le processus sur ces dernières séquences ce qui devrait donner la comparaison sur 5,6 ,7 et 8 lignes.

4- etc. jusqu'à ce qu'on n'ait plus de séquence résultante.

C'est peut être une possibilité à creuser.

[fuyo2004]

Oui je vais creuser ça. Je vais essayer de reprendre toutes les idées mentionnées ici et de les approfondir.

Merci à nouveau pour votre aide.