siguin exactament els de p, és a dir:

Així, podrem arribar a trobar com a màxim n - m + 1 desplaçaments s.

Aquest algorisme, també conegut com de "força bruta", funciona d'una manera simple i òbvia: després d'un mismatch entre patró i seqüència, el procés de comparació s'atura i s'inicïa un altre cop desplaçant el patró una posició sobre la seqüència. En l'exemple, la comparació entre patró i seqüència comença amb la primera posició de tots dos. Com que els símbols són iguals, la comparació continua amb els dos nucleòtids següents, en els quals també hi ha coincidència. En aquest cas, la comparació també continua amb els dos nucleòtids següents però no es produeix coincidència. Així doncs, la comparació entre patró i seqüència comença un altre cop, però ara es compara la posició 0 del vector patró amb la posició 1 del vector seqüència (segon nucleòtid), i així es fa successivament, desplaçant l'inici de la comparació del patró sobre la seqüència només un nucleòtid.

A l'hora de construir la next table, s'assigna un valor de -1 a la posició 0 del vector de la next table i un 0 a la posició 1. El valor -1 a la posició 0 és un senyal qualsevol que ens serveix per començar la comparació amb el següent nucleòtid de la seqüència en el cas que es produeixi un mismatch entre la posició 0 del patró i un símbol de la seqüència. En la posició 1 del vector de la next table s'hauria de comparar el prefix de la posició 1, format exclusivament per la posició 0, amb el patró abans de la posició 1. Com que el prefix, tot i ser coincident, sempre serà màxim, assignarem directament el valor de 0 a la posició 1. Continuem amb la posició 2 del vector patró, on es mira el nombre de nucleòtids coincidents amb el patró abans d'aquella posició. En aquest cas és senzill, ja que només hem de mirar si la posició 1 (T) és igual que la posició 0 (C) del vector patró. Com que no són iguals, el valor del vector de la next table per la posició 2 serà 0. Si passem a la posició 3, hem de comparar si el prefix format per les posicions 1 i 2 o el format únicament per la 2 coindeixen amb el patró des del seu inici, és a dir, si el prefix constituït per les posicions 1 i 2 és igual a les posicions 0 i 1 o si la posició 2 és igual que la posició 0 del patró. En aquest cas, tampoc hi ha cap coincidència, de manera que el valor de la next table per la posició 3 és 0. Si mirem la posició 4, haurem de comparar els prefixos formats per les posicions 1, 2 i 3, per les posicions 2 i 3 o per la posició 3 amb el patró que els precedeix. Aquí veiem que la posició 3 és igual a la posició 0 del vector patró, així que el valor del vector de la next table per la posició 4 és igual a 1 (el prefix més gran a la posició 4 que coincideix amb el patró està format per un nucleòtid). Si ara ens centrem en la posició 5, passa el mateix que amb la posició 4, i el prefix més gran que coincideix amb el patró és d'un nucleòtid, de manera que el valor de la next table per la posició 5 és 1. Quan mirem la posició 6, tenim diferents prefixos: els formats per les posicions 1, 2, 3, 4 i 5, per 2, 3, 4, i 5, per 3, 4 i 5, per 4 i 5 i per 5. En aquest cas, el prefix format per les posicions 4 i 5 coincideix amb les posicions 0 i 1 del vector patró, i posarem un 2 (2 nucleòtids coincidents) a la posició 6 del vector de la next table. Per finalitzar amb la next table d'aquest patró, mirem l'última posició, la 7. Cap dels prefixos per aquesta posició coincideix amb el patró. Així doncs, el vector de la next table tindrà un valor de 0 a la posició 7.

Un cop construïda la next table, es procedeix a implementar el KMP. El funcionament d'aquest seria el següent: sempre que hi ha correspondència entre dos símbols (un de la seqüència i l'altre del patró) es passa a la posició següent, tant de la seqüència com del patró. En canvi, quan tenim dos símbol diferents, es comença a buscar el patró a la seqüència a partir de la posició del patró que ens indica la next table.

