méthode pour encoder une séquence ADN

**FryHandiz** · 14/03/2016, 21h10

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 !

**Bousk** · 14/03/2016, 23h11

Salut,

te fatigues pas avec des considérations de quantité de mémoire.

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

**koala01** · 15/03/2016, 00h08

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

), 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

).

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 :

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

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 :

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

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

**LandReagan** · 15/03/2016, 07h11

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?

**Bousk** · 15/03/2016, 09h34

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.

**LandReagan** · 15/03/2016, 10h06

Ah ouais, je n'avais pas compris ça comme ça.

**ternel** · 15/03/2016, 10h18

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)

**VivienD** · 15/03/2016, 11h30

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 :

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

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üß

**RPGamer** · 15/03/2016, 13h31

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 :

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
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()

**jopopmk** · 15/03/2016, 14h08

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 :

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

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

**ternel** · 15/03/2016, 14h39

il n'est pas forcément nécessaire d'inverser la séquence, tu peux aussi parcourir un tableau par la fin:

Code :

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

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.

**koala01** · 15/03/2016, 14h41

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 :

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

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

**RPGamer** · 15/03/2016, 15h16

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

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
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;
}

**jopopmk** · 15/03/2016, 15h29

J'ai bien dit que j'étais pas expert en C++, et que mon exemple était "rapide"

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

**RPGamer** · 15/03/2016, 15h40

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

Code :

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

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?

**VivienD** · 15/03/2016, 15h58

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 :

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

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

Envoyé par RPGamer

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

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

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

**RPGamer** · 15/03/2016, 16h15

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

**VivienD** · 15/03/2016, 16h19

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.

**bacelar** · 15/03/2016, 17h13

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.

**jopopmk** · 15/03/2016, 17h56

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

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.

méthode pour encoder une séquence ADN

C++

Discussions similaires

Partager

Partager