méthode pour encoder une séquence ADN

Version imprimable

14/03/2016, 21h10
FryHandiz

méthode pour encoder une séquence ADN

Bonjour à toutes et à tous,

Je débute en C++ et j'ai une petite API à développer.
Sauf que voilà, j'arrive à un moment où je bloque un peu... !
Donc j'ai une séquence ADN formée des quatre lettres suivantes : ATCG et j'ai besoin de l'encoder afin de pouvoir la manipuler (genre créer une séquence reverse ex:GCTA, ou le complémentaire TAGC). Bref, mon souci est surtout qu'on m'a vite fait parlé d'un truc que je ne comprends pas.
Apparemment, il est nécessaire d'encoder pour se retrouver avec par exemple A = 0, C=1, T=2 et G=3. Pour que ça prenne moins de place en mémoire (Gniéh ? 1ère question xD). Apparemment, quand je "stock" mes valeurs dans un tableau, ça prendrait moins de place...
Et après bon... Je sais pas trop comment créer ma méthode mais déjà, comprendre ça m'aiderait pas mal.

Merci d'avance pour votre aide !
14/03/2016, 23h11
Bousk

Salut,

te fatigues pas avec des considérations de quantité de mémoire. :weird: (tu peux lancer ce regard à quiconque t'as sorti cette absurdité)
Tu veux une séquence, tu crées un vector et basta. Un vector de char est suffisant. Si tu veux fignoler, tu peux créer un enum contenant tes 4 valeurs à la place, et c'est tout pour le moment, ça fera très bien l'affaire.
15/03/2016, 00h08
koala01

Salut,

Si j'ai bien compris le principe de l'ADN (ce qui reste encore à démontrer, vu que je suis informaticien, et non biologiste :D), le nucélotide est systématiquement composés de quatre éléments représentés par les lettre C G A et T (et autre combinaisons possibles), et tu as une série de nucélotides qui se suivent pour représenter une "séquence ADN"(merci wikipedia :D).

Hé bien, le plus facile est sans doute de créer deux types de donnée bien distincts : un type de donnée permettant de représenter la notion de nucléotide et un type de donnée permettant de représenter... une séquence d'ADN.

Ceci dit, je dis qu'il faut créer des types de données, mais le seul but recherché est de permettre au développeur de savoir s'il est occupé à travailler sur... ce qui représente un nucléotide ou sur ce qui représente une séquence ADN! On n'est donc pas forcément obligé d'aller très loin dans la définition de ces types et, en l'occurrence, des alias de type pourraient très bien faire l'affaire ;) (enfin, dans un premier temps du moins).

Ainsi, la notion de nucléotide, vu quelle doit être représentée par quatre lettres, pourrait très bien prendre la forme de

Code:

using Nucleotide = std::array<char, 4>;

(Attention: C++11 obligatoire ;) )

Quant à la notion de "séquence d'ADN", elle pourrait tout aussi bien prendre la forme de

Code:

using AdnSequence = std::vector<Nucleotide>;

.

La seule chose, c'est que la notion de tableau (comme celle représentée par la classe std::vector) est particulièrement rapide lorsqu'il s'agit d'accéder aux différents éléments qu'elle contient, mais... d'une lenteur crasse lorsqu'il s'agit d'augmenter le nombre d'éléments qu'elle est capable de contenir. Si bien que l'idéal est généralement de faire en sorte que std::vector demande directement "assez de mémoire" que pour être en mesure de contenir l'ensemble des éléments que nous nous apprêtons à lui donner.

PS : je confirme ce que bousk dit : un char pour représenter les valeurs de C, G, T et A est largement suffisant, et prendra surement moins de place en mémoire que d'utiliser n'importe quel type "entier" ;)

En outre, il serait éventuellement possible de faire encore mieux du point de vue de l'utilisation de la mémoire en essayant de faire en sorte d'utiliser systématiquement deux bits pour chaque lettre. Mais, à moins d'avoir la preuve que l'utilisation d'un char pour représenter un des éléments du nucléotide ne représente déjà une "utilisation trop importante de la mémoire", je crois qu'il serait particulièrement masochiste d'essayer de faire autrement ;)
15/03/2016, 07h11
LandReagan

Du nucléotide...

Salut,

Un nucléotide est SOIT : A, C, G ou T. Il semble donc qu'une enum soit plus appropriée qu'un std::array!

Non?
15/03/2016, 09h34
Bousk

Oui mais tu as bien une séquence de nucléotide non ? Donc fatalement à un moment il t'en faut plusieurs.. un tableau/array donc. ;)
15/03/2016, 10h06
LandReagan

Ah ouais, je n'avais pas compris ça comme ça.
15/03/2016, 10h18
ternel

Pour le coup, le nucléotide ne contient qu'une valeur (parmi {A, T, C,G}), c'est la séquence qui est représentable par un vector.

On a intéret à prendre un using Nucleotide = char; ou enum class Nucleotide {A, T, C, G};.
Mais je suis d'accord avec using AdnSequence = std::vector<Nucleotide>;. (ou list, selon besoin, mais à voir plus tard)
15/03/2016, 11h30
VivienD
Bonjour,