Per exemple:
Els dos primers nucleòtids de la seqüència són C i T i es corresponen amb els dos primers símbols del patró. Ara bé, quan arribem al tercer nucleòtid, a la seqüència trobem una C i al patró una G. Amb el KMP mirem el valor que té la next table pel tercer símbol i veiem que és un 0. Ara es compararà la posició 3 de la seqüència (on s'havia produït el mismatch) amb la posició 0 del patró, que com que és un vector, serà la primera posició, la C. Amb aquest pas ens hem estalviat la comparació del patró amb la segona posició de la seqüència, perquè al disposar de la next table (que actua com un sistema de memòria) ja sabem que aquesta comparació és innecessària perquè no pot donar lloc a una correspondència exacta amb el patró.

En la penúltima comparació del patró amb la seqüència, en què el patró comença a comparar amb el nucleòtid 5 de la seqüència, es produeix una correspondència entre els símbols fins arribar al nucleòtid número 11 de la seqüència, on hi ha una G, que es compara amb la A del patró. Com que hi ha aquest mismatch, mirem el valor d'aquesta A a la next table i observem un 2. Aleshores, es comença a comparar el símbol G de la seqüència amb el de la posició 2 del vector patró. Finalment, trobem el patró p dins la seqüència t amb un desplaçament s igual a 8.

Una vegada implementat l'algorisme de Knuth-Morris-Pratt en llenguatge de programació Perl per a la cerca de subseqüències úniques en el genoma humà del gens GH, IGF-1 i EPO, es va determinar que el temps d'execució del programa seria d'uns 40* dies aproximadament per a cada gen, en el millor dels casos. Aquest temps és molt superior als antecedents de què disposavem per part del supervisor del treball, el Dr. Robert Castelo, que ja havia implementat l'algorisme simple de correspondència exacta en llenguatge C amb la finalitat de trobar patrons únics del gen de la EPO de ratolí en el genoma d'aquest organisme. En un principi, s'havia pensat que implementant l'algorisme de Knuth-Morris-Pratt, que és més eficient que l'algorisme simple de correspondència exacta, hi hauria un guany computacional, tot i que el llenguatge Perl és més lent que el llenguatge C. Però, la gran diferència en termes de temps entre aquests dos llenguatges de programació ha fet impossible obtenir les subseqüències úniques dels gens d'interès en els terminis establerts. No obstant, hem creat un programa basat en la implementació de l'algorisme de Knuth-Morris-Pratt que és capaç de realitzar aquesta cerca de patrons únics en tot el genoma donat un mRNA. Per a la comprovació del correcte fucionament del programa hem corroborat els resultats obtinguts pel Dr. Robert Castelo, és a dir, comprovar que els tres patrons únics trobats al gen de la EPO de ratolí són subseqüències úniques del cromosoma 5 del genoma de ratolí, on es troba el locus d'aquest gen.

* El càlcul d'aquests 40 dies aproximats es va dur a terme de la següent manera:
El nostre programa contenia una sèrie de "xivatos" que ens informaven de l'estat d'execució del mateix a cada moment: la llargada a la qual buscava, el patró que comprovava i en quin cromosoma, i dins de cada cromosoma, cada cop que ja havia fet unes 50.000 línies. Mitjançant aquests "prints" a la finestra terminal vam poder detectar que, en un dels ordinadors més ràpids que el Dr. Robert Castelo ens va permetre accedir, el programa processava unes 50.000 línies cada 5 segons. Tenint en compte que el genoma de ratolí té un total de 63.299.105 línies, el programa tardaria uns 6.329,91 segons a processar tot el genoma per cada patró. Com que una hora són 3.600 segons, això serien 1,75 hores. Si pel mRNA de la EPO de Mus musculus, que té 579 nucleòtids, el programa ens genera uns 566 patrons de 14 nucleòtids, el nombre total d'hores necessàries per executar-lo és de 990,5 hores, que equivalen a uns 41 dies aproximadament.

Tal com hem comentat a l'apartat d'objectius, per poder monitoritzar l'expressió gènica del mRNA en el cas d'un possible dopatge genètic, cal disposar de seqüències específicament marcades i que siguin capaces d'hibridar selectivament amb el mRNA diana. Per aquest motiu, interessa obtenir uns patrons únics dels gens d'interès (GH, IGF-1 i EPO) que siguin accessibles als PNAs marcats i no estiguin amagats a l'estructura secundària del mRNA. Així doncs, un cop obtinguts els patrons únics al genoma (concretament en el cromosoma 5 del genoma de ratolí) a través de la implementació de l'algorisme de Knuth-Morris-Pratt, es prediu l'estructura secundària del mRNA i la localització de les subseqüències trobades del gen de la EPO amb el programa mFOLD. Aquest programa, creat pel Dr. Michael Zuker del Rensselaer Polytechnic Institute's School of Science i disponible com a servei web, és un software que prediu el plegament i l'estructura secundària tant de RNA com de DNA

La metodologia seguida en aquest projecte és la següent:

1. Implementació de l'algorisme simple de correspondència exacta de seqüències per a la cerca de patrons únics en un mRNA.
2. Implementació de l'algorisme de Knuth-Morris-Pratt de correspondència exacta de seqüències per a la cerca de patrons únics en un mRNA que també siguin únics a tot el genoma.
3. Càlcul i comparació del nombre d'operacions de nucleòtids que fan tots dos algorismes per trobar els patrons únics de cada mRNA dins del seu propi mRNA.
4. Utilitzant la implementació de l'algorisme de Knuth-Morris-Pratt, buscar si les subseqüències úniques de 14 nucleòtids (CGACAGTCGAGTTC, AGTGGTCTACGTAG i GGGTCTACGCCAAC) trobades pel Dr. Robert Castelo al gen de la EPO de ratolí són úniques al cromosoma 5 d'aquest organisme.
5. Localitzar aquestes subseqüències úniques a l'estructura secundària del mRNA de la EPO de ratolí per determinar si es troben en les regions més internes o en les més exposades.

Les seqüències utilitzades per a l'elaboració d'aquest projecte, obtingudes a la base de dades de NCBI, són les següents: