Algorisme/title> </head> <body BACKGROUND="violleta024.jpg" TEXT=#000000 VLINK=#990000> <a name="inici"></a> <FONT COLOR="#990000"> <CENTER><h1>Algorisme del CERCAEXONS</h1></CENTER></FONT> <p> <hr> <a name="disseny"></a> <p>En l'apartat <a href="metodes.html">mètodes</a> podem veure el <a href="metodes.html#disseny">disseny del programa</a> utilitzat, i els diferents mètodes que utilitzem per resoldre el problema plantejat (predir exons). I ara us mostrem com hem programat aquesta solució, és a dir l'algorisme del programa CERCAEXONS. L'algorisme ha estat realitzat seguint els principis del disseny descendent, és a dir hem anat refinant els detalls de la implementació del problema d'una forma incremental, de forma que a cada pas el programa sigui més entenedor i més intuitiu que si donéssim tots els detalls en un sol pas. D'aquesta manera hem utilitzat accions curtes que resolen només una tasca concreta, afavorint-se així la reutilització de funcions. A continuació mostrem l'algorisme utilitzat. Utilitzem una sintaxi que creiem prou entenedora. <h2>Algorisme del CERCAEXONS - Primer Nivell </h2> <p>El primer nivell consisteix en les tasques bàsiques que s'han de fer pel nostre programa, on tractem les dades d'entrada per poder obtenir el resultat del programa. <p> <dl> <dt><b>ALGORISME</b> CERCAEXONS (<b>entrada</b> fasta: <b>cadena caràcters</b>; <b>entrada</b> acceptors: <b>cadena caràcters</b>; <b>entrada</b> donadors: <b>cadena caràcters</b>; <b>entrada</b> codons: <b>cadena caràcters</b>; <b>entrada</b> llindar: <b>natural</b>; <b>entrada</b> llindar_exons: <b>natural</b>) <dd><b>variables:</b> id: <b>cadena de caràcters</b>; s: <b>vector de caràcters</b>; s_reverse: <b>vector de caràcters</b>; matriu_acceptors: <b>hash amb 3 claus: vector reals, natural i natural</b>; matriu_donadors: <b>hash amb 3 claus: vector reals, natural i natural</b>; taula_codons: <b>hash de real</b>; resultat_pos: <b>matriu</b>; resultat_neg: <b>matriu</b>; resultat_pos_bons: <b>matriu</b>; resultat_neg_bons: <b>matriu</b>; resultats_units: <b>matriu</b>; </dl> <p> <p> (id, s) = LLEGIR_FASTA(fasta); <p> matriu_acceptors := LLEGIR_MATRIU(acceptors); <p> matriu_donadors := LLEGIR_MATRIU(donadors); <p> taula_codons := LLEGIR_USCODONS(codons); <p> s_reverse := reverse(s); <p> resultat_pos := EXONS(s, matriu_acceptors, matriu_donadors, taula_codons, llindar, "+"); <p> resultat_neg := EXONS(s_reverse, matriu_acceptors, matriu_donadors, taula_codons, llindar, "-"); <p> resultat_neg := POSICIONS_REALS_STRANDNEG (resultat_neg, MIDAVECTOR(s)); <p> resultat_pos_bons := EXONS_BONS(resultat_pos, llindar_exons); <p> resultat_neg_bons := EXONS_BONS(resultat_neg, llindar_exons); <p> resultats_units := UNIR_RESULTATS(resultat_pos_bons, resultat_neg_bons); <p> ORDENAR(resultats_units); <p> FORMAT_GFF(id,resultats_units); <p><b>FI ALGORISME</b> <p> <h2>Algorisme del CERCAEXONS - Segon Nivell </h2> <p>En el segon nivell del disseny del programa, mostrem la funció més important del programa, la funció EXONS, aquesta és la funció que donada una seqüència ens prediu els EXONS possibles segons les dades introduïdes. Aquesta funció resol la tasca utilitzant la funció RESULTAT, aquesta funció la veiem més avall. La funció RESULTAT fa els càlculs necessaris per poder predir els exons segons els mètodes que utilitzem. <dl> <dt><b>FUNCIO</b> EXONS (<b>entrada</b> s: <b>vector de caràcters</b>; <b>entrada</b> matriu_acceptors: <b>hash amb 3 claus: vector reals, natural i natural</b>; <b>entrada</b> matriu_donadors: <b>hash amb 3 claus: vector reals, natural i natural</b>; <b>entrada</b> taula_codons: <b>hash de reals</b>; <b>entrada</b> llindar: <b>natural</b>; <b>entrada</b> strand: <b>caracter</b>) <b>retorna matriu</b> <dd><b>variables:</b> s0: <b>vector de caràcters</b>; s1: <b>vector de caràcters</b>; s2: <b>vector de caràcters</b>; Matriu0: <b>matriu de caràcters</b>; Matriu1: <b>matriu de caràcters</b>; Matriu2: <b>matriu de caràcters</b>; resultat0: <b>matriu</b>; resultat1: <b>matriu</b>; resultat2: <b>matriu</b>;resultatJ: <b>matriu</b>; </dl> <p> <p> s1 := PAUTES_LECTURA(s, 1); <p> s2 := PAUTES_LECTURA(s, 2); <p> matriu0 := MATRIU_STOPCODONS(s0,s,0); <p> matriu1 := MATRIU_STOPCODONS(s1,s,1); <p> matriu2 := MATRIU_STOPCODONS(s2,s,2); <p> resultat0 := RESULTAT(matriu0, matriu_acceptors, matriu_donadors, matriu_acceptors{P}, matriu_donadors{P}, taula_codons, 0, $llindar, strand, s); <p> resultat1 := RESULTAT(matriu1, matriu_acceptors, matriu_donadors, matriu_acceptors{P}, matriu_donadors{P}, taula_codons, 1, llindar, strand, s); <p> resultat2 := RESULTAT(matriu2, matriu_acceptors, matriu_donadors, matriu_acceptors{P}, matriu_donadors{P}, taula_codons, 2, llindar, strand, s); <p> resultatJ := RESULTATS_JUNTS(resultat0, resultat1, resultat2); <p> <b>retorna</b> resultatJ; <p><b>FI FUNCIO</b> <p> <dl> <dt><b>FUNCIO</b> RESULTAT (<b>entrada</b> s: <b>matriu de caràcters</b>; <b>entrada</b> hash_acceptors: <b>hash amb 3 claus: vector reals, natural i natural</b>; <b>entrada</b> hash_donadors: <b>hash amb 3 claus: vector reals, natural i natural</b>; <b>entrada</b> pa: <b>natural</b>; pd: <b>natural</b>; <b>entrada</b> hash_codons: <b>hash de reals</b>; <b>entrada</b> llindar: <b>natural</b>; <b>entrada</b> strand: <b>caracter</b>;<b>entrada</b> seq: <b>vector de caràcters</b>) <b>retorna matriu</b> <dd><b>variables:</b> splicing_acceptors: <b>vector reals</b>; splicing_donadors: </b>vector reals</b>; taula_acceptors: <b>matriu</b>; taula_donadors: <b>matriu</b>; taula_ATG: <b>matriu</b>; taula_STOP: <b>matriu</b>; combinacio_interns <b>matriu</b>; combinacio_inici: <b>matriu</b>; combinacio_term: <b>matriu</b>; combinacio_single: <b>matriu</b>; combinacio_3: <b>matriu</b>; combinacio: <b>matriu</b>; resultat_fila: <b>matriu</b>; resultat: <b>matriu</b>; i: <b>natural</b>; j: <b>natural</b>; c: <b>natural</b>; p: <b>natural</b>; </dl> <p> <p> i := 0; <p> c := 0; <p> <b>mentre</b> (i < MIDAVECTOR(s)) <b>fer</b> <p> p := COMPTARNUCLEOTIDS(s, i) <p> splicing_acceptors := FILA_SPLICING(seq, hash_acceptors, hash_acceptors{tamany}, pa, p, MIDAFILAMATRIU(s[i]})); <p> splicing_donadors = FILA_SPLICING(seq, hash_donadors, hash_donadors{tamany}, pd, p, MIDAFILAMATRIU(s[i]); <p> taula_acceptors = SOBRE_LLINDAR(splicing_acceptors, llindar); <p> taula_donadors = SOBRE_LLINDAR(splicing_donadors, llindar); <p> taula_ATG = MATRIU_ATG(s[i], pauta, i); <p> taula_STOP = MATRIU_STOP(s[i]); <p> combinacio_interns = COMBINACIONS(taula_acceptors, taula_donadors, "internal"); <p> combinacio_inici = COMBINACIONS(taula_ATG, taula_donadors, "first "); <p> combinacio_term = COMBINACIONS(taula_acceptors,taula_STOP, "terminal"); <p> combinacio_single = COMBINACIONS(taula_ATG,taula_STOP, "single "); <p> combinacio_3 = RESULTATS_JUNTS(combinacio_inici, combinacio_interns, combinacio_term); <p> combinacio = UNIR_RESULTATS(combinacio_3, combinacio_single); <p> resultat_fila = BIAIX_CODIFICANT(combinacio, hash_biaix, s[i], pauta, i); <p> resultat_fila = POSICIONS_REALS(resultat_fila,s, i, strand); <p> j := 0; <p> <b>mentre</b> (j < MIDAVECTOR(resultat_fila)) <b>fer</b> <p> resultat[c] := resultat_fila[j]; <p> j := j + 1; <p> c := c + 1; <p> <b>fmentre</b> <p> i := i + 1; <p> <b>fmentre</b> <p><b>FI FUNCIO</b> <p> <h2>Algorisme del CERCAEXONS - Tercer Nivell </h2> <p> El proper pas ha sigut refinar les funcions utilitzades, escrivint un tercer nivell de l'algorisme. Aquest pas consisteix en fer l'algorisme de cadascuna de les funcions que hem vist que ens resolen una tasca determinada. També hem afegit controls dels diferents errors d'execució que es podrien donar en el programa. Aquesta tasca ja ha sigut molt extensa, així que ja no la mostrarem aquí. <p> Per veure en detall l'algorisme implementat en llenguatge de programació PERL, aquí teniu el codi font: <a href="cgi-bin/cercaexons.pl">CERCAEXONS</a> <p> <hr> <CENTER><p><a href="#inici"><b>TORNAR A DALT</b></a></CENTER> <b> <ul> <li><a href="index.html">Servidor</a> <li><a href="objectiu.html">Plantejament del problema i objectiu del treball</a> <li><a href="introduccio.html">Introducció</a> <li><a href="materials.html">Materials</a> <li><a href="metodes.html">Mètodes</a> <p> <li><a href="resultats.html">Resultats i conclusions</a> </ul> </b> </body> </html>