Pour représenter une nucléotide et pouvoir retranscrire ta séquence ADN sous la forme d'une chaîne de caractère, je serais plutôt d'avis d'utiliser l'énumération suivante:
Code:

1 2 3 4 5 6 7 enum Nucleotide : char { A = 'A', C = 'C', G = 'G', T = 'T' };
Ainsi, tu pourras faire les conversions Nucleotide-char de manière implicite.

Tschüß

En généralisant l'utilisation d'une nucléotide comme celle de VivienD, tu peux alors représenter une séquence ADN comme suit :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <array>
 
enum Nucleotide : char
{
   A = 'A',
   C = 'C',
   G = 'G',
   T = 'T'
};
 
class Sequence
{
public:
 
   static constexpr size_t SIZE = 4;
 
   Sequence(const std::array<Nucleotide, SIZE> &sequence);
   void reverse();
   void complement();
 
   // opérateur << pour faciliter l'affichage d'une séquence
   friend std::ostream &operator <<(std::ostream &os, const Sequence &sequence)
   {
       for (char nucleotide : sequence.sequence)
       {
          os << nucleotide;
       }
       return os;
   }
 
private:
 
   std::array<Nucleotide, SIZE> sequence;
 
};
 
Sequence::Sequence(const std::array<Nucleotide, SIZE> &sequence) :
   sequence(sequence)
{
}
 
void Sequence::reverse()
{
   for (auto i = 0u; i < SIZE/2; i++)
   {
       auto temp = sequence[i];
       sequence[i] = sequence[SIZE - 1 - i];
       sequence[SIZE - 1 - i] = temp;
   }
}
 
void Sequence::complement()
{
   // ...
}
 
int main()
{
    Sequence sequence{{A, T, C, G}};
    std::cout << sequence << std::endl;
 
    sequence.reverse();
    std::cout << sequence << std::endl;
 
    return 0;
}

Comme tu peux le voir, l'utilité du tableau est visible lorsqu'il s'agit de manipuler la séquence. Plus simple que mon exemple : utiliser la fonction std::reverse() ;)

Salut,

je suis pas franchement expert en C++ du coup je te parlerai pas des classes de std.
Pour la remarque sur la mémoire : ça peut dépendre du compilo mais le char est l'élément le plus petit en mémoire (un octet).
Pour l'inversion d'une séquence : c'est une inversion de tableau, pas d'astuce particulière
Pour la complémentaire d'une séquence : là l'utilité de valeurs bien définies peut faciliter le travail (XOR).
Exemple rapide avec des valeurs de PREPRO :
Code:

1 2 3 4 5 6 #define A 0x01 // valeur pour l'adénine telle que A^X = T #define T 0x03 // valeur pour la thymine telle que T^X = A #define C 0x05 // valeur pour la cytosine telle que C^X = G #define G 0x07 // valeur pour la guanine telle que G^X = C #define Z 0x00 // délimiteur de séquence, facultatif #define X 0x02 // masque XOR d'inversion

15/03/2016, 14h39
ternel
il n'est pas forcément nécessaire d'inverser la séquence, tu peux aussi parcourir un tableau par la fin:
Code:

1 2 3 for(int i = taille-1; i>=0; --i) { utiliser(tab[i]); }
Si, comme je t'y invite vivement, tu travailles avec des std::vector (ou std::list ou autre), il y a les fonctions membres rbegin() et rend() pour cela.

Citation:
Envoyé par jopopmk
Salut,

je suis pas franchement expert en C++ du coup je te parlerai pas des classes de std.
Pour la remarque sur la mémoire : ça peut dépendre du compilo mais le char est l'élément le plus petit en mémoire (un octet).
Pour l'inversion d'une séquence : c'est une inversion de tableau, pas d'astuce particulière
Pour la complémentaire d'une séquence : là l'utilité de valeurs bien définies peut faciliter le travail (XOR).
Exemple rapide avec des valeurs de PREPRO :
Code:

1 2 3 4 5 6 #define A 0x01 // valeur pour l'adénine telle que A^X = T #define T 0x03 // valeur pour la thymine telle que T^X = A #define C 0x05 // valeur pour la cytosine telle que C^X = G #define G 0x07 // valeur pour la guanine telle que G^X = C #define Z 0x00 // délimiteur de séquence, facultatif #define X 0x02 // masque XOR d'inversion
Si ce n'est qu'un #define, c'est franchement moyen moyen en C++... Une énumération (simple) fait bien mieux le travail en cas de besoin ;)

La meilleure approche est peut-être un mix des deux.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <algorithm>
#include <array>
#include <map>
 
enum Nucleotide : char
{
   A = 0x01,
   C = 0x05,
   G = 0x07,
   T = 0x03
};
 
class Sequence
{
public:
 
   static constexpr size_t SIZE = 4;
 
   Sequence(const std::array<Nucleotide, SIZE> &sequence);
   void reverse();
   void complement();
 
   friend std::ostream &operator <<(std::ostream &os, const Sequence &sequence);
 
private:
 
   static constexpr char COMPLEMENT = 0x02;
   static const std::map<char, char> mapping;
 
