Discussion :

[ctobini]

Bonjour,

Je suis en train de créer une base de données MySQL avec une table contenant des séquences d'ADN devant être uniques.

Les 2 écueils sont les suivants :

- un index unique doit contenir la longueur du segment de la chaine à comparer, or la longueur est variable et la comparaison doit se faire sur la totalité de la chaine

- une indexation sur des chaines aussi longues (>= 500 caractères) va être lourde pour la base.

Je cherche donc un algo capable de convertir une chaine de caractère en entier, sachant que la chaine est composée de 4 caractères (A, T, G et C) et que leur ordre est primordial (ATGC et AGTC ne doit pas être pondéré de la même manière).

Connaîtriez-vous un algo capable de faire ceci (soit directement utilisable (je développe en Perl) soit assez bien décrit pour être implémenté par quelqu'un qui n'a jamais fait d'algo (moi )) ?

En vous remerciant,

C. Tobini

[alex_pi]

Je cherche donc un algo capable de convertir une chaine de caractère en entier, sachant que la chaine est composée de 4 caractères (A, T, G et C) et que leur ordre est primordial (ATGC et AGTC ne doit pas être pondéré de la même manière).

Une façon simple est de constater que tu n'as que 4 caractères, qu'il peuvent donc être stockés sur 2 bits (00, 01, 10 et 11), et que donc tu peux mettre 4 caractères par octets., ce qui divise donc par 4 la taille de ta chaine.

Ensuite, une méthode un peu moins simple consiste à compresser ta chaine. Typiquement, je pense qu'un petit Burrows-Wheeler (suivi d'une compression arithmétique par exemple) a des chances de bien arranger une chaine génétique, mais je n'en suis pas sûr, à tester.

Bon après, une compression, ça ne marche que si tu fais une recherche précise sur la chaine, tu ne pourras pas faire des recherches de sous chaîne facilement.

Have fun

[souviron34]

tu peux aussi faire :

ici caractère = indice dans tableau [A T G C] : A = 0 T = 1 G = 2 C = 3 ..

entier = 1er caractère + (10+2ième*10) + (100+3ième *100) + (1000 + 4ième*1000)

[alex_pi]

tu peux aussi faire :

ici caractère = indice dans tableau [A T G C] : A = 0 T = 1 G = 2 C = 3 ..

entier = 1er caractère + (10+2ième*10) + (100+3ième *100) + (1000 + 4ième*1000)

C'est quand même franchement gâcher d'utiliser 13 bits au lieu de 8 ! Je me permet quand même de rappeler que l'écriture décimal n'a que peu de signification quand on fait de l'informatique.

entier court = 1 er caratère<<6 + 2eme << 4 + 3 eme << 2 + 4 eme

me semble plus judicieux (avec << n signifiant "décalé de n bits vers la droite)

[souviron34]

C'est quand même franchement gâcher d'utiliser 13 bits au lieu de 8 ! Je me permet quand même de rappeler que l'écriture décimal n'a que peu de signification quand on fait de l'informatique.

entier court = 1 er caratère<<6 + 2eme << 4 + 3 eme << 2 + 4 eme

me semble plus judicieux (avec << n signifiant "décalé de n bits vers la droite)

Bah :

1) il demande un entier.... On a bien 32 bits ces jours-ci, non ???

2) pour moi, non informaticien de formation, désolé mais je préfère éviter la notation << ainsi que le concept associé... L'algorithme me semble plus clair (je répète, je ne fais et n'ai fait que des programmes scientifiques, destinés à être modifiés par des scientifiques ou des informaticiens, et je n'ai jamais eu de cours d'info) avec la formulation "mathématique")...

JE NE VEUX PAS CONNAITRE LA NOTION DE BITS... ni de compter en binaire, en hexa, ou en octal. Mon monde est en décimal, je compte en décimal...

[EDIT]

PS: je te souhaite bien du plaisir à déboguer des gros programmes faits par d'autres que toi avec des opérations complexes de shifts, et une contrainte de temps pour que ça marche...

[/EDIT]

[alex_pi]

JE NE VEUX PAS CONNAITRE LA NOTION DE BITS... ni de compter en binaire, en hexa, ou en octal. Mon monde est en décimal, je compte en décimal...
[/EDIT]

Donc à la question "comment je fais pour que ça prenne moins de place" vous répondez "je ne sais pas comment c'est stocké, mais je vais quand même répondre". C'est pas mal...