Conversion chaine de caractère => entier (ordre des caractères primordial car ADN)

Version imprimable

23/09/2007, 12h12
ctobini

Conversion chaine de caractère => entier (ordre des caractères primordial car ADN)

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 :roll:)) ?

En vous remerciant,

C. Tobini
23/09/2007, 13h01
alex_pi

Citation:

Envoyé par ctobini

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
23/09/2007, 17h14
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)
23/09/2007, 17h26
alex_pi

Citation:

Envoyé par 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)

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)
23/09/2007, 19h48
souviron34

Citation:

Envoyé par alex_pi

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]
23/09/2007, 19h58
alex_pi

Citation:

Envoyé par souviron34

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...
23/09/2007, 20h39
souviron34

Citation:

Envoyé par alex_pi

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...

Avant de répondre n'importe quoi, lis ce que poste le PO.. Il n'a jamais parlé de "prendre moins de place", il a demandé :

1) un entier
2)assez bien décrit pour être implémenté par quelqu'un qui n'a jamais fait d'algo

Donc ...
23/09/2007, 21h04
alex_pi

Citation:

Envoyé par souviron34

Avant de répondre n'importe quoi, lis ce que poste le PO.. Il n'a jamais parlé de "prendre moins de place", il a demandé :

1) un entier
2)assez bien décrit pour être implémenté par quelqu'un qui n'a jamais fait d'algo

Donc ...

Ok, disons que "<<", ça fait peur...

ctobini : tu considères que A = 0, C = 1, G = 2 et T = 3. Pour stocker une chaine de 4 lettres sur un entier de 8 bits, qui existe sur MySQL, tu procèdes de la façons suivante :
si ta chaine est xyzt avec ces petites lettres étant les représentations numériques des grandes, tu prends l'entier x + 4*y + 16 * z + 64 * t
A partir de l'entier, pour récupérer x, tu prends le reste de la division modulo 4. Pour récupérer y, tu divises pas 4, puis tu fais pareil que pour x, et ainsi de suite.

souviron34 : la notation avec les << (qui était inversé par rapport à ce que je viens d'écrire) est parfaitement lisible dans ce cas puisqu'il s'agit bien de physiquement décaler les bits pour mettre les caractères à leur place. Ce n'est pas une optimisation débile, c'est une notation qui en l'occurence est bien plus addaptées que des multiplication par 4 16 ou 64 (et encore plus que celle par 10 100 et 1000...). Et j'insiste que ne pas vouloir se demander comment est physiquement stocké quelque chose lorsque l'on veut justement optimiser ce stockage est une aberration.

Citation:

Envoyé par alex_pi

souviron34 : la notation avec les << (qui était inversé par rapport à ce que je viens d'écrire) est parfaitement lisible dans ce cas puisqu'il s'agit bien de physiquement décaler les bits pour mettre les caractères à leur place

Pour aller dans le sens d'alex_pi, il suffit d'ecrire proprement son programme pour que ca reste lisible.

Par exemple on peut faire un truc du genre:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Constante Entier LETTRE_A = binaire(00) Constante Entier LETTRE_C = binaire(01) Constante Entier LETTRE_G = binaire(10) Constante Entier LETTRE_T = binaire(11) Fonction AjouterLettre( [IN/OUT] Entier resultat, [IN] Entier lettre) { resultat = resultat<<2 | lettre; Fin Fonction Programme Entier adn=0; AjouterLettre(adn, LETTRE_A); AjouterLettre(adn, LETTRE_T); AjouterLettre(adn, LETTRE_G); AjouterLettre(adn, LETTRE_C); Fin Programme
Enfin, tout ca n'a pas trop de rapport avec le PO. Vu qu'il veut stocker plus de 500 caracteres, ca rentre pas trop dans les types primitifs (32/64 bits). Et de toute façon, le probleme se situe dans le monde MySQL.

Soit dit en passant, les index des tables InnoDB de MySql utilisent les BTree, et je pense que c'est largement assez performant pour faire des recherches. Et en MySQL 5.0, le moteur InnoDB crée à la volée une table de hash basée sur le BTree. :P

24/09/2007, 11h03
Thierry Chappuis
Citation:
Envoyé par pseudocode

Code:

1 2 3 4 #define LETTRE_A 0b00 #define LETTRE_C 0b01 #define LETTRE_G 0b10 #define LETTRE_T 0b11
La notation que tu utilises pour exprimer des constantes entières avec leur représentation binaire n'est pas valide. Par ailleurs, ce prototype:

Code:

void ajouterLettre(int &resultat, int lettre)

c'est n'importe quoi. Même si on est pas sur le forum C, je pense qu'il est souhaitable de publier du code écrit correctement. Personnellement, le pseudocode me convient parfaitement.

Thierry
24/09/2007, 11h20
pseudocode

Citation:

Envoyé par Thierry Chappuis

c'est n'importe quoi. Même si on est pas sur le forum C, je pense qu'il est souhaitable de publier du code écrit correctement. Personnellement, le pseudocode me convient parfaitement.

Toutes mes excuses...:oops: j'ai modifié mon post en consequence.