   std::array<Nucleotide, SIZE> sequence;
 
};
 
const std::map<char, char> mapping =
{
  {0x01, 'A'},
  {0x05, 'C'},
  {0x07, 'G'},
  {0x03, 'T'}
};
 
Sequence::Sequence(const std::array<Nucleotide, SIZE> &sequence) :
   sequence(sequence)
{
}
 
void Sequence::reverse()
{
   std::reverse(sequence.begin(), sequence.end());
}
 
void Sequence::complement()
{
   // ...
}
 
inline std::ostream &operator <<(std::ostream &os, const Sequence &sequence)
{
   for (char nucleotide : sequence.sequence)
   {
      os << mapping.at(nucleotide);
   }
   return os;
}
 
int main()
{
    Sequence sequence{{A, T, C, G}};
    std::cout << sequence << std::endl;
 
    sequence.reverse();
    std::cout << sequence << std::endl;
 
    sequence.complement();
    std::cout << sequence << std::endl;
 
    return 0;
}

15/03/2016, 15h29
jopopmk

J'ai bien dit que j'étais pas expert en C++, et que mon exemple était "rapide" :mrgreen:
Ce choix de valeurs (d'autres fonctionnent aussi hein) permet de trouver la complémentaire d'une séquence de la plus simple des manières.
On peut évidemment valoriser les éléments d'une enum pareillement, mais en C ça taille un int, là on a de la constante qui tient dans un octet ^(*).

Maintenant à voir quel est l'objectif principal : manipuler des séquences (valoriser l'enum avec des valeurs qui simplifie les opérations) ou les afficher (valoriser l'enum avec les char équivalents) ? Je proposais juste une astuce pour le premier cas.

^(*) : en C non plus les #define ne sont pas toujours les meilleurs choix ;)

Pour le complément, j'ai ça avec un enum :

Code:

1
2
3
4
5
6
7
void Sequence::complement()
{
   for (auto &nucleotide : sequence)
   {
       nucleotide = static_cast<Nucleotide>(nucleotide ^ COMPLEMENT);
   }
}

Une idée pour faire plus simple?

Citation:
Envoyé par jopopmk
Salut,

je suis pas franchement expert en C++ du coup je te parlerai pas des classes de std.
Pour la remarque sur la mémoire : ça peut dépendre du compilo mais le char est l'élément le plus petit en mémoire (un octet).
Pour l'inversion d'une séquence : c'est une inversion de tableau, pas d'astuce particulière
Pour la complémentaire d'une séquence : là l'utilité de valeurs bien définies peut faciliter le travail (XOR).
Exemple rapide avec des valeurs de PREPRO :
Code:

1 2 3 4 5 6 #define A 0x01 // valeur pour l'adénine telle que A^X = T #define T 0x03 // valeur pour la thymine telle que T^X = A #define C 0x05 // valeur pour la cytosine telle que C^X = G #define G 0x07 // valeur pour la guanine telle que G^X = C #define Z 0x00 // délimiteur de séquence, facultatif #define X 0x02 // masque XOR d'inversion
Citation:
Envoyé par RPGamer
La meilleure approche est peut-être un mix des deux.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include <iostream> #include <algorithm> #include <array> #include <map> enum Nucleotide : char { A = 0x01, C = 0x05, G = 0x07, T = 0x03 }; class Sequence { public: static constexpr size_t SIZE = 4; Sequence(const std::array<Nucleotide, SIZE> &sequence); void reverse(); void complement(); friend std::ostream &operator <<(std::ostream &os, const Sequence &sequence); private: static constexpr char COMPLEMENT = 0x02; static const std::map<char, char> mapping; std::array<Nucleotide, SIZE> sequence; }; const std::map<char, char> mapping = { {0x01, 'A'}, {0x05, 'C'}, {0x07, 'G'}, {0x03, 'T'} }; Sequence::Sequence(const std::array<Nucleotide, SIZE> &sequence) : sequence(sequence) { } void Sequence::reverse() { std::reverse(sequence.begin(), sequence.end()); } void Sequence::complement() { // ... } inline std::ostream &operator <<(std::ostream &os, const Sequence &sequence) { for (char nucleotide : sequence.sequence) { os << mapping.at(nucleotide); } return os; } int main() { Sequence sequence{{A, T, C, G}}; std::cout << sequence << std::endl; sequence.reverse(); std::cout << sequence << std::endl; sequence.complement(); std::cout << sequence << std::endl; return 0; }
On peut même aller plus loin si on tient prendre en compte les propriétés chimiques des nucléotides. Soit dit en passant, je fais appel à de lointains souvenirs, là.

D'une part, l'adénine et la cytosine sont des amines tandis que la guanine et la thymine sont des cétones; et il s'avère qu'un cétone ne peut s'apparier qu'à une anime, et inversement. D'autre part, l'adénine et la guanine sont des purines tandis que la cytosine et la thymine sont des pyrimidines; et il s'avère qu'une purine ne peut s'apparier qu'à une pyrimidine.
En réservant un bit pour chacun des types de molécule (soit quatre bits en tout, sur au minimum huit disponibles dans char), on peut code l'énumération Nucleotide comme suit:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 enum Nucleotide : char { //Flags __F_Nucleotide_Amine = 0x01, __F_Nucleotide_Ketone = 0x02, __F_Nucleotide_Purine = 0x04, __F_Nucleotide_Pyrimidine = 0x08, //Mask __M_Nucleotide_Complement = 0x0f, //Nucleotides A = __F_Nucleotide_Amine | __F_Nucleotide_Purine, C = __F_Nucleotide_Amine | __F_Nucleotide_Pyrimidine, G = __F_Nucleotide_Ketone | __F_Nucleotide_Purine, T = __F_Nucleotide_Ketone | __F_Nucleotide_Pyrimidine };
Avec l'opérateur binaire & et les drapeaux __F_Nucleotide_Xyz, on peut savoir si le nucléotide est une amine, un cétone, une purine ou une pyrimidine. Avec l'opérateur binaire ^ et le masque __M_Nucleotide_Complement on peut trouver le complément d'un nucléotide ou savoir si deux nucléotides peuvent s'apparier l'un à l'autre: en effet, l'opération X ^ Y donne 0x0f, c'est-à-dire __M_Nucleotide_Complement, si et seulement si X et Y représente des nucléotides complémentaires.

15/03/2016, 16h15
RPGamer

Je suis pas fan des __ normalement réservés pour la STL mais l'idée est bonne :)
15/03/2016, 16h19
VivienD

Citation:

Envoyé par RPGamer

Je suis pas fan des __ normalement réservés pour la STL mais l'idée est bonne :)

Je utilise le double tiret bas pour indiquer aux développeurs qui veulent utiliser mon code, moi inclus, qu'ils ne doivent pas toucher à ces éléments.
15/03/2016, 17h13
bacelar

Citation:

Je utilise le double tiret bas pour indiquer aux développeurs qui veulent utiliser mon code, moi inclus, qu'ils ne doivent pas toucher à ces éléments.

Valable en C, mais pas en C++, ou les "__" en début d'identifiants sont réservés à la STL.

P.S.: Je ne crois pas que les "__" soient valide en C non plus. Je crois que les "__exit" et autres bidules implémentés dans certaines C-Runtime apprécient la blague.
15/03/2016, 17h56
jopopmk

Le "__" est utilisé pour les conventions d'appel sous Zindows (MSVC) ex. __cdecl, __fastcall ...
Je sais pas si y'a une vraie convention pour son usage.

Enfin c'est pas la question, on s'égare :mrgreen:
Remarquez, FryHandiz n'est pas revenu depuis qu'il a posé sa question ...

Sinon j'aime bien le découpage de VivienD, ça ajoute du sens supplémentaire et le principe est élégant.
15/03/2016, 18h47
bacelar

Citation:

Le "__" est utilisé pour les conventions d'appel sous Zindows (MSVC) ex. __cdecl, __fastcall ...

Ils se permettent cela justement parce que la norme leur en donne le droit en C++.
VC++ est un compilateur C++, pas un compilateur C.
Mais je pense qu'il y a les même restrictions en C (tout OS, tout compilateur, même s'ils ne le vérifient pas).
15/03/2016, 18h51
Bousk

