Brevet FR2939929A1 — publié le 20100618

DOMAINE TECHNIQUE AUQUEL SE RAPPORTE L'INVENTION La présente invention concerne de manière générale le domaine du calcul par ordinateur et plus particulièrement une méthode d'accélération du calcul par ordinateur de la probabilité d'observer différentes séquences d'un nombre donné T d'arrangements d'un nombre p d'états observés d'une variable parmi une pluralité desdites séquences qui sont modélisées par un unique modèle de Markov caché. L'invention trouve une application particulièrement avantageuse en bioinformatique dans le calcul par ordinateur des paires d'haplotypes les plus 10 probables d'un individu de génotype connu. ARRIÈRE-PLAN TECHNOLOGIQUE De nombreux systèmes complexes rencontrés dans différents domaines comme la biologie, la finance, la physique ou la sociologie sont modélisés grâce à des modèles de Markov cachés. Ces modèles sont particulièrement utilisés en 15 biologie pour la reconstruction des haplotypes d'individus d'une population donnée à partir des génotypes de ces individus et d'informations génétiques sur cette population. Une autre application courante des modèles de Markov cachés concerne la reconnaissance vocale et manuscrite et de nombreux brevets ont été délivrés 20 ces dernières années concernant différentes méthodes de calculs de ces modèles, comme par exemple le brevet US7433820. Le principe des modèles de Markov cachés est décrit dans le document intitulé � A tutorial on hidden Markov model and selected applications in speech recognition � de L.R. Rabiner, publié dans la revue Proceedings of the IEEE en 25 1989 (volume 77(2), pages 257-285). Un modèle de Markov caché est un modèle statistique dans lequel les valeurs prises successivement par une variable étudiée dépendent des valeurs prises successivement par une autre variable. Les valeurs de la variable étudiée sont appelées les états observés du modèle, tandis que les valeurs prises par l'autre variable sont appelées les états cachés du modèle. 30 La variable étudiée peut par exemple être des paires d'allèles successives d'une paire de chromosomes étudiée dans le cas de la détermination des haplotypes, ou encore des phonèmes dans le cas de la reconnaissance vocale On suppose dans ce modèle que la probabilité d'observer, au temps t du 35 modèle, un état observé donné dépend de l'état caché dans lequel est l'autre variable du modèle à ce temps t, et que la succession dans le temps des états cachés obéit à un processus Markovien, c'est-à-dire que l'état caché de l'autre variable du modèle au temps t dépend uniquement de l'état caché de cette autre variable au temps t-1 par une probabilité de transition. C'est pourquoi lorsqu'un état observé est observé au temps t, on dit que l'état observé est émis par le modèle au temps t. On parlera dans la suite pour simplifier de l'état caché du modèle au temps t pour désigner l'état caché de l'autre variable du modèle. Le temps t désigne dans les modèles de Markov un compteur incrémenté à chaque étape du modèle. Le modèle peut également émettre un nombre quelconque p d'états observés au temps t. Une des applications classiques d'un modèle de Markov caché est le calcul de la probabilité que ce modèle de Markov émette une séquence particulière comportant un nombre T d'arrangements d'un nombre p d'états observés. Le terme de � séquence � désigne une suite ordonnée d'éléments. Chaque élément de cette séquence situé au rang t de cette séquence, c'est-à-dire en t-ième position dans la séquence, est constitué d'un arrangement de p états observés. L'expression � arrangement de p états observés � désigne ici un groupement ordonné d'un nombre p d'états observés de l'ensemble des états observés. Ces expressions seront reprises par la suite. Dans le cas des haplotypes, chez l'homme, le modèle de Markov caché autorise le calcul de la probabilité d'observer sur une paire de chromosomes données une séquence d'arrangements de deux allèles, c'est-à-dire une séquence de paires de deux allèles. II existe actuellement différents algorithmes de calcul par ordinateur d'une telle probabilité. L'un des algorithmes les plus utilisés est l'algorithme de propagation alpha bêta qui est décrit en détail dans le document précité publié par L.R. Rabiner. Cette algorithme autorise le calcul de la probabilité d'observer une séquence particulière d'états observés uniques, par le calcul de probabilités intermédiaires de sous-séquences d'états observés uniques. Selon cette méthode de l'état de la technique, décrite plus en détail ci- après, pour calculer les probabilités d'observation de plusieurs séquences d'arrangements de p états observés, le processeur de l'ordinateur est programmé de manière connue pour réaliser les étapes de cet algorithme alpha bêta, pour chaque séquence de l'ensemble des séquences étudiées, successivement, et pour chaque sous-séquence d'états observés uniques d'une même séquence. Chaque sous-séquence d'états observés uniques d'une séquence comporte, à chaque rang t de cette sous-séquence, l'état observé positionné à un rang u donné dans l'arrangement de p états observés situé au rang t correspondant de ladite séquence. Une telle application de la méthode de propagation alpha bêta est décrite dans le document intitulé � Accounting for decay of linkage disequilibrium in haplotype inference and missing-data imputation � publié par M. Stephens et P. Scheet dans l'American journal of human genetics (volume 76(3), pages 449-462) en 2005, et brevetée dans le brevet W002064617. Cette approche donne des résultats précis mais présente l'inconvénient d'être très coûteuse en temps de calcul, ce qui limite la taille des séquences considérées, c'est-à-dire le nombre d'arrangements d'états observés par 10 séquence ainsi que le nombre total de séquences prises en compte. OBJET DE L'INVENTION Afin de remédier à cet inconvénient de l'état de la technique, la présente invention a pour but d'accélérer le calcul par ordinateur de la probabilité d'observer différentes séquences d'un nombre donné T d'arrangements d'états observés 15 d'une variable de manière à diminuer le temps de calcul et/ou les ressources informatiques nécessaires à la réalisation de ce calcul. A cet effet, on propose selon l'invention une méthode de calcul par ordinateur de la probabilité d'observer chaque séquence d'un ensemble d'un nombre prédéterminé de séquences comportant chacune un nombre donné T 20 d'arrangements d'un nombre p d'états observés d'une variable modélisée par un modèle de Markov caché, chaque arrangement de p états observés de rang t de chaque séquence ayant été émis par ce modèle , au temps t de ce modèle correspondant audit rang t de chaque séquence, ledit modèle de Markov caché comportant un ensemble prédéfini d'états cachés, ledit ordinateur comportant au 25 moins un processeur et une mémoire, méthode selon laquelle le processeur effectue les tâches suivantes : a) classer lesdites séquences d'arrangements de p états observés selon un arbre informatique stocké dans ladite mémoire, cette tâche comportant les sous-étapes suivantes : 30 a1) enregistrer, dans les premiers noeuds de profondeur 1 dans l'arbre, chaque arrangement de p états observés de rang 1 desdites séquences, a2) enregistrer, dans chaque noeud de profondeur t comprise entre 2 et T, l'arrangement de p états observés de ladite variable situé au rang t correspondant de chaque séquence d'au moins une partie de l'ensemble desdites 35 séquences et un identifiant du noeud parent de profondeur t-1 de ce noeud de profondeur t, toutes les séquences dont les arrangements de p états observés sont identiques jusqu'au rang t étant regroupées sur une même branche de l'arbre qui s'étend de l'un desdits premiers noeuds à l'un desdits noeuds de profondeur t, b) calculer, pour chaque premier noeud de l'arbre et pour chaque état caché dudit modèle de Markov caché, une probabilité intermédiaire d'observer 5 chaque état observé de l'arrangement de p états observés de ladite variable enregistrée dans ce premier noeud , ledit modèle étant dans ledit état caché au temps 1 de ce modèle, c) calculer, pour chaque noeud de profondeur t comprise entre 2 et T-1, pour chaque état observé de rang u compris entre 1 et p dans l'arrangement de p 10 états observés enregistré dans le noeud de profondeur t correspondant, et pour chaque état caché dudit modèle de Markov caché, une probabilité intermédiaire d'observer la sous-séquence d'états observés uniques comportant à chaque rang compris entre 1 et t, l'état observé de rang u dans l'arrangement de p états observés situé au rang correspondant de la séquence considérée, cette sous- 15 séquence étant appelée sous-séquence d'états observés uniques de taille t et de rang u de la séquence considérée lorsque ledit modèle est dans ledit état caché au temps t de ce modèle et, d) calculer, pour chaque noeud terminal de l'arbre, la probabilité d'observer la séquence d'arrangements de p états observés de ladite variable 20 décrite par la branche de l'arbre menant du premier noeud correspondant audit noeud terminal de l'arbre. Ainsi, les calculs redondants car communs à deux séquences différentes ou plus sont éliminés, car les séquences comprenant des arrangements de p états observés identiques du rang 1 au rang t sont regroupées sur une même branche 25 de l'arbre. Le processeur effectue donc moins d'opérations. Le temps de calcul et/ou les ressources informatiques de l'ordinateur, telles que la taille de la mémoire ou la puissance du processeur, nécessaires à la réalisation du calcul de la probabilité d'observer lesdites différentes séquences sont réduites. Selon d'autres caractéristiques avantageuses de la méthode selon 30 l'invention, - les étapes b), c) et d) sont effectuées dans cet ordre, et lors de l'étape c), le processeur calcule d'abord, pour tous les noeuds de même profondeur t et pour tous les états cachés du modèle au temps t, lesdites probabilités intermédiaires d'observer lesdites sous-séquences d'états observés uniques de 35 taille t et de rang u, pour tous les rangs u compris entre 1 et p, lorsque ledit modèle est dans chaque état caché au temps t, puis, les probabilités intermédiaires d'observer les sous-séquences d'états observés de taille t+1 et de rang u, pour tous les rangs u compris entre 1 et p, lorsque ledit modèle est dans chaque état caché au temps t+1 ; - lors de l'étape c), le processeur calcule, pour chaque noeud de profondeur t comprise entre 2 et T-1, la probabilité d'observer la sous-séquence d'états observés uniques de taille t et de rang u, qui est égale à la somme des probabilités intermédiaires d'observer les sous-séquences d'états observés uniques de taille t et de rang u correspondant à ce noeud lorsque ledit modèle est dans chaque état caché au temps t, pour tous les états cachés du modèle au temps t; - lors de l'étape c), le processeur calcule, pour chaque noeud de profondeur t comprise entre 2 et T-1, la probabilité d'observer la sous-séquence d'arrangements de p états observés décrite par la branche de l'arbre menant du premier noeud correspondant audit noeud de profondeur t, appelée sous-séquence de taille t, qui est égale au produit, pour tous les rangs u compris entre 1 et p, desdites probabilités d'observer les sous-séquences d'états observés uniques de taille t et de rang u correspondant à ce noeud de profondeur t ; - lors de l'étape c), le processeur calcule les probabilités intermédiaires d'observer les sous-séquences d'états observés uniques de taille t+1 et de rang u correspondant à chaque noeud de profondeur t+1 si et seulement si la probabilité d'observer la sous-séquence de taille t correspondant au noeud de profondeur t parent dudit noeud de profondeur t+1 fait partie des Y plus grandes probabilités calculées par le processeur pour l'observation de toutes les sous-séquences de taille t ; - lors de l'étape c), le processeur calcule, pour chaque noeud de profondeur t, une probabilité normalisée d'observer la sous-séquence de taille t correspondante, cette probabilité normalisée étant égale à ladite probabilité d'observer la sous-séquence de taille t correspondante divisée par la somme des probabilités d'observer toutes les sous-séquences de taille t, et le processeur calcule les probabilités intermédiaires d'observer les sous-séquences d'états observés uniques de taille t+1 et de rang u correspondant à chaque noeud de profondeur t+1 si et seulement si la probabilité normalisée d'observer la sous-séquence de taille t correspondant au noeud de profondeur t parent dudit noeud de profondeur t+1 est supérieure à un seuil prédéterminé. L'invention concerne également une méthode telle que décrite précédemment, pour calculer par ordinateur la probabilité d'observer toutes les séquences pouvant être émises par ledit modèle de Markov et comportant un nombre T d'arrangements de p états observés, comportant l'étape préliminaire suivante : le processeur détermine toutes les séquences pouvant être émises par le modèle de Markov considéré et comportant un nombre T d'arrangements de p états observés, chaque état observé de l'arrangement de p états observés du rang t de chaque séquence appartenant à un ensemble d'états observés de ladite variable prédéterminé en fonction dudit temps t dudit modèle correspondant au rang t de cette séquence. L'invention concerne également une méthode de calcul par ordinateur de la probabilité d'observer toutes les séquences pouvant être émises par un modèle de Markov et comportant un nombre T d'arrangements de p états observés, chaque état observé de l'arrangement de p états observés du rang t de chaque séquence appartenant à un ensemble d'états observés de ladite variable prédéterminé en fonction du temps t dudit modèle correspondant au rang t de cette séquence et ledit modèle de Markov caché comportant un ensemble prédéfini d'états cachés, ledit ordinateur comportant au moins un processeur et une mémoire, méthode selon laquelle ledit processeur construit un arbre informatique dans ladite mémoire et effectue les tâches suivantes : e) déterminer toutes les combinaisons possibles de p états observés de l'ensemble prédéterminé d'états observés au temps 1 du modèle, f) enregistrer dans chaque premier noeud de profondeur 1 dans l'arbre, l'une des combinaisons de p états observés déterminée à l'étape e), g) calculer, pour chaque premier noeud, la probabilité d'observer la combinaison de p états observés de ladite variable enregistrée dans ce premier noeud, h) à chaque profondeur t successive dans l'arbre, avec t compris entre 2 et T-1, hl) déterminer tous les arrangements possibles de p états observés de l'ensemble prédéterminé d'états observés au temps t du modèle, h2) enregistrer, dans chaque noeud de profondeur t, chaque arrangement possible de p états observés déterminé à l'étape h1) et un identifiant du noeud parent de profondeur t- 1 de ce noeud de profondeur t, et h3) calculer la probabilité d'observer la sous-séquence d'arrangements de p états observés décrite par la branche de l'arbre menant du premier noeud correspondant audit noeud de profondeur t, appelée sous-séquence de taille t, i) pour chaque noeud terminal de l'arbre, i1) déterminer tous les arrangements possibles de p états observés de l'ensemble prédéterminé d'états observés au temps T du modèle, i2) enregistrer dans chaque noeud terminal de l'arbre, chaque arrangement possible de p états observés déterminé à l'étape i1) et un identifiant du noeud parent de ce noeud terminal, et i3) calculer la probabilité d'observer la séquence d'arrangements de p états observés de ladite variable décrite par la branche de l'arbre menant du premier noeud correspondant audit noeud terminal de l'arbre. Selon d'autres caractéristiques avantageuses et non limitatives de cette méthode : - lors des étapes g) et h3), le processeur calcule également, pour chaque noeud de profondeur t comprise entre 1 et T-1, une probabilité normalisée d'observer la sous-séquence de taille t correspondant à ce noeud, égale à ladite probabilité d'observer ladite sous-séquence divisée par la somme des probabilités d'observer toutes les sous-séquences de taille t, et le processeur effectue l'étape h) pour chaque noeud de profondeur t+1 si et seulement si la probabilité normalisée d'observer la sous-séquence de taille t correspondant au noeud de profondeur t parent dudit noeud de profondeur t+1 est supérieure à un seuil prédéterminé ; - le processeur effectue l'étape h) pour chaque noeud de profondeur t+1 si et seulement si la probabilité d'observer la sous-séquence de taille t correspondant au noeud de profondeur t parent dudit noeud de profondeur t+1 fait partie des Y plus grandes probabilités calculées par le processeur pour l'observation de toutes les sous-séquences de taille t. L'invention concerne enfin une méthode de détermination par ordinateur des arrangements de p haplotypes les plus probables d'un individu de génotype connu comportant un nombre T de polymorphismes appelés SNP, ces haplotypes étant modélisés par un modèle de Markov caché, grâce à la méthode précédemment décrite, dans laquelle - ladite variable correspond à l'allèle des SNP successifs de ce génotype, - l'ensemble des états observés possibles de cet allèle pour chaque SNP correspond aux allèles d'un ensemble de chromosomes ancestraux connus, - l'ensemble des états cachés du modèle correspond auxdits chromosomes ancestraux connus, - chaque séquence d'un nombre donné T d'arrangements de p états observés de l'allèle correspondant aux SNP successifs du génotype de l'individu est un arrangement de p haplotypes de l'individu, l'arrangement de p états observés de l'allèle de rang t de chaque séquence correspondant au SNP de rang t dudit génotype. DESCRIPTION DÉTAILLÉE D'UN EXEMPLE DE RÉALISATION La description qui va suivre, en regard des dessins annexés, donnée à titre d'exemple non limitatif, fera bien comprendre en quoi consiste l'invention et comment elle peut être réalisée. Sur les dessins annexés : - la figure 1 est une représentation schématique de séquences d'arrangements d'états observés sous forme de table ; - la figure 2 est un schéma représentant un exemple de modèle de Markov caché à deux états cachés et deux états observés ; - la figure 3 est une représentation schématique d'un ensemble de séquences d'états observés du modèle de Markov caché de la figure 2, représentées selon la méthode de calcul de propagation alpha bêta de l'état de la technique ; - la figure 4 est une représentation schématique de l'ensemble de séquences d'états observés du modèle de Markov caché de la figure 3, selon la présente invention ; - la figure 5 est une représentation schématique d'un arbre dans lequel sont classés les arrangements d'états observés des séquences, selon la présente invention ; - la figure 6 résume les grandes étapes de détermination d'une séquence de paires d'allèle la plus probable pour un génotype donné ; - les figures 7 et 8 représentent des tableaux de données décrits dans la description. Dans la suite de la description, différents modèles de Markov caché ~. sont décrits. Par souci de simplification, les paramètres se correspondant dans ces différents modèles sont désignés par les mêmes notations. Les termes définis dans l'arrière plan technologique dans le cadre de l'étude d'une variable modélisée par un modèle de Markov, notamment les expressions � états cachés du modèle �, � états observés émis par le modèle �, � séquence � et � arrangement � sont repris dans la suite de la description. L'expression � combinaison d'un nombre p d'états observés � désignera une partie non ordonnée de l'ensemble des états observés. Quel que soit le modèle de Markov caché considéré, les états cachés du modèle X sont au nombre de N et sont notés S =i . L'état caché du modèle au temps t est noté q, et appartient à l'ensemble S des états cachés du modèle. Une séquence de T états cachés du modèle est notée Q =9,'•• '9r. Le temps t désigne un compteur incrémenté à chaque étape du modèle. A chaque temps t du modèle de Markov caché, un seul état observé ou un arrangement de p états observés de la variable modélisée par ce modèle est observé: cet état observé ou cet arrangement d'états observés est situé dans la séquence Ox d'arrangements d'états observés émis par le modèle au rang t de cette séquence. La variable étudiée peut par exemple être des paires d'allèles successives d'une paire de chromosomes étudiée dans le cas de la détermination des haplotypes, ou encore des phonèmes dans le cas de la reconnaissance vocale. Les états observés Vk du modèle sont au nombre de M et appartiennent à l'ensemble V tel que V =} V,,...,VA,� . Le u-ième état observé émis par le modèle au temps t de la séquence Ox est noté oxt., et appartient à l'ensemble V des états observés du modèle. Ces états observés sont représentés sur la figure 1 qui sera décrite plus en détail ultérieurement. Le modèle est initialement dans l'état caché Si avec une probabilité initiale notée r. =Pr(q, =Si). L'ensemble de ces probabilités initiales pour les N 15 états cachés forme une distribution de probabilité it _(Ir,,...,nNj dont la somme pour 1 si sN est égale à 1. Les états cachés et observés du modèle 2\, sont interconnectés par des relations probabilistes. Dans le modèle X , on passe de l'état caché S; au temps t à l'état caché 20 S; au temps t+1 avec une probabilité de transition au entre deux états cachés telle que au =Pr(q,,, =S~ q, =S;) . L'ensemble de ces probabilités de transition entre deux états cachés pour les N états cachés forme une matrice de transition notée A a;; où 1 _ Chaque flèche du schéma est associée à la probabilité de transition ou d'émission correspondante notée en vis-à-vis. On suppose ici que l'ensemble des paramètres du modèle X considéré sont connus. La détermination de ces paramètres se fait par exemple par des processus d'apprentissage qui ne rentrent pas dans le cadre de ce brevet. L'une des utilisations d'un modèle de Markov caché X = ,t, A, B connu consiste à déterminer la probabilité que ce modèle émette une séquence particulière de T états observés uniques 0 =015•••,0,.. Cette probabilité est notée Pr(O X). Dans l'exemple ci-dessus, le modèle de Markov caché peut par exemple 25 permettre de calculer la probabilité d'observer la séquence d'états observés suivante : 01 = V,, V,, V,, V2, V1, V2, V,. Selon une première méthode de l'état de la technique, le processeur est programmé pour réaliser le calcul de Pr(O I a,) directement par l'expression suivante: Pr(01X) =1Pr(OIQ,X)Pr(QIX) 30 e où la somme est réalisée sur toutes les séquences d'états cachés possibles. Avec Q =q,, qr et O le processeur applique les formules suivantes : 35 Pr ( Q =q1,...,q. 1 2,.) =Ir q,aq,q,ag2g3...aqr-,qr et Pr(O =o1,...,or 1 Q =g1,...,gr,X) =bq (ol)bgZ (o2)...bgr (or) Avec cette méthode de l'état de la technique, le processeur calcule par exemple successivement la probabilité de chaque séquence d'états observés représentée dans la liste de la figure 3. Cependant, le temps de calcul nécessaire au processeur pour réaliser le calcul de la probabilité d'observer une séquence d'états observés augmente exponentiellement avec le nombre d'états observés de chaque séquence. En effet, le processeur doit alors effectuer de l'ordre de NT opérations du fait qu'il y a NT séquences cachées possibles de taille T Les ordinateurs actuels ne peuvent effectuer ces calculs lorsque T est grand. Ceci est notamment le cas dans les calculs des haplotypes chez l'homme, où le nombre T d'arrangements de deux états observés à prendre en compte dans chaque séquence est souvent de l'ordre de plusieurs centaines. Selon une autre méthode de l'état de la technique, le processeur de l'ordinateur est programmé pour calculer cette probabilité selon l'algorithme de propagation alpha bêta. Pour calculer la probabilité d'observer, dans le modèle X , une séquence O =o,,...,oT donnée de T états observés uniques (figure 1, ligne 1), le processeur calcule alors successivement, pour chaque état observé de rang t de cette séquence O, la probabilité intermédiaire a, (i) d'observer la sous-séquence ol,•••,o, des états observés de la séquence O jusqu'au rang t, appelée sous-séquence d'états observés uniques de taille t, lorsque que le modèle se trouve au temps t dans l'état caché S;. Ceci se traduit par la formule : a, (i) =Pr(o,,...,o,,q, =S; 1 X) Le processeur calcule ces probabilités intermédiaires ut( i) pour tous les états cachés S, du modèle X et pour chaque état observé de la séquence O =o,,...,oT , soit N valeurs de la probabilité intermédiaire a, (i) par état observé, avec les relations récursives suivantes : al(i) =n;b,(o,) a,+! (i) = fat( j)a), En d'autres termes, la probabilité intermédiaire d'observer le premier état observé d'une séquence lorsque le modèle est dans l'état caché Si est égale au produit de la probabilité initiale que le modèle soit dans l'état caché S, par la probabilité d'émission du premier état observé de la séquence, et la probabilité intermédiaire d'observer l'état observé de rang t+1 d'une séquence lorsque le modèle est dans l'état caché Si est égale à la somme sur tous les états cachés du modèle du produit de la probabilité intermédiaire d'observer l'état observé de rang t de la séquence par la probabilité de transition entre l'état caché S, et un autre état caché du modèle par la probabilité d'émission de l'état observé de rang t+1 lorsque le modèle est dans cet autre état caché. Une fois les valeurs des probabilités intermédiaires a, (i) obtenues pour les T états observés, le processeur calcule la probabilité d'observer la séquence O Pr(O I x) en sommant les probabilités intermédiaires calculées au rang T pour la séquence O complète sur tous les états cachés possibles, c'est-à-dire pour i variant de 1 à N, selon la formule Pr(01x) =ZIXT (i) Pour effectuer le calcul de Pr(O I X.) par cet algorithme de propagation alpha bêta, le processeur effectue ici de l'ordre de T*N2 opérations. Comme expliqué précédemment, le modèle de Markov caché peut émettre un nombre p d'état observé à chaque temps t, et l'ensemble des états observés possibles pour la variable à chaque temps t peut varier. Dans le cas où le modèle de Markov caché émet un nombre p d'états observés à chaque temps t, selon cette méthode de l'état de la technique, le processeur calcule la probabilité d'observer une séquence Ox d'arrangements de p états observés (ox1,1ioxl,2,••.ox1,p; OX2,1,OX2,2•.•OX2,P; .... ;OXT1,OXT2•••oxTp) en calculant la probabilité d'observer un arrangement correspondant de p séquences d'états observés uniques (Ox1,1,0x2,1,...OXT,1),(OX1,2,0x2,2...OxT2),...(oX,,p,Ox2,p...OXTp) de la variable. En pratique, dans la mémoire de l'ordinateur, chaque séquence Ox d'arrangements d'états observés oxt,u est stockée sous la forme d'une table ou d'une matrice dont chaque enregistrement contient un état observé du modèle. Pour l'état observé noté oxt,u , l'exposant x indique à quelle séquence de l'ensemble des séquences appartient ledit état observé, l'indice t indique le rang t de ladite séquence de l'arrangement de p états observés auquel appartient ledit état observé et l'indice u indique le rang u de cet état observé dans ledit arrangement de rang t de la séquence Ox. Comme le montre la figure 1, lignes 2 et 3, les états observés oxt,u, avec u compris entre 1 et p, de l'arrangement Dxt de rang t de chaque séquence correspondent aux enregistrements de la table disposés dans la colonne d'indice t de cette table. Chaque sous-séquence d'états observés uniques de taille T et de rang u (ox1,u,ox2,u,...oxTu) de chaque arrangement de la séquence correspond aux enregistrements de la table disposés sur la ligne d'indice u et est désignée par la référence Exu. Pour calculer la probabilité d'observer l'arrangement de p séquences d'états observés uniques (oxl,u,ox2,u,...oxTu), le processeur calcule comme décrit précédemment, selon l'algorithme de propagation alpha bêta, la probabilité 13 d'observer chacune des p séquences d'états observés uniques (0X1,1,0X2,1,...OXTI),(OX,,2,0X22...OXT2),...(ox,,p,oX2,p...OXTp), puis le processeur calcule la probabilité d'observer la séquence OX d'arrangements de p états observés (OX1,1,OX1,2,...OX1,p; OX2,1,OX2,2...OX2,p; .... ;0XT,1,OXT2...OXT,p) en multipliant ces p probabilités d'observer chacune des p séquences d'états observés uniques de taille T. Selon cette méthode de l'état de la technique, pour calculer les probabilités d'observer un nombre I de séquences O1 ...0' d'arrangements de p états observés du modèle, le processeur applique p*l fois l'algorithme alpha bêta exposé. Le nombre d'opérations nécessaires au calcul d'une séquence restant élevé, le nombre total de séquence pouvant être prises en compte par cette méthode est limité. La présente invention propose d'accélérer le calcul par le processeur des probabilités d'observer chaque séquence d'un ensemble d'un nombre donné I de séquences comportant chacune un nombre T d'arrangements de p états observés en éliminant les calculs de probabilités intermédiaires redondants dans l'ensemble des différentes séquences considérées. Pour cela, le processeur de l'ordinateur est programmé pour effectuer les tâches correspondant aux étapes décrites ci-après. Les I séquence OX d'arrangement d'états observés oXt,, sont représentées 20 dans différentes tables, comme le montre la figure 1, ligne 3. Construction de l'arbre informatique. Le processeur est programmé pour, dans une étape a), classer lesdites séquences d'arrangements de p états observés selon un arbre informatique stocké dans la mémoire de l'ordinateur. Cet arbre comporte par exemple un noeud 25 racine vide ou contenant un enregistrement quelconque ainsi qu'une pluralité d'ensemble de noeuds nkt de profondeur t. L'indice k de la notation nkt indique la position du noeud nkt dans l'ensemble des noeuds de profondeur t. Cet indice sera omis dans la suite de la description lorsque l'on considère l'un des noeuds de profondeur t quelconque parmi l'ensemble des noeuds de profondeur t, ce noeud 30 de profondeur t quelconque sera donc noté nt. L'arbre informatique est équivalent à une base de données informatique dans laquelle les enregistrements du champ t correspondent à chaque noeuds nt de profondeur t dans l'arbre. Comme représenté schématiquement sur la figure 5, chaque noeud nt de 35 profondeur t dans l'arbre est ici défini comme un enregistrement de base de données informatique contenant au moins un arrangement Dnt de p états observés et un identifiant du noeud parent nt-, de profondeur t-1 du noeud nt de profondeur t. Dans le cas de I séquences OX d'états observés uniques telles que représentées sur la figure 1, ligne 1, chaque noeud nt de l'arbre contient l'un des états observé oXt de rang t de l'une de ces I séquences OX. Cet état observé est noté 0,,, . Dans le cas de I séquences OX d'arrangements Dxt de p états observés telles que représentées sur la figure 1, ligne 2 et 3, chaque noeud nt de l'arbre contient l'un des arrangements de p états observés Dxt de rang t de l'une de ces I séquences OX. Les états observés de cet arrangement de p états observés sont notés ont,u. L'arrangement contenu dans chaque noeud de profondeur t est noté Dnt. L'arbre comporte trois types de noeuds. Les premiers noeuds ont comme parent le noeud racine noté R sur la figure 5. Ce noeud racine joue uniquement un rôle de référence pour l'initiation de l'arbre et il est par exemple vide. Les noeuds internes de l'arbre ont un noeud parent qui n'est pas le noeud racine et au minimum un noeud enfant. Les noeuds terminaux de l'arbre ont un noeud parent mais aucun noeud enfant. Pour les I séquences de l'ensemble des séquences, il y aura I noeuds terminaux dans l'arbre. Le processeur effectue dans l'étape a) les sous-étapes suivantes : a1) enregistrer, dans les premiers noeuds n, de profondeur 1 dans l'arbre, chaque arrangement de p états observés de rang 1 desdites séquences OX, a2) enregistrer, dans chaque noeud nt de profondeur t comprise entre 2 et T, l'arrangement de p états observés de ladite variable du rang t correspondant 25 de chaque séquence d'au moins une partie de l'ensemble desdites séquences et un identifiant du noeud parent nt_, de profondeur t-1 de ce noeud nt de profondeur t, toutes les séquences dont les arrangements de p états observés sont identiques jusqu'au rang t étant regroupées sur une même branche de l'arbre qui 30 s'étend de l'un desdits premiers noeuds n, à l'un desdits noeuds nt de profondeur t. Lors de l'étape a1), le processeur enregistre également dans chaque noeud n, un identifiant du noeud racine correspondant. En référence à la figure 1, ligne 3, dans l'étape a1) de la méthode, le processeur enregistre dans chaque premier noeud n, de l'arbre les colonnes 1 35 desdites tables qui correspondent aux arrangements DX, d'états observés. Dans l'étape a2), le processeur enregistre dans chaque noeud nt de profondeur t comprise entre 2 et T la colonne d'indice t d'au moins une partie desdites tables. Les noeuds nt de profondeur t dans l'arbre contiennent donc les colonnes d'indice t desdites tables, qui correspondent aux arrangements Dxt d'états observés de rang t de chaque séquence OX correspondante, arrangements Dxt qui regroupe les états observés émis par le modèle au temps t de ce modèle et sont notés de manière générale dans l'arbre Dnt. Dans ledit arbre informatique, deux séquences OX et OY sont sur une même branche, c'est-à-dire un même chemin jusqu'au noeud de profondeur t si et seulement si o; 'oiv,...,o =o, et °f+, ≠Ol , dans le cas d'un modèle n'émettant qu'un seul état observé à chaque temps t. Le processeur traite alors un ensemble de séquences semblables à celle de la figure 1, ligne 1. La figure 4 montre par exemple la classification en arbre des séquences de la liste de la figure 3. Dans le cas d'un modèle émettant p états observés à chaque temps t, deux séquences OX et OY sont sur une même branche, c'est-à-dire un même chemin jusqu'au noeud de profondeur t lorsque : / T Y / x Y ' r Y T ù Y x ù Y x ù °I,P ù°t,P °z,P ù°Z.P °~,P ù°~,p Le processeur peut également enregistrer dans chaque noeud nt un identifiant de l'ensemble des noeuds enfants i n,+,j de ce noeud nt. Cet ensemble 20 peut être vide. Ces étapes a1) et a2) correspondent à la transformation des I tables utilisées pour le calcul séquentiel selon l'état de la technique des probabilités des séquences correspondantes, représentées sur la figure 1, ligne 3, en un arbre adapté à être exploré de manière plus rapide et plus efficace, comme représenté 25 sur la figure 5. Calcul des probabilités intermédiaires correspondant aux états observés enregistrés dans chaque premier noeud de l'arbre. Selon la présente invention, le processeur effectue également les tâches décrites ci-après. 30 Dans une étape b), il calcule, pour chaque premier noeud n, de l'arbre et pour chaque état caché S; dudit modèle de Markov caché, la probabilité intermédiaire d'observer chaque état observé on,,u de l'arrangement de p états observés de ladite variable enregistré dans ce premier noeud n,, ledit modèle étant dans ledit état caché S; au temps 1 du modèle. 35 Dans le cas simple du modèle de Markov décrit précédemment, le modèle n'émet qu'un seul état observé on au temps t et chaque arrangement de p états observés ne contient qu'un seul état observé de la variable : p est égale à 1. Le processeur calcule alors les N probabilités intermédiaires associées à l'état observé o,, de chaque noeud n, de profondeur 1 qui sont égales au produit de la probabilité initiale que le modèle soit dans l'état caché S. au temps 1 par la probabilité d'émission de l'état observé. Les probabilités intermédiaires associées à l'état observé O,, du noeud n, vérifient ainsi l'équation suivante : aä (i)=itb;(oä) Dans l'exemple de l'arbre représenté sur la figure 4, le processeur calcule les probabilités intermédiaires associées aux deux seuls noeuds de profondeur 1 contenant chacun l'un des deux états observés possibles V, et V2. Dans le cas d'un modèle de Markov émettant p états observés au temps t, le processeur calcule la probabilité intermédiaire d'observer chaque état observé onl de l'arrangement de p états observés de ladite variable enregistré dans chaque premier noeud lorsque le modèle est dans l'état caché Si. Le processeur calcule donc la matrice de P XN probabilités 15 intermédiaires associée à chaque noeud n, de profondeur 1 avec am,. (i) =71;b; (o,, �) où i est compris entre 1 et N et u est compris entre 1 et p. Calcul des probabilités intermédiaires correspondant aux états observés enregistrés dans chaque noeud de profondeur t dans l'arbre. Dans une étape c), il calcule pour chaque noeud de profondeur t 20 comprise entre 2 et T-1, pour chaque état observé de rang u compris entre 1 et p dans l'arrangement de p états observés enregistré dans le noeud de profondeur t correspondant, et pour chaque état caché dudit modèle de Markov caché, une probabilité intermédiaire d'observer la sous-séquence d'états observés uniques comportant à chaque rang compris entre 1 et t, l'état observé de rang u dans 25 l'arrangement de p états observés situé au rang correspondant de la séquence considérée, cette sous-séquence étant appelée sous-séquence d'états observés uniques de taille t et de rang u de cette séquence, ledit modèle étant dans ledit état caché au temps t de ce modèle. Comme représenté sur la figure 1, ligne 3, chaque sous-séquence CXt,u 30 d'états uniques de taille t et de rang u de chaque séquence comporte les états observés situés sur la ligne d'indice u de la table correspondante dans les colonnes d'indices 1 à t. L'arbre permet de ne représenter et donc de ne calculer qu'une fois les sous-séquences identiques de toutes les séquences de l'ensemble des séquences. 35 Dans l'exemple de l'arbre représenté sur la figure 4, le processeur calcule les probabilités intermédiaires associées aux noeuds de profondeur 2 à 6 contenant chacun l'un des deux états observés possibles V, et V2. Dans le cas simple du modèle de Markov émettant un seul état observé à chaque temps t, chaque noeud nt de profondeur t comportant un noeud parent unique nt_, de profondeur t-1 associé aux probabilités intermédiaires an,_ i (i) , dans le cas simple où p est égale à 1, le processeur calcule la probabilité intermédiaire associée à l'état observé ont de chaque noeud nt de profondeur t lorsque le modèle est dans l'état caché S, au temps t du modèle en sommant sur tous les états cachés de ce modèle le produit de la probabilité intermédiaire associée au noeud parent dudit noeud nt de profondeur t pour un état caché Si par la probabilité de transition entre cet état caché Si et l'état caché Si du modèle que multiplie la probabilité d'émission de l'état observé ont du noeud nt considéré par le modèle dans l'état caché S. Chaque probabilité intermédiaire associée à l'état observé de chaque noeud nt de profondeur t pour chaque état caché S, de l'exemple de modèle de Markov décrit précédemment vérifie ainsi l'équation a.,, ( t) _man,., (.i) a,, b, (°,,,) . Le processeur calcule ainsi N probabilités intermédiaires pour chaque noeud nt de profondeur t dans l'arbre. Dans le cas du modèle de Markov émettant p états observés au temps t, le processeur calcule la matrice de P XN probabilités intermédiaires associée à chaque noeud nt de profondeur t. La probabilité intermédiaire de chaque sous- séquence Cxt,u d'états observés uniques de taille t et de rang u de la séquence Ox considérée, lorsque ledit modèle est dans ledit état caché S, au temps t de ce N modèle est calculée par la formule an,.0 (i) = b ,(0 , , , . , , ) où i est compris entre 1 et N et u est compris entre 1 et p. Calcul de la probabilité d'observer chaque séquence associée aux 25 noeuds terminaux de l'arbre. Dans une étape d), le processeur calcule, pour chaque noeud terminal de l'arbre, la probabilité d'observer la séquence d'arrangements de p états observés de ladite variable décrite par la branche de l'arbre menant du premier noeud correspondant audit noeud terminal de l'arbre. 30 Dans l'exemple de l'arbre représenté sur la figure 4, le processeur calcule la probabilité de chaque séquence O' à 06 correspondant aux branches de l'arbre menant aux noeuds de profondeur 7. Dans le cas général, les noeuds terminaux sont notés nT, et contiennent chacun un arrangement DnT de p états observés. 35 Le noeud parent du noeud nT de profondeur T étant le noeud nT_, de profondeur T-1 associé aux probabilités intermédiaires anT., (i) , dans le cas simple du modèle de Markov où p est égale à 1, le processeur calcule la probabilité intermédiaire associée à l'état observé de chaque noeud nT terminal pour chaque état caché Si du modèle en sommant sur tous les états cachés de ce modèle le produit de la probabilité intermédiaire associée au noeud parent nT_, du noeud nT pour un état caché Si par la probabilité de transition entre cet état caché S, et l'état caché Si du modèle que multiplie la probabilité d'émission de l'état observé considéré par le modèle dans l'état caché Si. En d'autres termes, le processeur calcule chacune des N probabilités intermédiaires associées à nT par la formule suivante : c,, (i) = b;(o, ) Ensuite, le processeur calcule dans cette étape d), pour chaque noeud terminal de l'arbre, la probabilité de la séquence OX correspondant à ce noeud terminal en sommant les probabilités intermédiaires associées à l'état observé du noeud nT pour tous les états cachés du modèle, selon la formule suivante : Pr(O lx) =Xa, (i) Dans le cas du modèle de Markov émettant p états observés au temps t, pour calculer la probabilité d'observer chaque séquence OX de l'ensemble des I séquences d'arrangements de p états observés de ladite variable correspondant à chaque noeud terminal, le processeur calcule tout d'abord les probabilités intermédiaires d'observer chacune des p sous-séquences EXu d'états observés uniques de taille T et de rang u (ox,,2,oX2,2...oxT,2),...(ox,,P,ox2,p...oxTp) comprises dans la séquence d'arrangements de p états observés correspondant audit noeud terminal lorsque le modèle est dans chacun de ses états cachés au temps T, pour tous les états cachés du modèle. Comme le montre la figure 1, ligne 3, chaque sous-séquences d'états observés uniques de taille T et de rang u notée EXu comporte les états observés situés sur la ligne d'indice u de la table correspondante, dans les colonnes d'indices 1 à T. L'arbre permet de ne représenter et donc de ne calculer qu'une fois les sous-séquences identiques de toutes les séquences de l'ensemble des séquences. Puis, pour chaque noeud terminal, il calcule la probabilité d'observer chacune des p sous-séquences EXu d'états observés uniques de taille T et de rang u (ox,,,,ox2,,,...oxT,,), (0X1,2,oX2,2...oXT2),...(oX1,p,oX2,P...OXT,p) comprises dans la séquence OX d'arrangements de p états observés correspondant audit noeud terminal nT en sommant les probabilités intermédiaires d'observer chacune des p sous- séquences d'états observés uniques de taille T et de rang u pour tous les états cachés du modèle. Ensuite, dans cette étape d), le processeur calcule la probabilité d'observer la séquence OX complète correspondant à chaque noeud terminal n-r en multipliant, pour chaque noeud terminal nT, les probabilités d'observer les sous-séquences d'états observés uniques de taille T et de rang u correspondant audit noeud terminal pour tous les rangs u compris entre 1 et p, selon la formule suivante : P N Pr(Ox lx) =1-1anrä(i) L'ensemble des p*N valeurs des probabilités intermédiaires an,,,, (i) avec 1 Pour cela, le processeur enregistre dans chaque noeud nt un identifiant de l'ensemble des noeuds enfants nt+, de ce noeud nt, et il effectue les étapes b), c) et d) pour tous les noeuds d'une même branche de l'arbre jusqu'à une profondeur t préfixée de l'arbre avant de passer aux noeuds d'une autre branche de l'arbre. Grâce à la méthode selon l'invention, le processeur n'effectue aucun calcul identique plusieurs fois pour calculer les probabilités de l'ensemble des séquences. Le temps de calcul nécessaire à la détermination des probabilités d'observer différentes séquences d'états observées peut ainsi être considérablement diminué. Cette diminution dépend évidemment des ressemblances existant entre les différentes séquences considérées. En variante, selon l'invention, quel que soit le mode de réalisation de l'invention, lors de l'étape c), le processeur calcule, pour chaque noeud nt de profondeur t comprise entre 2 et T-1, la probabilité d'observer la sous-séquence Cxt,u d'états observés uniques de taille t et de rang u (ox,,u,ox2,u,...oxt,u) qui est égale à la somme des probabilités intermédiaires d'observer les sous-séquences Cxt,u d'états observés uniques de taille t et de rang u correspondant à ce noeud, lorsque ledit modèle est dans ledit état caché au temps t, pour tous les états cachés du modèle au temps t. Comme exposé précédemment, chaque sous-séquence Cxt, d'états observés uniques de taille t et de rang u comporte les états observés situés sur la ligne d'indice u de la table correspondante, dans les colonnes d'indices 1 à t. En outre, lors de l'étape c), le processeur peut être programmé pour calculer, pour chaque noeud nt de profondeur t comprise entre 2 et T-1, la probabilité d'observer la sous-séquence d'arrangements de p états observés décrite par la branche de l'arbre menant du premier noeud n, correspondant audit noeud nt de profondeur t, appelée sous-séquence de taille t, qui est égale au produit, pour tous les rangs u compris entre 1 et p, desdites probabilités d'observer les sous-séquences Cxt,, d'états observés uniques de taille t et de rang u correspondant à ce noeud de profondeur t. Sur la figure 1, ligne 3, chaque sous-séquence de taille t comporte les arrangements d'états observés décrits par les t premières colonnes de la table correspondante. Elle est notée Fxt. Les calculs effectués par le processeur dans cette variante de la méthode selon l'invention autorise avantageusement la détermination des séquences de l'ensemble des différentes séquences considérées qui sont les plus probables, c'est-à-dire qui présentent la plus grande probabilité d'observation. Pour cela, de préférence, le processeur ne procède pas au calcul des probabilités des sous-séquences Fxt+, de taille t+1 correspondant aux noeuds de profondeur t+1 si la probabilité d'observer la sous-séquence Fxt de taille t correspondant aux noeuds parents de profondeur t de ces noeuds est trop faible. Pour cela, le processeur effectue une sélection, selon leur probabilités normalisées, des sous-séquences Fxt de taille t de l'arbre les plus probables. Le processeur est alors programmé pour, lors de l'étape c), - calculer, pour chaque noeud nt de profondeur t dans l'arbre, une probabilité normalisée d'observer la sous-séquence Fxt de taille t correspondante, cette probabilité normalisée étant égale à ladite probabilité d'observer la sous- séquence Fxt de taille t correspondante divisée par la somme des probabilités d'observer toutes les sous-séquences Pt de taille t avec y compris entre 1 et I, et - calculer les probabilités intermédiaires d'observer la sous-séquence Cxt+,,u d'états observés uniques de taille t+1 et de rang u correspondant à chaque noeud nt+, de profondeur t+1 si et seulement si la probabilité normalisée d'observer la sous-séquence Fxt de taille t correspondant au noeud nt de profondeur t parent dudit noeud nt+, de profondeur t+1 est supérieure à un seuil prédéterminé. Ce seuil peut être par exemple compris entre 0,00001 et 0,1. Pour un seuil très faible, beaucoup de sous-séquences sont sélectionnées par le processeur et les probabilités de beaucoup de séquences complètes sont calculées. Pour un seuil élevé, seules les séquences de très fortes probabilités sont déterminées. Alternativement, on peut envisager que le processeur détermine les Y séquences dont l'observation est la plus probable dans un modèle de Markov donné ainsi que leur probabilité d'observation. Pour cela, le processeur est programmé pour calculer, lors de l'étape c), les probabilités intermédiaires d'observer les sous-séquences Cxt,U de taille t d'états observés uniques de taille t+1 et de rang u correspondant à chaque noeud de profondeur t+1 si et seulement si la probabilité d'observer la sous-séquence Fxt de taille t correspondant au noeud de profondeur t parent dudit noeud de profondeur t+1 fait partie des Y plus grandes probabilités calculées par le processeur pour l'observation de toutes les sous-séquences Fyt de taille t où y est compris entre 1 et I. Le temps de calcul est alors en outre réduit, puisque seules les probabilités des séquences les plus probables sont calculées par le processeur. L'invention concerne également une méthode de détermination des séquences les plus probables comportant un nombre donné T d'arrangements de p états observés d'une variable, chaque arrangement de p états observés de rang t de chaque séquence ayant été émis par un modèle de Markov caché au temps t de ce modèle, et chaque état observé de l'arrangement de p états observés de rang t de chaque séquence appartenant à un ensemble d'états observés de ladite variable qui est prédéterminé en fonction du temps t correspondant à chaque rang t desdites séquences. Cette méthode réalise une nouvelle fonction appelée exploration, qui permet par exemple dans le cas d'une application à la détermination des paires d'haplotypes humains, d'explorer très rapidement toutes les paires d'haplotypes possible pour un génotype donné et de déterminer les paires les plus probables ainsi que leur probabilité d'observation. Cet exemple est décrit plus en détail ci- après. Le processeur est ainsi également programmé pour déterminer quelles séquences de taille T d'arrangements de p états observés sont le plus probablement générées par le modèle de Markov caché 2\, 31,A,Bj . Pour cela, le processeur détermine par exemple, préalablement aux étapes décrites précédemment, l'arbre de toutes les séquences possibles comportant T arrangements de p états observés. Les états observés de chaque arrangement de p états observés du rang t de la séquence font partie de l'ensemble des états observés prédéterminé en fonction du temps t de ce modèle. Cet ensemble prédéterminé des états observés ne dépend de préférence que du temps t du modèle de Markov caché, c'est-à-dire du rang t considéré. Le processeur réalise ensuite les étapes de la méthode décrite précédemment. Avantageusement, le processeur peut en variante être programmé de manière à construire cet arbre progressivement de temps t en temps t+9, tout en calculant les probabilités associées à chaque arrangement de p états observés enregistré dans chaque noeud de l'arbre. En outre, le processeur est programmé pour sélectionner à chaque profondeur t dans l'arbre les noeuds contenant les arrangements de p états observés associés aux probabilités intermédiaires les plus grandes. Les noeuds nt+, dans l'arbre de profondeur t+1 ne sont construits qu'à partir de ces noeuds nt de profondeur t sélectionnés. Le processeur est alors programmé pour réaliser les tâches décrites ci-après. Construction de l'arbre et calcul des probabilités d'observer chaque séquence. e) déterminer toutes les combinaisons possibles de p états observés de l'ensemble prédéterminé d'états observés au temps 1 du modèle, f) enregistrer dans chaque premier noeud n, de profondeur 1 dans l'arbre, l'une des combinaisons de p états observés déterminée à l'étape e), g) calculer, pour chaque premier noeud n, , la probabilité d'observer la 5 combinaison de p états observés de ladite variable enregistrée dans ce premier noeud n,, h) à chaque profondeur t successive dans l'arbre, avec t compris entre 1 et T-1, h1) déterminer tous les arrangements possibles de p états observés de l'ensemble prédéterminé d'états observés au temps t du modèle, h2) enregistrer, 10 dans chaque noeud nt de profondeur t, chaque arrangement possible de p états observés déterminé à l'étape h1) et un identifiant du noeud parent de profondeur t-1 de ce noeud nt de profondeur t, et h3) calculer la probabilité d'observer la sous-séquence d'arrangements de p états observés décrite par la branche de l'arbre menant du premier noeud correspondant audit noeud nt de profondeur t, appelée 15 sous-séquence de taille t, i) pour chaque noeud terminal nT de l'arbre, i1) déterminer tous les arrangements possibles de p états observés de l'ensemble prédéterminé d'états observés au temps T du modèle, i2) enregistrer dans chaque noeud terminal nT de l'arbre, chaque arrangement possible de p états observés déterminé à l'étape i1) 20 et un identifiant du noeud parent de ce noeud terminal nT, et i3) calculer la probabilité d'observer la séquence d'arrangements de p états observés de ladite variable décrite par la branche de l'arbre menant du premier noeud n, correspondant audit noeud terminal nT de l'arbre. Lors de l'étape f), le processeur enregistre également dans chaque 25 noeud n, un identifiant du noeud racine de l'arbre correspondant. Sélection, selon leurs probabilités normalisées, des sous-séquences de l'arbre les plus probables. De préférence, selon une première méthode de sélection des noeuds correspondant aux séquences les plus probables, lors des étapes g) et h3), le 30 processeur calcule également, pour chaque noeud nt de profondeur t comprise entre 1 et T-1, une probabilité normalisée d'observer la sous-séquence de taille t correspondant à ce noeud nt, égale à ladite probabilité d'observer ladite sous-séquence divisée par la somme des probabilités d'observer toutes les sous-séquences de taille t, et le processeur effectue l'étape h) pour chaque noeud nt+, 35 de profondeur t+1 si et seulement si la probabilité normalisée d'observer la sous-séquence de taille t correspondant au noeud nt de profondeur t parent dudit noeud nt+, de profondeur t+1 est supérieure à un seuil prédéterminé. Ce seuil peut être par exemple compris comme précédemment entre 0,00001 et 0,1. Sélection, selon leurs probabilités, des sous-séquences de l'arbre les plus probables. Alternativement, selon une deuxième méthode de sélection des noeuds correspondant aux séquences les plus probables, le processeur effectue l'étape h) pour chaque noeud de profondeur t+1 si et seulement si la probabilité d'observer la sous-séquence de taille t correspondant au noeud de profondeur t parent dudit noeud de profondeur t+1 fait partie des Y plus grandes probabilités calculées par le processeur pour l'observation de toutes les sous-séquences de taille t. En pratique, dans le cas général du modèle de Markov caché décrit précédemment émettant p états observés à chaque temps t , le processeur réalise par exemple les tâches décrites ci-après. Ici, l'ensemble des états observés possible de la variable ne varie pas avec le temps t du modèle. On définit ici des ensembles Er regroupant les noeuds de profondeur t dans l'arbre. Le processeur enregistre tout d'abord un noeud racine R vide (voir figure 5). Initialisation: construction et calcul des probabilités intermédiaires des 20 états observés enregistrés dans les premiers noeuds de l'arbre. Au temps t = 1, le processeur détermine les M!(M- P)!P! combinaisons non ordonnées possibles de p états observés parmi les M états observés de l'ensemble des états observés du modèle au temps 1 et construit un ensemble E, de M!.(M - P) !P! premiers noeuds nk, de profondeur 1 avec k 25 compris entre 1 et M!(M' P) !P! correspondants à ces M!J(M - p) ! p! combinaisons. Tous les premiers noeuds ni' ont comme noeud parent le noeud racine de l'arbre. Le processeur enregistre dans chacun de ces premiers noeuds l'une des M!/(M- p) ! p! combinaisons déterminées et l'identifiant du noeud racine R. 30 II calcule les p*N probabilités intermédiaires associées à chaque état observé de la combinaison d'états observés considérée, qui sont calculées par : ani(l) ,b,(e,, u) Induction : construction des noeuds internes de l'arbre et calcul de la probabilité d'observer la sous séquence de taille t associée à chacun de ces 35 noeuds. Pour chaque temps t = 2 à t = T-1 : Pour k = 1 à k = I E,-1I , IE,- !l représentant le nombre de noeuds dans l'ensemble E,_, au temps t : - le processeur détermine les M!!(M - P) ! arrangements ordonnés possibles de p états observés parmi les M états observés de l'ensemble des états observés du modèle au temps t et construit, pour chaque noeud nk,_, de Et_,, les MV(M - P) ! noeuds enfants possibles n't correspondants aux M!V(M - Io)! arrangements déterminés ; - le processeur inclut ces noeuds nkt dans l'ensemble Et, -le processeur calcule, pour chaque noeud nkt, les p*N probabilités intermédiaires d'observer chaque sous-séquence d'états observés uniques de taille t et de rang u associée à chaque état observé unique de l'arrangement de p états observés enregistré dans ce noeud, par la formule : au,,,,( i) a;, b, (ou,,u) où i est compris entre 1 et Net u est compris entre 1 et p. - le processeur calcule, pour chaque noeuds nkt, la probabilité d'observer 15 la sous-séquence de taille t correspondant au noeud nkt par la formule suivante : u =p N =ri an, k,u(i). u= i= Première méthode de sélection des noeuds: sélection, selon leur probabilités normalisées, des sous-séquences de l'arbre les plus probables. 20 - le processeur calcule, pour chaque noeuds nkt, la probabilité normalisée d'observer la sous-séquence de taille t correspondant à chaque noeud nkt par la formule suivante : u =p N jl~a k (1) Pr( = n , ,u n; lx) u= i= IE, u=p N fEa (1) n, , ,u - le processeur élimine le noeud n; de l'ensemble Et si Pr(ni 1 x) On appelle haplotypes ces arrangements d'allèles de chaque chromosome. Les haplotypes font l'objet de nombreuses études car il peuvent correspondre à des facteurs de risque ou de susceptibilité aux maladies plus complexes que les polymorphismes simples. Actuellement, on détermine les haplotypes d'une population d'individus à partir des génotypes via des logiciels d'inférence statistiques connus. Les logiciels les plus performants sont basés sur des modèles de Markov cachés qui permettent de modéliser les processus de diversification génétique à l'origine des haplotypes, que sont les mutations et les recombinaisons (c'est-à-dire les échanges de portions de chromosomes lors de la gamétogenèse, c'est-à-dire la formation des cellules reproductrices). Dans ce modèle, les haplotypes d'individus donnés d'une population peuvent être déduits de quelques haplotypes appelés haplotypes ancestraux qui sont modifiés au cours des générations par des mutations ponctuelles, par exemple, le remplacement d'un allèle par un autre au niveau d'un SNP, et des recombinaisons. Les chromosomes observés à l'heure actuelle sont dans cette hypothèse formés d'une mosaïque de ces haplotypes ancestraux. Cette hypothèse est décrite en détail dans le document de SB Gabriel et al intitulé The structure of haplotype blocks in the human genome, publié dans la revue Science (New York, NY 2002, 296(5576):2225-2229). L'homme possédant pour chaque SNP deux allèles, l'un situé sur le chromosome paternel et l'autre sur le chromosome maternel de la paire de chromosome correspondante, on détermine chez l'homme des paires d'haplotypes. Ainsi, grâce à la méthode selon l'invention, il est possible de déterminer les paires d'haplotypes les plus probables pour un individu de génotype donné par un calcul par ordinateur de la probabilité d'une séquence d'arrangements de deux états observés correspondant aux paires d'allèles de chaque SNP du génotype étudié. Ci-dessous un exemple simplifié de la détermination de la paire d'haplotype d'une paire de chromosomes comportant cinq SNP par un mode de réalisation de la méthode selon l'invention est détaillé. Les étapes de cette détermination sont représentées sur la figure 6. L'incrémentation du temps t dans le modèle de Markov caché considéré ici correspond au passage d'un SNP du chromosome au SNP suivant dans la chaîne nucléotidique. Les notations des paramètres (A, B, 3t) du modèle de Markov caché décrit plus haut ainsi que la notation X de ce modèle ont été conservées dans le modèle de Markov caché considéré dans cet exemple, bien qu'elles désignent évidemment des valeurs différentes. Les états cachés du modèle de Markov caché considéré sont par 5 exemple au nombre de trois. Ce sont ici trois chromosomes ancestraux composés de 5 allèles correspondant aux cinq SNP considérés : S,=ATTTC S2= TA T TA S3=ATCG C. 10 L'ensemble des états cachés du modèle varie donc ici avec le temps t de ce modèle. Les chances de recombinaisons entre ces chromosomes ancestraux sont modélisées par les probabilités de transitions entre deux états cachés du modèle de Markov caché. 15 Pour simplifier l'exemple décrit ici, on suppose que les probabilités de transition entre deux états cachés ne sont pas fonction du temps t, c'est-à-dire qu'elles ne varient pas en fonction du SNP considéré. En variante, les probabilités de transitions peuvent varier en fonction du temps t. Les étapes de la méthode selon l'invention ne sont pas modifiées dans ce cas. 20 Le processeur de l'ordinateur a en mémoire par exemple la matrice de transitions A et la distribution initiale ' suivantes : /0,98 0,01 0,01\ A= 0,03 0,95 0,02 \0,05 0,05 0,90/ 25 /0,34\ : = 0,33 \0,33, Ces matrices peuvent être par exemple mises en mémoire manuellement par l'utilisateur. 30 Dans cet exemple, deux allèles existent pour chaque SNP considéré, il y a donc deux états observés V,, V2 possibles pour chaque SNP. Ici, l'ensemble des états observés possibles dépend du temps t. L'ensemble d'états observés V ={V1, V2} possible à chaque temps t du modèle, c'est-à-dire à chaque rang t de chaque séquence, est représenté dans le tableau de la figure 7. Ce tableau est également 35 mis en mémoire dans l'ordinateur. Les mutations intervenant dans les chromosomes ancestraux sont modélisées via les probabilités d'émissions. Dans le modèle de Markov caché de cet exemple, chaque chromosome ancestral peut émettre, pour un SNP donné, soit l'état observé correspondant à l'allèle qu'il possède, soit l'état observé correspondant à l'autre allèle en cas de mutation. Pour chaque SNP, la probabilité d'émission par chaque chromosome ancestral Si de l'allèle qu'il possède est notée b;. La probabilité d'émission par chaque chromosome ancestral Si de l'autre allèle est alors égale à 1-b,. Ici l'ordinateur a en mémoire la matrice d'émission B suivante : /0,99 0,01\ B = 0,99 0,01 \0,99 0,01 Pour déterminer efficacement la ou les paires d'haplotypes les plus probables pour un génotype donné, le processeur est programmé ici pour éliminer les noeuds de profondeur t de l'arbre de séquences d'états observés possible correspondant à une sous-séquence de taille t dont la probabilité normalisée est inférieure à un seuil f prédéterminé. Pour la détermination des paires d'haplotypes, le seuil f est de préférence compris entre 0,001 et 0,01. Il est par exemple ici égal à 0,01. Le processeur a enfin en mémoire le génotype g dont l'utilisateur veut déterminer les paires d'haplotypes les plus probables. g = (A/T, A/T, T/T, G/T,, A/C). Ce génotype g est composé de quatre SNP hétérozygotes SPI, SP2, SNP4 et SNP5 qui correspondent aux SNP de rang 1, 2, 4 et 5 du génotype et d'un SNP homozygote noté SNP3 qui correspond au SNP de rang 3 du génotype. Il a donc 8 paires d'haplotypes compatibles pour 16 haplotypes distincts compatibles. Dans ce mode de réalisation, le processeur construit les noeuds de profondeur t dans l'arbre informatique à chaque temps t du modèle correspondant. Cet arbre est représenté sur la figure 6. Selon l'invention, le processeur est programmé pour effectuer les étapes suivantes. Le processeur enregistre préalablement un noeud racine vide. Etape t = 1: le processeur enregistre dans un premier noeud de profondeur 1, l'arrangement possible des deux allèles observés pour le SNP de rang 1 SNP1. Cette étape est représentée sur la première ligne de l'arbre de la figure 6. Ici, l'ensemble des états observés du modèle au temps t =1 comprend les deux allèles A et T, comme représenté dans le tableau de la figure 7. Le processeur enregistre également un identifiant de ce noeud racine et calcule la probabilité d'observer cette paire d'allèle. L'expression � paire d'allèle � est par la suite utilisée pour désigner un arrangement de deux allèles. Pour cela, il calcule la probabilité d'observer l'allèle A en calculant la probabilité intermédiaire notée aA(1) d'observer l'allèle A lorsque le modèle est dans l'état caché S, au temps 1, la probabilité intermédiaire notée aA(2) d'observer l'allèle A lorsque le modèle est dans l'état caché S2 au temps 1 et la probabilité intermédiaire notée aA(3) d'observer l'allèle A lorsque le modèle est dans l'état caché S3 au temps 1. Ensuite, le processeur calcule la probabilité d'observer l'allèle A au temps 1 en sommant ces trois probabilités intermédiaires. Ces sous-étapes correspondent aux calculs suivants: a.~(1)=irib, =0, 0,3366 a, (2)=(1-b,)=0,0033 a, (3) = = 0.3267 Pr(AIÀ)=a_,(1)+a,(2)+a,(3)=0.6666 La probabilité d'observer l'allèle A au temps t =1, c'est-à-dire pour le SNP noté SNP1 est donc ici égale à 0,6666. Le processeur calcule la probabilité d'observer l'allèle T en calculant la probabilité intermédiaire notée aT(1) d'observer l'allèle T lorsque le modèle est dans l'état caché S1 au temps 1, la probabilité intermédiaire notée aT(2) d'observer l'allèle T lorsque le modèle est dans l'état caché S2 au temps 1 et la probabilité intermédiaire notée aT(3) d'observer l'allèle T lorsque le modèle est dans l'état caché S3 au temps 1. Ensuite, le processeur calcule la probabilité d'observer l'allèle T au temps 1 en sommant ces trois probabilités intermédiaires. Ces sous-étapes correspondent aux calculs suivants : ar(1)=It,(1-b,)=0,0034 (Xr(2)=7r,b,=0,3267 a, (3)=rr_(1-1),)=0,0033 Pr(T2)=a,.(1)+a,.(2)+a, (3)=0,3334 La probabilité d'observer l'allèle T au temps t =1, c'est-à-dire pour le SNP noté SNP1 est donc de 0,3334. Enfin, le processeur calcule la probabilité d'observer la paire AT au temps t = 1, c'est-à-dire la probabilité pour que chacun des deux chromosomes de la paire comporte l'un des deux allèles A et T. Cette probabilité est égale au produit des probabilités d'observer l'allèle A et l'allèle T au temps 1 calculées précédemment. Comme il n'y a qu'un seul noeud de profondeur 1, la probabilité normalisée Pn(ATIÀ) d'observer la paire AT au temps 1 est donc ici égale à 1. C'est cette probabilité normalisée Pn qui est représentée sur la figure 6 à côté de chaque noeud de l'arbre. Etape t = 2 : le processeur enregistre, dans deux noeuds de profondeur 2, les paires d'allèles observées possibles de l'ensemble des états observés possibles pour le SNP de rang 2 SNP2 ainsi qu'un identifiant du noeud de profondeur 1. Cette étape est représentée sur la deuxième ligne de l'arbre de la figure 6. Ici, il y a deux paires d'allèles possibles: AT et TA, car l'ensemble des états observés du modèle au temps t =2 comprend les deux allèles A et T, comme représenté dans le tableau de la figure 7. Le processeur calcule alors la probabilité d'observer la sous-séquence de taille 2 de paire d'allèles correspondant à chaque noeud de profondeur 2 dans l'arbre. Ici, il y a deux sous-séquences de taille 2 de paires d'allèles : (AT ; AT) et (AT ; TA). Pour cela, le processeur calcule la probabilité intermédiaire d'observer chaque sous-séquence d'allèles uniques de taille 2 correspondantes à chacune des deux sous-séquence de taille 2 de paire d'allèles. La sous-séquence de paires d'allèles (AT;AT) se décompose en deux sous-séquences d'allèles uniques (A;A) et (T;T) et la sous-séquence de paires d'allèles (AT;TA) se décompose en deux sous-séquences d'allèles uniques (A;T) et (T;A). Pour cela, il effectue les calculs suivants. Le processeur calcule la probabilité d'observer la sous-séquence d'allèles uniques (A;A) notée Pr(AAIÀ) sur l'un des chromosomes de la paire concernée, en calculant les probabilités intermédiaires notées aA,(1), aAA(2) et aA,(3) d'observer cette sous-séquence (A;A) lorsque le modèle est dans chacun de ses états observés, puis en sommant ces trois probabilités intermédiaires : (1) =[a_, (1)aä +a, (2)a,, +cX_, (3)a,,](1-b, )=0,00346302 a, (2) = [a, (1) (1,_ +a, (2)a,, +a, (3) a,_]h, =0,0226076 a,.,(3)=[a,(1)aä+a,(2)a_,+a,(3)a,,](1-b,)=0,00297462 Pr(AAIÂ)=a{, (1)1 (2) i (3)=0,0290453 De la même façon, avec des notations équivalentes, le processeur calcule la probabilité d'observer la sous-séquence d'allèles uniques (T;T) sur l'un des chromosomes de la paire concernée : arr(I)=[ar(1)aä+ar(2)a,,+a,. (3)a3,1h,=0,013165 ar, (2)=[ar(1)a,,+a, (2)(12, +a,(3)a,y1(1-h,)=0,00310564 arr(3)=[ar(1)a,,+ar(2)c123+a,(3)a d h, = 0,00944262 Pr (TTIÀ) = arr (1) +arr (2) +arr (3)=0,0257133 De la même façon, avec des notations équivalentes, le processeur calcule la probabilité d'observer la sous-séquence d'allèles uniques (A;T) sur l'un des chromosomes de la paire concernée : aa.(1)=[a.,(1)au+ a,(2)a. +a,(3)a_,]b,=0,342839 a r(2)=[a,(1)a,+a,(2)aä+a,(3)a,,](1-b,)=0,00022836 a,r(3)=[a,(1)(h;+(2)u,;+a,(3)aä]h,=0,294487 Pr (AT;Â) = a,r (1) i a,r (2) 1 a,r (3) --0,637555 Le processeur calcule la probabilité d'observer la sous-séquence d'allèles uniques (T;A) sur l'un des chromosomes de la paire concernée selon les formules suivantes : a,r (1) =[a, (1)aä +a, (2)(12l +a, = 0,342839 a.,r (2) =[a., (I )a,, +a,, (2)a,, +a, (3)a,_](I -h,) = 0,00022836 10 a.,,-(3)=[a.,(1)a,, +a.,(2)a,,+a,(3)aä]b, =0,294487 Pr(A'112L)=a,r(1) 1 a,r(2) ia,r(3)=0,637555 La probabilité d'observer les allèles successives AA et TT sur chacun des deux chromosomes, c'est-à-dire la probabilité Pr(AA,TTIÀ) d'observer la paire d'haplotype (AA;TT) est égale à la probabilité d'observer la sous-séquence de 15 paires d'allèles (AT;AT), qui est égale au produit des probabilités Pr(AAIÀ) et Pr(TTI À) d'observer chaque sous-séquence d'allèles (A;A) et (T;T). La probabilité Pr(AT,TAI À) d'observer les allèles successives AT et TA sur chacun des deux chromosomes, c'est-à-dire la probabilité d'observer la paire d'haplotype (AT;TA) est égale à la probabilité d'observer la sous-séquence de paires d'allèles (AT;TA), 20 qui est égale au produit des probabilités Pr(AT1À) et Pr(TAIÀ) d'observer chaque sous-séquence d'allèles (A;T) et (T;A). Le processeur calcule ensuite la probabilité normalisée d'observer les paires d'haplotypes AA,TT et AT,TA sur la paire de chromosome étudiée. Pour cela, il effectue les calculs suivants : 25 Pn Pr ( AA I À)xPr(TT 1 À) ( AA,TT j À) = 0,003792 Pr (AA, TT I À) + Pr (AT, 7A ~ À) = Pi,(AT,1:4~À)= Pr(ATI~ï)xPr(7A~2) =0,9962(18• Pr(AA,TT I t)+Pr(AT,TA~ 2) Le processeur compare ensuite ces probabilités normalisées au seuil 30 prédéterminé f. Ici Pr(AA,TT IX) Selon l'invention, le processeur détermine par cette méthode d'exploration les paires d'haplotypes les plus probables pour le génotype étudié dans le modèle de Markov caché considéré en effectuant un nombre réduit d'opérations. Par les méthodes connues de l'état de la technique, le processeur aurait été programmé pour calculer la probabilité de chaque haplotype via l'algorithme de propagation alpha bêta, pour ensuite déterminer la paire la plus probable. Pour s SNP hétérozygotes, il y a 2`-' paires d'haplotypes possibles, donc 2S haplotypes dont la probabilité est déterminée par la méthode de l'état de la technique. Ce nombre est considérablement réduit par la méthode selon l'invention. Cette fonction d'exploration peut être utilisée pour améliorer le logiciel PHASE v2.1 décrit par exemple dans le document intitulé � Accounting for decay of linkage disequilibrium in haplotype inference and missing-data imputation � publié par M. Stephens et P. Scheet dans l'American journal of human genetics (volume 76(3), pages 449-462) en 2005, et breveté dans le brevet WO02064617. Ce logiciel Phase v2.1 est basé sur un modèle de Markov caché et constitue un logiciel très performant pour la détermination des haplotypes. Selon l'invention, la méthode de calcul de la présente invention et la fonction d'exploration décrites ci-dessus sont intégrées à ce logiciel PHASE v2.1 pour obtenir un nouveau logiciel amélioré afin d'accélérer les calculs du processeur commandés par ce logiciel. Les performances des logiciels Phase v2.1 de l'état de la technique et de ce nouveau logiciel selon l'invention ont été comparées sur un nombre important de données réelles de génotypes extraites de la base de données publique HapMap (http://www.hapmap.org/) dont les haplotypes correspondant sont partiellement connus. Les haplotypes les plus probables pour différents génotypes ont été calculés par les deux logiciels et comparés aux haplotypes partiellement connus. Ces différents génotypes comportaient chacun un nombre de SNP et des natures de SNP différents. Un taux d'erreur exprimé en pourcentage correspondant à la proportion de nucléotides erronés dans les haplotypes calculés par rapport aux haplotypes connus à été déterminé. En parallèle, les temps de calcul nécessaire au même processeur pour calculer ces haplotypes selon les instructions des deux logiciels ont été aussi relevés. Les résultats sont exposés dans le tableau de la figure 8 où les temps de calcul sont exprimés en secondes. Le différents génotypes étudiés sont repérés dans ce tableau par un numéro placé dans la première colonne. On constate que dans le nouveau logiciel selon l'invention, la méthode conforme à la présente invention accélère le temps de calcul du processeur d'environ 80 fois et fournit les haplotypes les plus probables avec un taux d'erreur équivalent à celui des haplotypes obtenus par le logiciel PHASE v2.1 de l'état de la technique. D'autres applications de cette méthode peuvent être envisagées, dans différents domaines où les probabilités de séquences d'états observés dans un modèle de Markov caché sont calculées par un ordinateur. Ces domaines sont par exemple ceux de la finance, de la météorologie et de la reconnaissance vocale. La présente invention n'est nullement limitée aux modes de réalisation décrits et représentés mais l'homme du métier saura y apporter toute variante conforme à son esprit. La méthode peut être appliquée par exemple au calcul par ordinateur des arrangements de trois ou plus haplotypes d'individus appartenant à des espèces polyploïdes à trois chromosomes ou plus. La méthode accélère alors le calcul des séquences d'arrangements de trois allèles ou plus. REVENDICATIONS1. Dispositif électronique de calcul de la probabilité d'observer chaque séquence (Ox) d'un ensemble d'un nombre prédéterminé de séquences (Ox) comportait chacune un nombre donné T d'arrangements d'un nombre p d'états observés d'une variable modélisée par un modèle de Markov caché, chaque arrangement de p états observés de rang t de chaque séquence ayant été émis par ce modèle, au temps t de ce modèle correspondant audit rang t de chaque séquence, ledit modèle de Markov caché comportant un ensemble prédéfini d'états cachés, ledit dispositif comportant au moins un processeur et une mémoire, et étant programmé pour effectuer les tâches suivantes : a) classer lesdites séquences d'arrangements de p états observés selon un arbre informatique stocké dans ladite mémoire, cette tâche comportant les sous-étag es suivantes : a1) enregistrer, dans les premiers noeuds de profondeur 1 dans l'arbre, chaque arrangement de p états observés de rang 1 desdites séquences (Ox), a2) enregistrer, dans chaque noeud de profondeur t comprise entre 2 et T, l'arrangement de p états observés de ladite variable situé au rang t correspondant de chaque séquence (Ox) d'au moins une partie de l'ensemble desdites :;équences (Ox) et un identifiant du noeud parent de profondeur t-1 de ce noeud de profondeur t, .:outes les séquences dont les arrangements de p états observés sont identiques jusqu'au rang t, étant regroupées sur une même branche de l'arbre qui s'étend de l'un desdits premiers noeuds à l'un desdits noeuds de profondeur t, D) calculer, pour chaque premier noeud de l'arbre et pour chaque état caché dudit modèle de Markov caché, une probabilité intermédiaire d'observer chaque état observé de l'arrangement de p états observés de ladite variable enregistrée dans ce premier noeud, lorsque ledit modèle est dans ledit état caché au temps 1 de ce modèle, :D) calculer, pour chaque noeud de profondeur t comprise entre 2 et T-1, pour chaque état observé de rang u compris entre 1 et p dans l'arrangement de p états observés enregistré dans le noeud de profondeur t correspondant, et pour chaque état caché dudit modèle de Markov caché, une probabilité intermédiaire d'observer la sous-séquence d'états observés uniques comportant à chaque rang compris entre 1 et t, l'état observé de rang u dans l'arrangement de p états observés situé au rang correspondant de la séquence (Ox) considérée, cette sous-séquence étant appelée sous-séquence d'états observés uniques de taille t et de rang u de la séquence (OX) considérée, lorsque ledit modèle est dans ledit état caché au temps t de ce modèle et d) calculer, pour chaque noeud terminal de l'arbre, la probabilité d'observer la séquence (OX) d'arrangements de p états observés de ladite variable décrite par la branche de l'arbre menant du premier noeud correspondant audit noeud terminal de l'arbre. 2. Dispositif selon la revendication précédente, programmé pour effectuer les tâches b), c) et d) dans cet ordre, et pour calculer, lors de la tâche c), - d'abord, pour tous les noeuds de même profondeur t et pour tous les états cachés du modèle au temps t, lesdites probabilités intermédiaires d'observer lesdites sous-séquences d'états observés uniques de taille t et de rang u, pour tous les rangs u compris entre 1 et p, lorsque ledit modèle est dans chaque état caché au temps t, - puis, les probabilités intermédiaires d'observer les sous-séquences d'états observés uniques de taille t+1 et de rang u, pour tous les rangs u compris entre 1 et p, lorsque le modèle est dans chaque état caché au temps t+1. 3. Dispositif selon l'une des revendications précédentes, dans lequel, lors de la tâche c), le processeur calcule, pour chaque noeud de profondeur t comprise entre 2 et T-1, la probabilité d'observer la sous-séquence d'états observés uniques de taille t et de rang u, qui est égale à la somme, des probabilités intermédiaires d'observe- les sous-séquences d'états observés uniques de taille t et de rang u correspondant à ce noeud lorsque le modèle est dans chaque état caché au temps t, pour tous les états cachés du modèle au temps t. 4. Dispositif selon la revendication précédente, dans lequel, lors de la tâche c), le processeur calcule, pour chaque noeud de profondeur t comprise entre 2 et T-1, la probabilité d'observer la sous-séquence d'arrangements de p états observés décrite par la branche de l'arbre menant du premier noeud correspondant audit noeud de profondeur t, appelée sous-séquence de taille t, qui est égale au produit, pour tous les rangs u compris entre 1 et p, desdites probabilités d'observer les sous-séquences d'états observés uniques de taille t et de rang u correspondant à ce noeud de profondeur t. 5. Dispositif selon la revendication précédente, dans lequel, lors de la tâche c), le processeur calcule les probabilités intermédiaires d'observer les sous- séquence:3 d'états observés uniques de taille t+1 et de rang u correspondant à chaque noeud de profondeur t+1 si et seulement si la probabilité d'observer la sous-séquence de taille t correspondant au noeud de profondeur t parent duditnoeud de profondeur t+1 fait partie des Y plus grandes probabilités calculées par le processeur pour l'observation de toutes les sous-séquences de taille t. 6. Dispositif selon la revendication 4, dans lequel, lors de la tâche c), - le processeur calcule, pour chaque noeud de profondeur t, une probabilité normalisée d'observer la sous-séquence de taille t correspondante, cette probabilité normalisée étant égale à ladite probabilité d'observer la sous-séquence de taille t correspondante divisée par la somme des probabilités d'observe- toutes les sous-séquences de taille t, et - le processeur calcule les probabilités intermédiaires d'observer les sous-séquences d'états observés uniques de taille t+1 et de rang u correspondant à chaque noeud de profondeur t+1 si et seulement si la probabilité normalisée d'observe- la sous-séquence de taille t correspondant au noeud de profondeur t parent dudit noeud de profondeur t+1 est supérieure à un seuil prédéterminé. 7. Dispositif selon la revendication 1, pour calculer la probabilité d'observer toutes les séquences pouvant être émises par ledit modèle de Markov et comportant un nombre T d'arrangements de p états observés, programmé pour effectuer la tâche préliminaire suivante : déterminer toutes les séquences pouvant être émises par le modèle de Markov considéré et comportant un nombre T d'arrangements de p états observés, chaque état observé de l'arrangement de p états observés du rang t de chaque séquence appartenant à un ensemble d'états observés de ladite variable prédéterminé en fonction dudit temps t dudit modèle correspondant au rang t de cette séquence. EL Dispositif électronique de calcul de la probabilité d'observer toutes les séquence.; pouvant être émises par un modèle de Markov et comportant un nombre T d'arrangements de p états observés, chaque état observé de l'arrangement de p états observés du rang t de chaque séquence appartenant à un ensemble d'états observés de ladite variable prédéterminé en fonction du temps t dudit modèle correspondant au rang t de cette séquence et ledit modèle de Markov caché comportant un ensemble prédéfini d'états cachés, ledit dispositif comportant au moins un processeur et une mémoire, et étant programmé pour construire dans ladite mémoire un arbre informatique et effectuer les tâches suivantes : E+) déterminer toutes les combinaisons possibles de p états observés de l'ensemble prédéterminé d'états observés au temps 1 du modèle, fi enregistrer dans chaque premier noeud de profondeur 1 dudit arbre informatique, l'une des combinaisons de p états observés déterminée à la tâchee), lj) calculer, pour chaque premier noeud, la probabilité d'observer la combinai;;on de p états observés de ladite variable enregistrée dans ce premier noeud, 1) à chaque profondeur t successive dans l'arbre, avec t compris entre 2 et T-1, hl) déterminer tous les arrangements possibles de p états observés de l'ensembla prédéterminé d'états observés au temps t du modèle, h2) enregistrer, dans chaque noeud de profondeur t, chaque arrangement possible de p états observés déterminé à la tâche h1) et un identifiant du noeud parent de profondeur t-1 de ce noeud de profondeur t, et h3) calculer la probabilité d'observer la sous-séquence d'arrangements de p états observés décrite par la branche de l'arbre menant c u premier noeud correspondant audit noeud de profondeur t, appelée sous-séquence de taille t, ) pour chaque noeud terminal de l'arbre, il) déterminer tous les arrangements possibles de p états observés de l'ensemble prédéterminé d'états observés au temps correspondant du modèle, i2) enregistrer dans chaque noeud terminal cle l'arbre, chaque arrangement possible de p états observés déterminé à la tâche il) et un identifiant du noeud parent de ce noeud terminal, et i3) calculer la probabilité d'observer la séquence d'arrangements de p états observés de ladite variable décrite par la branche de l'arbre menant du premier noeud correspondant audit noeud terminal de l'arbre. 9. Dispositif selon la revendication 8, pour déterminer les séquences les plus probables pouvant être émises par ledit modèle de Markov et comportant un nombre T d'arrangements de p états observés, dans lequel, lors des tâches g) et h3), le processeur calcule également, pour chaque noeud de profondeur t comprise entre 1 et T-1, une probabilité normalisée d'observer la sous-séquence de taille correspondant à ce noeud, égale à ladite probabilité d'observer ladite sous-séquence de taille t divisée par la somme des probabilités d'observer toutes les sous-séquences de taille t, et dans lequel le processeur effectue la tâche h) pour chaque noeud de profondeur t+1 si et seulement si la probabilité normalisée d'observer la sous-séquence de taille t correspondant au noeud de profondeur t parent dudit noeud de profondeur t+1 est supérieure à un seuil prédéterminé. 10. Dispositif selon la revendication 8, dans lequel le processeur effectue la tâche II) pour chaque noeud de profondeur t+1 si et seulement si la probabilité d'observer la sous-séquence de taille t correspondant au noeud de profondeur t parent dudit noeud de profondeur t+1 fait partie des Y plus grandes probabilités40calculées par le processeur pour l'observation de toutes les sous-séquences de taille t. 11. Dispositif selon l'une des revendications 8 à 10, pour déterminer les arrangements de p haplotypes les plus probables d'un individu de génotype connu comportait un nombre T de polymorphismes appelés SNP, ces haplotypes étant modélisé:; par un modèle de Markov caché, dans lequel - ladite variable correspond à l'allèle des SNP successifs de ce génotype, - l'ensemble des états observés possibles de cet allèle pour chaque SNP correspond aux allèles d'un ensemble de chromosomes ancestraux connus, - l'ensemble des états cachés du modèle correspond auxdits chromosomes ancestraux connus, - chaque séquence d'un nombre donné T d'arrangements de p états observés de l'allèle correspondant aux SNP successifs du génotype de l'individu est un arrangement de p haplotypes de l'individu, l'arrangement de p états observés Je l'allèle de rang t de chaque séquence correspondant au SNP de rang t dudit génotype.