Discussion :

[mido1951]

Bonjour,
voici mon problème:
J'ai plusieurs séquences voici un exemple des séquences:

Code :

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

1
2
3
4
5
6
>seq1
ABCDEFGHIJKLMANFJFEJFSADFJSDF
>seq2
JGIFJSDGFJSDFJSDOLJFOJDSFOJWERWRWA
>seq3
OSDFISDGSJNVSNLQORUEEJREFJERJ

Je veux découper chaque sequence en des sous-chaine de taille k et recupérer la position position de chaque sous chaine dans sa séquence id.
j'ai utilisé une fonction qui retourne une valeur val de chaque sous-chaine et je vais les stockés dans un tableau (de taille N avec N la taille du tableau) suivant leurs valeurs.
pour cela j'ai crée un tableau de liste chainées. Donc chaque noeud de la liste contient cette structure:

Code :

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

1
2
3
4
5
6
typedef struct Tnoeud{   
  	char* id;   // id du séquence
	char* kmer;   // sous-chaine
	unsigned int position; //position dans id
	struct Thash * next;
}Tnoeud_t;

voici mon programme:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//... pour les initialisations tout va bien
while(fgets(sequence1,TAILLE_MAX, fichier1)!= NULL)  // recupère la ligne du fichier de séquences
        {  
          if(sequence1[0]=='>'){
                            strcpy(id,sequence1);
                       printf("%s",id);   // pour afficher l'id de la séquence
                              }
          if(sequence1[0]!='>')
          {
           for(i=0;i<longseq-k;i++)
            {
			   strncpy(Kmer,sequence1+i,k);
					Value= hash(Kmer);   //la fonction qui retourne une valeur à partir une sous-chaine de taille k c'est Kmer
					Value=Value%lenght;
				TThash[Value]=ajouteteteliste(TThash[Value],id,Kmer,i); // le tableau de liste chainées de taille lenght est TThash
			}
           }
        }

J'ajoute à chaque fois dans la tete de la liste pour qu'il ne parcours pas toute la liste est insère le nouveau noeud à la fin (gagner du temps.).

Mon problème est que j'ai enormément de séquence (20000 séquences) et en moyenne la taille des séquences est 40000 caractères.
J'ai essayé d'éxécuter mais à un certain temps le processus s'arrete j'ai cru que c'est un problème de mémoire puisque je vais avoir (20000*40000) noeuds donc le tableau est très grand.
Est ce que vous avec une idée?
Merci

[picodev]

Bonjour,

arrête-moi si je me trompe mais j'imagine que le but est qu'à partir d'une chaîne tu puisses rapidement retrouver la séquence et la position.
Si c'est le cas, la liste chaînée n'est pas forcément la bonne option car une recherche dans une liste chaînée est coûteuse. Il vaudrait peut-être mieux s'orienter vers une structure de type trie/arbre préfixe sous forme binaire.
En gros tu as un arbre binaire, chaque nœud contient un lien vers son premier fils, un lien vers son frère droit, une liste de (sequence id, position) et une lettre. Cette structure serait bien plus performante pour les recherches et sans doute moins gourmande en mémoire. De plus tu pourrais également garder une seule et même structure pour des k différents.

[mido1951]

Le but est qu'à partir des séquences est de découper chaque séquence en des sous-chaines de taille k et ensuite de récupérer cette sous-chaine avec sa position dans la séquence id. du coup, je dois stocker la sous-chaine sa position et l'id de son origine.
Puis, une fois ce tableau de liste est créé je dois cherche le noeuds en fonction de deux parametres (id et la sous-chaines).
j'espère que c'est un peu clair.
merci pour ton aide

[dalfab]

Taille nécessaire estimée pour un système 32 bits :
- struct Tnoeud = 16 octets
- Nb struct Tnoeud = 20000 * 40000 / k
Dans Tnoeud il a des chaînes et 1 terminateur à réserver :
- Id = 20000 * ( 40000 + 1 ) = 800 020 000
- kmer = 20000 * ( 40000 / k ) * ( k + 1 )
Et les données de hash sont petites devant les autres ici.
Total dans cas où k=10 ==> 2 960 020 000

Le problème ici est que la quantité de données sous cette forme peut facilement atteindre 3GO. Hors sur une machine 32 bits c'est justement la limite maximum (code, dll et données) utilisable par une application.

On peut poser que l'id n'est pas nécessaire, car il peut être reconstruit si nécessaire. On gagne alors 1/3 de mémoire et le problème tient peut-être entièrement en mémoire.
Sinon on se retrouve dans le cas où la solution ne tient pas en mémoire, il faudra charger les données en fonction de la demande, et là ça dépend surtout du type d'accès attendu par le reste du code (par exemple on pourrait laisser toutes les chaînes dans le fichier et ne noter que des offsets à l'intérieur du fichier...)

[picodev]

C'est pourquoi un arbre préfixe conviendrait, car très peu gourmand en ressources. Les nœuds terminaux contiendraient une liste de (id,position).

[mido1951]

J'utilise un serveur de calcul je pense qu'il est limité à 4Go de Ram chaque processeur.
du coup, la table prend plus que 4Go en mémoire.
et si j'utilise un arbre le problème c'est que le parcours dans tout l'arbre est gourmand en temps de calcul vaut mieux utiliser une table et c'est mieux en parcours.(c'est ce que je pense).

[U]
Sinon on se retrouve dans le cas où la solution ne tient pas en mémoire, il faudra charger les données en fonction de la demande, et là ça dépend surtout du type d'accès attendu par le reste du code (par exemple on pourrait laisser toutes les chaînes dans le fichier et ne noter que des offsets à l'intérieur du fichier...)

Je n'ai pas compris cette partie svp.

Merci.

[mido1951]

C'est pourquoi un arbre préfixe conviendrait, car très peu gourmand en ressources. Les nœuds terminaux contiendraient une liste de (id,position).

Non He dois garder les memes parametres sur le noeud(id,souschaine de taille , position) et c'est meme chose. l'arbre occupe le meme espace mémoire que le tableau.

Des suggestions?
Merci

[picodev]

Oui, regarder ce qu'est un arbre préfixe … ou un trie … ou un DAWG …

Si tu fais des recherches à partir de id et sous-chaîne, que tu as de nombreuses sous-chaines (et tu en auras plus que d'id par définition) alors c'est une voie viable et intéressante.

Si tu restes avec une simple structure de liste ta recherche sera linéaire = au pire tu parcourreras toute la liste. Avec un trie tu parcourreras k nœuds (pour une sous-chaîne de longueur k) avant d'aboutir à la liste des id contenant cette sous-chaîne … je pense que le calcul est vite fait même sans estimation. De plus si cette sous-chaîne apparaît dans N listes elle ne sera stockée dans l'arbre qu'une seule fois au lieu des N éparpillé avec une liste. J'imagine qu'avec un alphabet de 4 lettres les sous-chaînes communes seront nombreuses aussi.

OK c'est plus compliqué à implémenter, c'est clair (quoique …), mais si tu cherches à optimiser sans rien changer tu n'iras pas très loin.