Quitte à disgresser jusqu'au bout:
http://www.doc.ic.ac.uk/lab/cplus/c++.rules/chap5.html

Citation:

The use of two underscores (`__') in identifiers is reserved for the compiler's internal use according to the ANSI-C standard.

Underscores (`_') are often used in names of library functions (such as "_main" and "_exit"). In order to avoid collisions, do not begin an identifier with an underscore.

http://www.gnu.org/software/libc/man...ved-Names.html

Citation:

In addition to the names documented in this manual, reserved names include all external identifiers (global functions and variables) that begin with an underscore (‘_’) and all identifiers regardless of use that begin with either two underscores or an underscore followed by a capital letter are reserved names. This is so that the library and header files can define functions, variables, and macros for internal purposes without risk of conflict with names in user programs.

En gros c'est réservé à l'implémentation et aux mot-clés du compilo.
16/03/2016, 07h14
FryHandiz

Woaw*! D’habitude quand je poste une question sur un forum j’ai soit jamais de réponses, soit on me répond que mon message n’est pas «*conforme*»*:D
Bon ok, j’avais aussi perdu le chemin pour venir ici …*! (non je ne suis pas blonde du tout*! Ahem.)

Bon alors, j’ai demandé un peu plus d’éclaircissement, et donc il faut pouvoir «*encoder*» de sorte à ce qu’on utilise 8 bits pour 4 lettres dans chacune des cases de notre tableau où vont se retrouver nos A,T,C,G.

@Koala01 > Dans mon cas, on souhaite surtout travailler sur des séquences même si, plus tard, on risque de vouloir rechercher si, entre deux séquences, on ne retrouve pas de similarité, etc. Mais pour moi, ça ce sera peut être plus tard ou jamais vu ma très faible connaissance en C++ xD (C’est la première année où je fais de l’informatique et on nous demande de coder une API de mapping de séquence… AHEM. Vive la reconversion…*! Heureusement que je suis un peu maso*:p).

@RPGamer > Si je ne dis pas de bétises, pour le complément/manipuler les séquences, il est préférable de le faire une fois qu’on a encodé. Car certaines fois, les séquences de nucléotides peuvent aller jusqu'à… 120 000 nucléotides, ce qui apparemment peut saturer la mémoire si on ne passe pas avant à l’encodage.

Me frappez pas mais pour la suite je n’ai pas trop compris le coup du A = 0x01, etc.*:s
Pourquoi devoir faire 0x01…*? Et pourquoi pas 1*? Et aussi, pourquoi de 2 en 2…*?
Je suis vraiment désolée si mes questions sont stupides mais je suis malheureusement loin d’être une informaticienne >.<’

Encore merci pour votre aide*!
16/03/2016, 09h07
RPGamer

Quand tu parles d'encoder les nucleotides sur un octet c'est dans cette direction que tu dois aller. On utilise la notation hexadécimal (0x..) pour coder un octet pour des questions pratiques (2⁴ = 16 donc 2 digits hexa permettent de coder 1 octet).

Donc pour coder une amine on te propose d'utiliser le premier bit :

0x01 = 00000001

pour coder une cétone le 2e bit :

0x02 = 00000010

pour coder une purine le 3e bit :

0x04 = 00000100

et pour coder une pyrimidine le 4e bit :

0x08 = 00001000

tous les bits du premier digit à 1 pour le masque de complément :

0x0f = 00001111

Avec ces valeurs tu vas pouvoir coder A, C, G et T par une simple opération logique "OU" (|), c-à-d pour chaque position si au moins 1 bit sur l'un des octets vaut 1, le bit du résultat à la même position vaut 1. Table de vérité :

1 OU 1 = 1
1 OU 0 = 1
0 OU 1 = 1
0 OU 0 = 0

Exemple :

A = amine + purine = 0x01 | 0x04 =

00000001
00000100 |
________
00000101 = 0x05

on a donc A = 0x05.

Pour le complément il suffit d'appliquer un "OU exclusif" (^) avec le masque de complément, c-à-d une opération OU dont un bit du résultat à une position donnée ne peut valoir 1 que si un seul des deux opérande a un bit 1 à cette même position. Table de vérité :

1 OUX 1 = 0
1 OUX 0 = 1
0 OUX 1 = 1
0 OUX 0 = 0

Le complément de A peut se déterminer comme suit : A OUX complément = 0x05 ^ 0x0f =

00000101
00001111 ^
________
00001010 = 0x0a

Le complément de A est donc T (cétone + pyrimidine).

Etant donné qu'il suffit de 4 bits pour coder tous les nucleotides, si tu veux absolument économiser de la mémoire il est toujours possible de coder 2 nucleotides par octets comme ceci :

A = 0x05 = 00000101
C = 0x09 = 00001001

AC = (A << 4) | C = 0x59 = 01011001

et pour extraire C par exemple, il faut appliquer un opération "ET" (&), c'est à dire que le bit du résultat vaut 1 seulement si les bits des 2 opérandes de cette position valent 1. Table de vérité :

1 ET 1 = 1
1 ET 0 = 0
0 ET 1 = 0
0 ET 0 = 0

C = AC ET complément = 0x59 & 0x0f =

01011001
00001111 &
________
00001001 = 0x09

Pour extraire A, étant donné qu'il est positionné au niveau des bits de poids fort, un simple décalage de 4 bits vers la droite suffit, les ordinateurs sont très performants pour le faire :

A = AC >> 4 = 0x59 >> 4 = 00000101 = 0x05

Après si ton max de mémoire occupée c'est 120 Ko, pas de quoi faire tousser nos machines ;)
16/03/2016, 09h15
ternel

D'une manière générale, on préfère utiliser la notation hexadécimale pour les valeurs subissant des opérations bit-à-bit, c'est à dire &, |, ^ et ~ (inverse).
Cela souligne que ce sont les bits du nombre qui nous intéresse, et qu'on va faire des choses non algébriques dessus.
16/03/2016, 11h50
fenkys

Bonjour,

120 000 nucléotide ce n'est rien avec un ordinateur moderne.

Pour répondre à RPGamer, pourquoi utiliser un bit différent pour une amine et une cétone. Le nucléotide est soit l'un, soit l'autre. Idem pour les purines / pyrimidines. Tu peux donc réduire à 2 bits par bases et 4 bases par octets.

Ceci étant, rechercher un séquence avec ce genre de stockage peut être un poil compliqué. Mais si la recherche n'est pas sa priorité, c'est jouable.

Citation:

on utilise 8 bits pour 4 lettres dans chacune des cases de notre tableau

Et si j'ai bien traduit cette phrase, c'est ce qui est demandé.

OK bah peu importe, la méthode reste la même, il suffit juste de diviser le nombre d'énumérés par 2. Si je reste sur une implémentation avec 4 codes :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
 
enum Nucleotide : char
{
    AMINE      = 0x01,
    KETONE     = 0x02,
    PURINE     = 0x04,
    PYRIMIDINE = 0x08,
 
    COMPLEMENT = 0x0f,
 
    A = AMINE | PURINE,
    C = AMINE | PYRIMIDINE,
    G = KETONE | PURINE,
    T = KETONE | PYRIMIDINE
};
 
inline const Nucleotide operator ^=(Nucleotide &x, const Nucleotide y)
{
    return x = static_cast<Nucleotide>(x ^ y);
}
 
inline const Nucleotide operator ^(Nucleotide x, const Nucleotide y)
{
    return x ^= y;
}
 
inline std::ostream &operator <<(std::ostream &os, const Nucleotide n)
{
    static const std::map<Nucleotide, char> MAPPING
    {{
        {A, 'A'},
        {C, 'C'},
        {G, 'G'},
        {T, 'T'}
    }};
 
    return os << MAPPING.at(n);
}
 
class Sequence
{
private:
 
    std::vector<Nucleotide> sequence;
 
public:
 
    Sequence(const std::vector<Nucleotide> &sequence) :
        sequence(sequence)
    {
 
    }
 
    void reverse()
    {
        std::reverse(sequence.begin(), sequence.end());
    }
 
    void complement()
    {
        for (auto &n : sequence)
        {
            n ^= COMPLEMENT;
        }
    }
 
    friend std::ostream &operator <<(std::ostream &os, const Sequence &s)
    {
       for (const auto n : s.sequence)
       {
          os << n;
       }
       return os;
    }
};
 
int main()
{
   Sequence sequence{{A, G, C, T, G, T, A, C}};
   std::cout << "Sequence de base : " << sequence << std::endl;
 
   Sequence sequence2 = sequence;
 
   sequence.reverse();
   std::cout << "Inverse : " << sequence << std::endl;
 
   sequence2.complement();
   std::cout << "Complement : " << sequence2 << std::endl;
 
   Nucleotide complement = A ^ COMPLEMENT;
   std::cout << "Complement de " << A << " : " << complement << std::endl;
 
   return 0;
}

Il faut ensuite l'adapter pour n'utiliser que 2 codes.

On peut aussi mixer macros temporaires et énumérations. Par exemple:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//Header file: nucleotide.h
 
#ifndef NUCLEOTIDE_H
#define NUCLEOTIDE_H
 
#include <stdexcept>
 
#ifdef NUCLEOTIDE_F_AMINE
# error "NUCLEOTIDE_F_AMINE is already defined!"
#endif // NUCLEOTIDE_F_AMINE
#ifdef NUCLEOTIDE_F_KETONE
# error "NUCLEOTIDE_F_KETONE is already defined!"
#endif // NUCLEOTIDE_F_KETONE
#ifdef NUCLEOTIDE_F_PURINE
# error "NUCLEOTIDE_F_PURINE is already defined!"
#endif // NUCLEOTIDE_F_PURINE
#ifdef NUCLEOTIDE_F_PYRIMIDINE
# error "NUCLEOTIDE_F_PYRIMIDINE is already defined!"
#endif // NUCLEOTIDE_F_PYRIMIDINE
#ifdef NUCLEOTIDE_M_COMPLEMENT
# error "NUCLEOTIDE_M_COMPLEMENT is already defined!"
#endif // NUCLEOTIDE_M_COMPLEMENT
 
//New temporary macros
#define NUCLEOTIDE_F_AMINE      0x01
#define NUCLEOTIDE_F_KETONE     0x02
#define NUCLEOTIDE_F_PURINE     0x04
#define NUCLEOTIDE_F_PYRIMIDINE 0x08
#define NUCLEOTIDE_M_COMPLEMENT 0x0f
 
//New unscoped enumeration: Nucleotide
enum Nucleotide : char
{
  Adenine  = NUCLEOTIDE_F_AMINE  | NUCLEOTIDE_F_PURINE,
  Cytosine = NUCLEOTIDE_F_AMINE  | NUCLEOTIDE_F_PYRIMIDINE,
  Guanine  = NUCLEOTIDE_F_KETONE | NUCLEOTIDE_F_PURINE,
  Thymine  = NUCLEOTIDE_F_KETONE | NUCLEOTIDE_F_PYRIMIDINE
}
 
//New function: isAmine
inline bool isAmine(Nucleotide const & n) noexcept
{
  return n & NUCLEOTIDE_F_AMINE;
}
 
//New function: isKetone
inline bool isKetone(Nucleotide const & n) noexcept
{
  return n & NUCLEOTIDE_F_KETONE;
}
 
//New function: isPurine
inline bool isPurine(Nucleotide const & n) noexcept
{
  return n & NUCLEOTIDE_F_PURINE;
}
 
//New function: isPyrimidine
inline bool isPyrimidine(Nucleotide const & n) noexcept
{
  return n & NUCLEOTIDE_F_PYRIMIDINE;
}
 
//New function: areComplement
inline bool areComplement(Nucleotide const & n1, Nucleotide const & n2) noexcept
{
  return (n1 ^ n2) == NUCLEOTIDE_M_COMPLEMENT;
}
 
//New function: complementOf
inline Nucleotide complementOf(Nucleotide const & n) noexcept
{
  return static_cast< Nucleotide >(n ^ NUCLEOTIDE_M_COMPLEMENT);
}
 
//New function: charToNucleotide
Nucleotide charToNucleotide(char const & c)
{
  Nucleotide n = Adenine;
  switch(c)
  {
    case 'A':
    case 'a':
      break;
    case 'C':
    case 'c':
      n = Cytosine;
      break;
    case 'G':
    case 'g':
      n = Guanine;
      break;
    case 'T':
    case 't':
      n = Thymine;
      break;
    default:
      throw std::invalid_argument("Not a DNA nucleotide!");
      break;
  }
  return n;
}
 
//New function: nucleotideToChar
inline char nucleotideToChar(Nucleotide const & n) noexcept
{
  return (n & NUCLEOTIDE_F_AMINE) ?
             ((n & NUCLEOTIDE_F_PURINE) ? 'A' : 'C') :
             ((n & NUCLEOTIDE_F_PURINE) ? 'G' : 'T');
}
 
#undef NUCLEOTIDE_F_AMINE
#undef NUCLEOTIDE_F_KETONE
#undef NUCLEOTIDE_F_PURINE
#undef NUCLEOTIDE_F_PYRIMIDINE
#undef NUCLEOTIDE_M_COMPLEMENT
 
#endif // NUCLEOTIDE_H

Je me suis permis de remplacer A, C, G et T par Adenine, Cytosine, Guanine et Thymine du fait que c'est moins risqué en ce qui concerne les collisions de nommage.

17/03/2016, 14h16
bacelar

Citation:

On peut aussi mixer macros temporaires et énumérations.

Moi, je ne vois que des inconvénients à l'utilisation des MACRO ici, perte de typage, namespace aux fraises, etc...
17/03/2016, 14h43
VivienD

Citation:

Envoyé par bacelar

Moi, je ne vois que des inconvénients à l'utilisation des MACRO ici, perte de typage, namespace aux fraises, etc...

C'est vrai que les macros sont insensibles aux espaces de nommage et que le typage avec les macros peut relever de la gageure. Néanmoins, l'énumération Nucleotide n'a, grâce aux macros, que quatre valeurs disponibles, à savoir Adenine, Cytosine, Guanine et Thymine. Ainsi, les chances que l'utilisateur entre une valeur erronée, comme un drapeau seul ou un masque, au lieu d'un nucléotide valide sont réduites à zéro, ou presque (cf. loi de Murphy).

Dans ce cas-là, on préférera utiliser des expressions constantes.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
namespace DNA
{
    constexpr char NUCLEOTIDE_F_AMINE      = 0x01;
    constexpr char NUCLEOTIDE_F_KETONE     = 0x02;
    constexpr char NUCLEOTIDE_F_PURINE     = 0x04;
    constexpr char NUCLEOTIDE_F_PYRIMIDINE = 0x08;
    constexpr char NUCLEOTIDE_M_COMPLEMENT = 0x0f;
 
    enum Nucleotide : char
    {
        Adenine  = NUCLEOTIDE_F_AMINE  | NUCLEOTIDE_F_PURINE,
        Cytosine = NUCLEOTIDE_F_AMINE  | NUCLEOTIDE_F_PYRIMIDINE,
        Guanine  = NUCLEOTIDE_F_KETONE | NUCLEOTIDE_F_PURINE,
        Thymine  = NUCLEOTIDE_F_KETONE | NUCLEOTIDE_F_PYRIMIDINE
    };
}
 
int main()
{
    auto n = DNA::Adenine;
    std::cout << "0x0" << std::hex << n << std::endl;
 
    return 0;
}

Citation:
Envoyé par RPGamer
Dans ce cas-là, on préférera utiliser des expressions constantes.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <iostream> namespace DNA { constexpr char NUCLEOTIDE_F_AMINE = 0x01; constexpr char NUCLEOTIDE_F_KETONE = 0x02; constexpr char NUCLEOTIDE_F_PURINE = 0x04; constexpr char NUCLEOTIDE_F_PYRIMIDINE = 0x08; constexpr char NUCLEOTIDE_M_COMPLEMENT = 0x0f; enum Nucleotide : char { Adenine = NUCLEOTIDE_F_AMINE | NUCLEOTIDE_F_PURINE, Cytosine = NUCLEOTIDE_F_AMINE | NUCLEOTIDE_F_PYRIMIDINE, Guanine = NUCLEOTIDE_F_KETONE | NUCLEOTIDE_F_PURINE, Thymine = NUCLEOTIDE_F_KETONE | NUCLEOTIDE_F_PYRIMIDINE }; } int main() { auto n = DNA::Adenine; std::cout << "0x0" << std::hex << n << std::endl; return 0; }
Certes, ca règle aussi les problèmes de validité mais l'utilisateur final peut encore accéder aux drapeaux seuls et au masque. Si ca ne dérange pas, on peut laisser comme ca (ou même envoyer tout ca dans un sous-espace de nommage du genre DNA::bits puis regrouper les drapeaux et les masques dans les énumérations Nucleotide_Flags et respectivement Nucleotide_Masks); dans le cas contraire, je ne vois que les macros temporaires pour atteindre l'effet voulu.

17/03/2016, 16h01
RPGamer

~~Les macros n'empêchent pas plus l'accès aux valeurs par l'utilisateur, au contraire même.~~ J'avais pas vu que tu les désactive à la fin de ton fichier source.

Il y a une autre solution qui consiste à transformer DNA en classe principale et à placer les expressions constantes comme membres statiques privés de cette classe et les fonctions libres comme fonctions amies.
17/03/2016, 16h12
VivienD

Citation:

Envoyé par RPGamer

Les macros n'empêchent pas plus l'accès aux valeurs par l'utilisateur, au contraire même.

Regarde la fin de mon code aux lignes 112 à 116 et tu verras que je les "détruis" à coup de #undef. Et oui! ca marche: je me suis déjà servi de cette astuce à de maintes et maintes reprises.

EDIT:

Citation:

Envoyé par RPGamer

~~Les macros n'empêchent pas plus l'accès aux valeurs par l'utilisateur, au contraire même.~~ J'avais pas vu que tu les désactive à la fin de ton fichier source.

Il y a une autre solution qui consiste à transformer DNA en classe principale et à placer les expressions constantes comme membres statiques privés de cette classe et les fonctions libres comme fonctions amies.

C'est vrai; je n'y avais pas pensé.:aie:
20/03/2016, 17h51
bowow

Bonjour,

Je ne sais pas trop ce que tu recherches à faire, mais si la finalité est de faire de l'alignement de séquence, on ne peut se permettre de les stocker en mémoire vu la quantité de séquences dans les fichiers FASTQ et FASTA.

Par contre, si c'est un simple exercice pour enregistrer une séquence ADN en mémoire, trouver la séquence inverse, complémentaire, la séquence ARNm et polypeptidique, t'embêtes pas avec ces encodages.

De plus, il existe déjà des algorithmes de texte en bio-informatique et une multitude d'outils déjà préexistants qui feront sûrement ton JOB sans problème.
27/03/2016, 13h02
FryHandiz

Bonjour,
J'ai bien peur que vous alliez un peu trop loin pour moi... En effet, j'ai pas vraiment besoin de parler de kétone ou d'amine car je m'intéresse pour le moment qu'au séquence nucléotidique et pas aux acides aminés. Donc du coup, je suis partie vers quelque chose de plus simple.
Je suis partie du principe que A et T sont complémentaires et G et C le sont aussi.
Du coup, pour coder sur deux bits chaque nucléotide, j'ai dit que A = 00, T=11, G=10 et C=01. Comme ça pour le complémentaire, pas de souci.
Mon projet est à rendre bientôt et je n'aurai jamais le temps de le terminer, mes connaissances sont vraiment très limitées xD Ce devait en effet être pour de l'alignement de séquence, mapper les reads, etc, mais vu que je ne pourrais jamais y arriver je vais me contenter de petites choses x)
En tout cas, merci beaucoup pour votre aide !
27/03/2016, 23h53
VivienD

