Plan M2 - STL. Algorithmes sur les séquences en bioinformatique. Cours 4: Algorithmes exactes de recherche de motifs, CONSENSUS et PatternBranching

of 30
9 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
M2 - STL Algorithmes sur les séquences en bioinformatique Cours 4: Algorithmes exactes de recherche de motifs, CONSENSUS et PatternBranching Alessandra Carbone Université Pierre et Marie Curie Plan Motifs
Document Share
Document Transcript
M2 - STL Algorithmes sur les séquences en bioinformatique Cours 4: Algorithmes exactes de recherche de motifs, CONSENSUS et PatternBranching Alessandra Carbone Université Pierre et Marie Curie Plan Motifs dans un texte aléatoire Régulation des gènes Motifs régulateurs le problème du Gold Bug Le problème Motif Finding Brute Force Motif Finding Le problème Median String Search Arbres de recherche Branch-and-Bound Motif Search Branch-and-Bound Median String Search Consensus et Pattern Branching: algorithme gourmand PMS: Exhaustive Motif Search A.Carbone - UPMC 2 Séquences aléatoires Insertion de motifs : AAAAAAAGGGGGGG atgaccgggatactgataccgtatttggcctaggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatactgggcataaggtaca tgagtatccctgggatgacttttgggaacactatagtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgaccttgtaagtgttttccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatggcccacttagtccacttatag gtcaatcatgttcttgtgaatggatttttaactgagggcatagaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtactgatggaaactttcaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttggtttcgaaaatgctctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatttcaacgtatgccgaaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttctgggtactgatagca atgaccgggatactgataaaaaaaagggggggggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaataaaaaaaaaggggggga tgagtatccctgggatgacttaaaaaaaagggggggtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgaaaaaaaagggggggtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaataaaaaaaagggggggcttatag gtcaatcatgttcttgtgaatggatttaaaaaaaaggggggggaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtaaaaaaaagggggggcaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttaaaaaaaagggggggctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcataaaaaaaagggggggaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttaaaaaaaaggggggga A.Carbone - UPMC 3 A.Carbone - UPMC 4 Ou sont les motifs insérés? Insertion de motifs AAAAAAGGGGGGG avec 4 substitutions atgaccgggatactgataaaaaaaagggggggggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaataaaaaaaaaggggggga tgagtatccctgggatgacttaaaaaaaagggggggtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgaaaaaaaagggggggtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaataaaaaaaagggggggcttatag gtcaatcatgttcttgtgaatggatttaaaaaaaaggggggggaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtaaaaaaaagggggggcaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttaaaaaaaagggggggctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcataaaaaaaagggggggaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttaaaaaaaaggggggga atgaccgggatactgatagaagaaaggttgggggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatacaataaaacggcggga tgagtatccctgggatgacttaaaataatggagtggtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgcaaaaaaagggattgtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatataataaaggaagggcttatag gtcaatcatgttcttgtgaatggatttaacaataagggctgggaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtataaacaaggagggccaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttaaaaaatagggagccctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatactaaaaaggagcggaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttactaaaaaggagcgga A.Carbone - UPMC 5 A.Carbone - UPMC 6 Où sont les motifs? Pourquoi chercher les motifs (15,4) est compliquée? atgaccgggatactgatagaagaaaggttgggggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatacaataaaacggcggga tgagtatccctgggatgacttaaaataatggagtggtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgcaaaaaaagggattgtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatataataaaggaagggcttatag gtcaatcatgttcttgtgaatggatttaacaataagggctgggaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtataaacaaggagggccaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttaaaaaatagggagccctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatactaaaaaggagcggaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttactaaaaaggagcgga atgaccgggatactgatagaagaaaggttgggggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatacaataaaacggcggga tgagtatccctgggatgacttaaaataatggagtggtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgcaaaaaaagggattgtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatataataaaggaagggcttatag gtcaatcatgttcttgtgaatggatttaacaataagggctgggaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtataaacaaggagggccaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttaaaaaatagggagccctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatactaaaaaggagcggaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttactaaaaaggagcgga A.Carbone - UPMC 7 AgAAgAAAGGttGGG caataaaacggcggg A.Carbone - UPMC 8 Problème Combinatoire de la régulation des gènes Trouver un motif dans un texte aléatoire - 20 séquences aléatoires (e.g. 600 nt de longueur) - chaque séquence contient un motif inséré de longueur 15, - chaque motif apparaît avec 4 mismatches, et on l appelle motif (15,4). Les expériences utilisant les micropuces d ADN ont montré que quand un gène X est supprimé ( knocked out ), 20 autres gènes ne sont pas exprimés Comment c est possible qu un seul gène puisse avoir un effet tellement drastique? A.Carbone - UPMC 9 A.Carbone - UPMC 10 Nouvelles technologies : les puces à ADN Exemple: analyse du cycle cellulaire de la levure A.Carbone - UPMC 11 A.Carbone - UPMC 12 Protéines régulatrices Identification de motifs Gène X code pour une protéine régulatrice, appelée facteur de transcription (TF) Les 20 gènes non exprimés demandent la présence du TF codé par le gène X pour avoir une induction de leur transcription. Trouver des motifs dans plusieurs régions régulatrices suggère une relation de régulation entre ces gènes. Un seul TF peut réguler plusieurs gènes. A.Carbone - UPMC 13 A.Carbone - UPMC 14 Un exemple de circuit de régulation : les gènes de développement de l oursin Régions régulatrices Chaque gène contient une région régulatrice (RR) typiquement située bp en amont du site de départ de la transcription. Localisés dans la RR il y a les sites de liaison des facteurs de transcription (TFBS), nommé motifs, spécifiques d un facteur de transcription donné. Les TFs influencent l expression du gène en se liant a une location spécifique dans la région régulatrice respective. A.Carbone - UPMC 15 A.Carbone - UPMC 16 Exemple : développement de l oursin de mer Sites de liaison des facteurs de transcription Un TFBS peut être localisé n importe où dans la région régulatrice (RR) Un TFBS peut varier dépendamment des régions régulatrices parce que des bases non-essentielles peuvent avoir mutées. Région promotrice du gène endo16 A.Carbone - UPMC 17 A.Carbone - UPMC 18 Motifs et site de départ de la transcrition Facteurs de transcription et motifs ATCCCG TTCCGG ATCCCG gène gène gène ATGCCG gène ATGCCC gène A.Carbone - UPMC 19 A.Carbone - UPMC 20 Logo du motif Logo de motif: un exemple Les motifs peuvent muter sur des positions qui se révèlent n être pas importantes Les 5 motifs dans 5 gènes différents ont muté a la position 3 et 5 La représentation est appelée logo du motif et représente les régions conservées et les régions variables du motif. TGGGGGA TGAGAGA TGGGGGA TGAGAGA TGAGGGA A.Carbone - UPMC 21 A.Carbone - UPMC (http://www-lmmb.ncifcrf.gov/~toms/sequencelogo.html) 22 Identification de motifs: complications Analogie de la recherche de motifs On ne connaît pas la séquence du motif On ne connaît pas où il se trouve le motif par rapport au début du gène Motifs peuvent différer de gène à gène Comment les distinguer des motifs aléatoires? Le problème de la recherche de motifs est similaire au problème posé par Edgar Allan Poe ( ) dans son compte Gold Bug A.Carbone - UPMC 23 A.Carbone - UPMC 24 Le problème du Gold Bug Suggestion pour le problème de Gold Bug Etant donné un message secret : 53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!; 46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-4)8`8*; );)6!8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;(88;4(+?3 4;48)4+;161;:188;+?; On veut déchiffrer le message encrypté dans le fragment Le message encrypté est écrit en anglais Chaque symbole correspond a une lettre de l alphabet anglais La ponctuation n est pas encodé A.Carbone - UPMC 25 A.Carbone - UPMC 26 Le problème du Gold Bug : comptage de symboles Approche naïve a la solution du problème: Compter la fréquence de chaque symbole dans le message encrypté. Trouver la fréquence de chaque lettre dans l alphabet anglais. Comparer les fréquences obtenues, chercher une corrélation et trouver une correspondance entre symboles et lettres de l alphabet. Fréquences des symboles dans le message Gold Bug Message du Gold Bug : Symbole Fréquence 8 ; 4 ) + * 5 6 (! :? ` - ] Langue anglaise: e t a o i n s r h l d c u m f p g w y b v k x j q z plus fréquent moins fréquent A.Carbone - UPMC 27 A.Carbone - UPMC 28 La décodification du message du Gold Bug : premier tentative Le problème du problème du Gold Bug : comptage des l-tuples La correspondance entre le symbole plus fréquent et la lettre plus fréquente de l alphabet: sfiilfcsoorntaeuroaikoaiotecrntaeleyrcooestvenpinelefheeosnlt arhteenmrnwteonihtaesotsnlupnihtamsrnuhsnbaoeyentacrmuesotorl eoaiitdhimtaecedtepeidtaelestaoaeslsueecrnedhimtaetheetahiwfa taeoaitdrdtpdeetiwt Le résultat n a pas de sens Une meilleure approche : Examiner les fréquences des l-tuples, combinaisons de 2 symboles, 3 symboles, etc. The est la 3-tuple plus fréquente en anglais et ;48 est la 3-tuple plus fréquente dans le texte encrypté. Inférer les symboles non connus en examinant l-tuples fréquents A.Carbone - UPMC 29 A.Carbone - UPMC 30 Le problème du Gold Bug : le clue ;48 La correspondance entre the et ;48 etla substitution de toutes les occurrence des symboles: 53++!305))6*the26)h+.)h+)te06*the!e`60))e5t]e*:+*e!e3(ee)5*!t h6(tee*96*?te)*+(the5)t5*!2:*+(th956*2(5*h)e`e*th0692e5)t)6!e )h++t1(+9the0e1te:e+1the!e5th)he5!52ee06*e1(+9thet(eeth(+?3ht he)h+t161t:1eet+?t A.Carbone - UPMC 31 Décodification du message du Gold Bug : deuxième tentative Inférer : 53++!305))6*the26)h+.)h+)te06*the!e`60))e5t]e*:+*e!e3(ee)5*!t h6(tee*96*?te)*+(the5)t5*!2:*+(th956*2(5*h)e`e*th0692e5)t)6!e )h++t1(+9the0e1te:e+1the!e5th)he5!52ee06*e1(+9thet(eeth(+?3ht he)h+t161t:1eet+?t thet(ee devient avec forte probabilité the tree Inférer : ( = r th(+?3h devient thr+?3h Est-ce qu on peux deviner + et?? A.Carbone - UPMC 32 Le problème de Gold Bug : solution La solution (continuation) Après avoir reconstruit toutes les correspondances, le message finale est : AGOODGLASSINTHEBISHOPSHOSTELINTHEDEVILSSEATWENYONEDEGRE ESANDTHIRTEENMINUTESNORTHEASTANDBYNORTHMAINBRANCHSEVENT HLIMBEASTSIDESHOOTFROMTHELEFTEYEOFTHEDEATHSHEADABEELINE FROMTHETREETHROUGHTHESHOTFIFTYFEETOUT La ponctuation est importante: A GOOD GLASS IN THE BISHOP S HOSTEL IN THE DEVIL S SEA, TWENY ONE DEGREES AND THIRTEEN MINUTES NORTHEAST AND BY NORTH, MAIN BRANCH SEVENTH LIMB, EAST SIDE, SHOOT FROM THE LEFT EYE OF THE DEATH S HEAD A BEE LINE FROM THE TREE THROUGH THE SHOT, FIFTY FEET OUT. A.Carbone - UPMC 33 A.Carbone - UPMC 34 Résoudre le problème du Gold Bug Conditions préalables pour trouver la solution : On doit connaître les fréquences relatives des lettres seules, et des combinaisons de 2 ou 3 lettres en anglais. La connaissance de tous les mots du dictionnaire anglais est souhaitée pour une inférence précise. A.Carbone - UPMC 35 Recherche de motifs et le problème du Gold Bug : similarités Les nucléotides dans les motifs codent pour un message dans le langage génétique. Les lettres dans le the gold bug codent pour un message en anglais. Pour résoudre le problème, nous analysons les fréquences des motifs dans le message de l ADN/Gold Bug. La connaissance de motifs régulateurs connus rende le problème plus simple. La connaissance des mots dans le dictionnaire anglais aide à la résolution du problème du Gold Bug. A.Carbone - UPMC 36 La recherche des motifs est un problème plus difficile que le problème du Gold Bug: Le problème de la recherche des motifs Etant donnée des séquences aléatoires d ADN: cctgatagacgctatctggctatccacgtacgtaggtcctctgtgcgaatctatgcgtttccaaccat Nous n avons pas un dictionnaire complet de motifs. Le langage génétique n a pas de grammaire standard. Seulement une petite fraction des séquences nucléotidiques encodent des motifs; la taille des données est énorme. agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc aaacgtacgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtacgtc Trouver le motif qui est présent dans toutes ces séquences. A.Carbone - UPMC 37 A.Carbone - UPMC 38 Le problème de la recherche des motifs Le problème de la recherche des motifs Un motif sans mutations : Information additionnelle: cctgatagacgctatctggctatccacgtacgtaggtcctctgtgcgaatctatgcgtttccaaccat agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc La séquence cachée est de longueur 8 aaacgtacgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca Le motif n est pas le même dans chaque séquence à cause des substitutions A.Carbone - UPMC 39 ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtacgtc acgtacgt Chaîne Consensus A.Carbone - UPMC 40 Le problème de la recherche des motifs Le problème de la recherche des motifs Un motif avec 2 mutations: cctgatagacgctatctggctatccaggtacttaggtcctctgtgcgaatctatgcgtttccaaccat agtactggtgtacatttgatccatacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc aaacgttagtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtccatataca Un motif a 2 mutations: cctgatagacgctatctggctatccaggtacttaggtcctctgtgcgaatctatgcgtttccaaccat agtactggtgtacatttgatccatacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc aaacgttagtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtccatataca ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaccgtacggc ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaccgtacggc Est-ce que l on peut toujours trouver un motif, avec 2 mutation? A.Carbone - UPMC 41 A.Carbone - UPMC 42 Définition des motifs Motifs: Profiles et Consensus Pour définir un motif, supposons de connaître où le motif commence dans la séquence Les positions du départ du motif dans les séquences peuvent être représentées par s = (s 1,s 2,s 3,,s t ) A.Carbone - UPMC 43 Alignement a G g t a c T t C c A t a c g t a c g t T A g t a c g t C c A t C c g t a c g G A Profile C G T Consensus A C G T A C G T Aligner les motifs par leur index de départ s = (s 1, s 2,, s t ) Construire la matrice profile avec les fréquences de chaque nucléotide dans les colonnes Le nucléotide consensus dans chaque position a le score plus élevé dans la colonne A.Carbone - UPMC 44 Consensus Consensus (continuation) Nous pensons au consensus comme a un motif ancêtre, qui est l origine des motifs émergeants. La distance entre un motif réel et une séquence consensus est généralement plus petite que entre 2 motifs réels. A.Carbone - UPMC 45 A.Carbone - UPMC 46 Evaluation des motifs Nous avons une idée de la séquence consensus, mais quel tôt de confiance on peut avoir dans elle? Il faut introduire une fonction de score pour comparer les différentes propositions de séquence consensus et pour choisir la meilleure. Terminologie t - nombre de séquences ADN n - longueur de chaque séquence ADN DNA séquences ADN (tableau t x n) l - longueur du motif (l-mer) s i - position du départ d un l-mer dans la séquence i s=(s 1, s 2, s t ) - tableau des positions de départ du motif A.Carbone - UPMC 47 A.Carbone - UPMC 48 Paramètres Score des motifs l t=5 l = 8 DNA cctgatagacgctatctggctatccaggtacttaggtcctctgtgcgaatctatgcgtttccaaccat agtactggtgtacatttgatccatacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc aaacgttagtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtccatataca ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaccgtacggc Etant donné s = (s 1, s t ) et DNA: Score(s,DNA) = l max i= 1 k { A, T, C, G} count( k, i) a G g t a c T t C c A t a c g t a c g t T A g t a c g t C c A t C c g t a c g G A C G T t n = 69 Consensus a c g t a c g t s s 1 = 26 s 2 = 21 s 3 = 3 s 4 = 56 s 5 = 60 A.Carbone - UPMC 49 Score =30 A.Carbone - UPMC 50 Le problème de la recherche des motifs Le problème de la recherche des motifs: formulation Si les positions de départ sont données s=(s 1, s 2, s t ), trouver un consensus est facile même s il y a des mutations parce qu on peut simplement construire un profile (pour trouver le motif). mais les positions de départ s ne sont pas connues d habitude. Comment peut on trouver alors la matrice de profile la meilleure? But: étant donné un ensemble de séquences d ADN, trouver un ensemble de l-mers, un pour chaque séquence, que maximise le score de consensus. Input: une matrice t x n de sequences d ADN (DNA), et l, la longueur du motif a chercher Output: un tableau de t positions de départ s = (s 1, s 2, s t ) qui maximisent Score(s,DNA) A.Carbone - UPMC 51 A.Carbone - UPMC 52 Le problème de la recherche des motifs: algorithme brute force Calcule les scores pour toutes combinaisons possibles des positions de départ s Le meilleur score déterminera le meilleur profile et le motif consensus dans DNA Le but est de maximiser le Score(s,DNA) en variant les positions de départ s i, ou: s i = [1,, n-l+1] i = [1,, t] BruteForceMotifSearch 1. BruteForceMotifSearch(DNA, t, n, l) 2. bestscore 0 3. for each s=(s 1,s 2,..., s t ) from (1,1... 1) to (n-l+1,..., n-l+1) 4. if (Score(s,DNA) bestscore) 5. bestscore score(s, DNA) 6. bestmotif (s 1,s 2,..., s t ) 7. return bestmotif A.Carbone - UPMC 53 A.Carbone - UPMC 54 Complexité de BruteForceMotifSearch On regarde (n - l + 1) t ensembles de positions de départ Pour chaque ensemble de positions de départ, la fonction de score est calculée avec l opérations, et la complexité devient l (n l + 1) t = O(l n t ) Le problème de la recherche de la chaîne médiane (Median String Search Problem) Etant donné un ensemble de t séquences d ADN trouver un motif qui apparaît dans toutes les t séquences avec un nombre minimale de mutations Cela signifie que pour t = 8, n = 1000, l = 10 on doit réaliser environs opérations en qqs millions d années. A.Carbone - UPMC 55 A.Carbone - UPMC 56 Distance de Hamming Distance totale : un exemple Distance de Hamming: d H (v,w) est le nombre de paires nucléotidiques que ne sont pas appariées dans l alignement de v et w. Par exemple: d H (AAAAAA,ACAAAC) = 2 Etant donné v = acgtacgt et s d H (v, x) = 0 acgtacgt cctgatagacg
Similar documents
View more...
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x