| Introducció | Objectius | Metodologia | Programes | Resultats | Conclusions | Referències | Autores | Agraïments |
CONCLUSIONS
Els resultats de l'anàlisi exhaustiu que aquí es detalla es troba en l'apartat de Resultats. |
||
Anàlisi de la complexitat algorísmica i del cost computacional de l'algorisme simple de correspondència exacta versus l'algorisme de Knuth-Morris-Pratt L'algorisme simple de correspondència exacta presenta una complexitat algorísmica d'ordre quadràtic: O(nm). És un tipus d'algorisme que no requereix un pre-processament del patró. Tal i com ja hem vist tant en l'apartat de Metodologia com de Programes, la idea és simple: el patró i la seqüència són comparades nucleòtid per nucleòtid, i en el cas d'un mismatch, el patró es desplaça una posició a la dreta, i la comparació es repeteix, i així fins que es troba una correspondència exacta o la seqüència s'ha finalitzat.
Així doncs, el cost computacional en el pitjor dels casos és O(nm). Aquest es donaria per una seqüència de n A's seguides per una C buscant un patró de m A's i una C (assumint que m < n):
|
||
|
En aquest cas, fins a m nucleòtids s'haurien de comparar per tots els n - m + 1 desplaçaments donats. Això resumeix la mencionada complexitat computacional d'aproximadament O(nm).
En els nostres resultats, per exemple pel mRNA del gen de la EPO, la longitud de la seqüència (m) és de 579 nucleòtids. El nostre programa genera uns 566 patrons d'aquest mRNA d'una longitud de 14 nucleòtids (n). Per tant, el nombre d'operacions esperat en els pitjors dels casos és 579*14*566 = 4.587.996. Però implementant el nostre programa, el nombre d'operacions que realitza és de 439.250. Aquesta diferència és causada perquè no estem en els pitjors dels casos. Si dividim el número total d'operacions realitzades per el número total de patrons generats a partir del mRNA (439.250/566), obtenim un total de 776 operacions per cada patró aproximadament. Si el mRNA de la EPO de ratolí té uns 579 nucleòtids, això significa que per cada patró compara 1,35 nucleòtids. Ara ho podem entendre: no compara tots els nucleòtids del patró cada cop, sinó que es desplaça a una altra comparació després de trobar un mismatch, al cap d'1 - 2 nucleòtids com a mitjana d'haver iniciat el patró.
Tot i que aquest algorisme simple encara és utilitzat en diverses aplicacions com la recerca en biologia, presenta clars inconvenients: és més aviat un mètode ineficient per a subseqüències d'alfabets petits, ja que els desplaçaments que realitza són molt petits (gairebé inapreciables) i la variable de la posició ha de fer marxa enrera cada cop que es dóna un mismatch, el què es tradueix en que la seqüència ha de ser memoritzada.
En canvi, l'algorisme de Knuth-Morris-Pratt presenta una complexitat algorísmica d'ordre lineal: O(n+m). Quan hem analitzat l'algorisme simple de correspondència exacta, hem mencionat que era ineficient, ja que torna enrere la posició de la seqüència cada cop que hi ha un mismatch, i alguns nucleòtids són comparats dos o més cops, tot i que, per la informació del patró que disposem, sabem que es podria haver saltat algunes posicions. L'algorisme de Knuth-Morris-Pratt treballa més eficientment: els nucleòtids del patró i de la seqüència són comparats d'esquerra a dreta. Si es dóna un mismatch, l'algorisme busca el prefix del patró que determina el desplaçament del patró sense saltar-se cap correspondència possible. Tal i com hem explicat a l'apartat de Metodologia, la informació que necessitem per trobar el desplaçament de la posició és emmagatzemada en una taula addicional, la next table, la qual és construida comparant el patró amb ell mateix.
Acabem de comentar en línies anteriors que l'algorisme de Knuth-Morris-Pratt té una complexitat lineal en els pitjors dels casos. Si analitzem l'algorisme en si a l'apartat de Programes, sembla que s'executaria fins a n i m vegades, amb una complexitat de O(nm). Però no és així. Si recordeu el nostre algorisme, sempre que els nucleòtids del patró i de la seqüència coincideixen, la posició s'incrementa. Quan es dóna un mismatch, la posició només es desplaça enrere segons la next table, tantes vegades com s'havia incrementat anteriorment, amb un límit de 2n vegades. Això significa que té una complexitat de O(2n) en el pitjor dels casos, sense considerar la construcció de la next table, la qual també té una complexitat similar. Per tant, hauriem de tenir una complexitat global de O(2n) + O(2m) equivalent a O(n+m).
Aquest és un dels principals avantatges de l'algorisme KMP; un altre bon motiu per utilitzar-lo és que no necessita memoritzar la seqüència a comparar.
Com a inconvenients d'aquest algorisme, tenim que necessita pre-processar cada patró, i això no és la solució més eficient per alfabets més aviat llargs. Però pel nostre problema, amb l'alfabet biològic L = {A,C, G, T}, és útil.
Continuant amb l'exemple anterior dels nostres resultats de la EPO, però ara per l'algorisme Knuth-Morris-Pratt, es realitzen aproximadament unes 399.104 operacions, en comptes de les 439.250. Així doncs, podem concloure que l'algorisme Knuth-Morris-Pratt obté un guany computacional del 9,14%. I el mateix per la resta de mRNAs comprovats, que es pot observar a l'apartat de Resultats. El guany computacional mitjà de l'algorisme Knuth-Morris-Pratt versus l'algorisme simple de correspondència exacta és del 8,695%.
|
|
|
|
||
Reproducció dels resultats del mRNA de ratolí a partir de l'algorisme de Knuth-Morris-Pratt
Podem concluir que efectivament el nostre programa funciona correctament i pot corroborar els resultats obtinguts pel Dr. Robert Castelo pel gen de la EPO de Mus musculus, tal i com s'ha demostrat a l'apartat de Resultats. També dóna el desplaçament dels patrons trobats, un factor molt important per aquells patrons que es troben localitzats entre dos exons separats per algun intró. A més, hem pogut comprovar que l'estratègia automàtica de moure la llargada també funciona eficientment, ja que al reproduir les tres subseqüències n'obtenim de més curtes i úniques al cromosoma 5. Si aquesta mateixa cerca s'hagués dut a terme en tot el genoma, aquestes subseqüències més curtes no s'haguéssin trobat com a úniques.
|
||
|
|
||
Predicció de l'estructura secundària del mRNA de la EPO
Com es pot veure en les imatges de l'apartat de Resultats, obtingudes per mitjà del mFOLD, les subseqüències úniques trobades per al mRNA de la EPO es localitzen en regions suficientment exposades en la predicció de l'estructura secundària d'aquest gen.
|
||
|
|