Citation:

Envoyé par FryHandiz

Bonjour,
J'ai bien peur que vous alliez un peu trop loin pour moi... En effet, j'ai pas vraiment besoin de parler de kétone ou d'amine car je m'intéresse pour le moment qu'au séquence nucléotidique et pas aux acides aminés. Donc du coup, je suis partie vers quelque chose de plus simple.
[...]

C'est vrai que nous nous sommes "un peu" emportés et que nous sommes bien plus loin que demandé en nous adonnant au débat ci-dessus. :aie:

Citation:

Envoyé par FryHandiz

[...]
Je suis partie du principe que A et T sont complémentaires et G et C le sont aussi.
Du coup, pour coder sur deux bits chaque nucléotide, j'ai dit que A = 00, T=11, G=10 et C=01. Comme ça pour le complémentaire, pas de souci.
[...]

Si tu te contentes de la complémentarité des nucléotides seule, cet encodage convient tout à fait. :)

Citation:

Envoyé par FryHandiz

[...]
Mon projet est à rendre bientôt et je n'aurai jamais le temps de le terminer, mes connaissances sont vraiment très limitées xD Ce devait en effet être pour de l'alignement de séquence, mapper les reads, etc, mais vu que je ne pourrais jamais y arriver je vais me contenter de petites choses x)
[...]

C'est vraiment dommage, ça... :? Toutefois, j'espère que ça ne te décourageras pas; dis-toi que ça n'est qu'à charge de revanche. ;)

Citation:

Envoyé par FryHandiz

[...]
En tout cas, merci beaucoup pour votre aide !

Mais, de rien. ;)
Après, je me permets de te conseiller de conserver ce fil de discussion sous le coude (en le mettant dans tes marque-pages, par exemple) car dans notre "délire" nous avons abordé différentes méthodes concernant la représentation de données via des champs de bits; c'est un sujet auquel tout développeur a souvent affaire, du moins plus souvent qu'on ne le croit. :mrgreen:

PS: Personnellement, je vais me garder ce fil dans mes marque-pages. En effet, ça serait regrettable, outrageant voire blasphématoire que de laisser autant de verve et de dévotion sombrer dans les profondeurs abyssales et pleines de microbes de l'oubli. :lun:
Tiens! J'en avais encore à revendre! :weird: