Seminari 9
Perl II
-Perl Bàsic-

Bioinformàtica - 1er trimestre curs 2012/2013 - UPF

Determinar nombres sencers positius perfectes

Direm que un nombre sencer positiu és perfecte si és igual a la suma de tots els seus divisors excepte ell mateix. Per exemple, el 6 és perfecte ja que els seus divisors són 1, 2 i 3; el 28 és perfecte ja que els seus divisors són 1, 2, 4, 7 i 14. Feu un programa en Perl que donat un nombre sencer positiu enregistrat en una variable $x ens digui si és perfecte o no (mostrant algun tipus de missatge amb la instrucció print).

Determinar nombres primers

Un nombre sencer i positiu és primer si, i només si, els seus únics divisors són 1 i ell mateix. Per exemple, el 5 és divisible per 1 i 5 però no per 2, 3 o 4, per tant és primer. En canvi, el 6, a més a més del 1 i del 6, també és divisible per 3 i per 2, per tant no és un nombre primer. Feu un programa en Perl que donat un nombre sencer positiu enregistrat en una variable $x ens digui si és primer o no (mostrant algun tipus de missatge amb la instrucció print).

Determinar nombres sencers positius amics

Direm que dos nombres sencers positius són amics si tenen el mateix quocient al dividir, cadascun d'ells, la suma dels seus divisors per ell mateix. Per exemple, els divisors del 6 són el 1, 2, 3, i el 6, i per tant sumen 12; mentre que els divisors del 28 són el 1, 2, 4, 7, 14 i 28, i per tant sumen 56; com que el quocient de dividir la suma dels divisors de 6 per ell mateix, 12/6 = 2, es igual al quocient de dividir la suma dels divisors de 28 per ell mateix, 56/28 = 2, el 6 i el 28 son amics. Si considerem el 12, els seus divisors són el 1, 2, 3, 4, 6, i el 12, que sumen 28, i per tant 28/12=14/6=7/3 que al no ser 2, el 12 no pot ser amic ni del 6 ni del 28. Feu un programa en Perl que, donats dos nombres sencers positius enregistrats en dues variables $x i $y, respectivament, ens digui si els nombres que hi ha a $x i $y són amics o no (mostrant algun tipus de missatge amb la instrucció print).

Determinar nombres sencers positius guays

Direm que un nombre sencer positiu és guay si aquest nombre és igual a la suma de qualsevol seqüència consecutiva i creixent de nombres sencers i positius més petits o iguals que ell mateix, començant a partir del 1. Per exemple, el 1 és guay ja que l'únic nombre sencer i positiu més petit o igual que ell és el propi 1; el 2 no és guay perquè ni 1 ni 1+2 són iguals a 2, el 3 en canvi si que és guay perquè 3=1+2. Fins al 10, el 4, 5, 7, 8 i 9 no són guays però, en canvi, el 6=1+2+3 i el 10=1+2+3+4 si que ho són, de guays.

Feu un programa en Perl que donat un nombre sencer positiu enregistrat en una variable $x ens digui si és guay o no mitjançant la instrucció print. Nota: l'única operació aritmètica que necessiteu és la suma.

Calcular el contingut G+C d'una seqüència de nucleòtids

Suposem que tenim una seqüència de nucleòtids escrita dins una variable de Perl $seq. Ficarem la seqüència dins un vector @v mitjançant la funció Perl split d'aquesta forma:

@v = split(//,$seq);

on cada nucleòtid dins de $seq anirà a parar a una posició dins de @v. El tenir la seqüència emmagatzemada dins un vector @v ens permet tractar individualment cada nucleòtid de la seqüència per la posició que ocupa dins el vector. Feu ara un programa en Perl al qual li entrem una seqüència de nucleòtids pel teclat i ens calcula el contingut en G+C de la seqüència com a percentage de nucleòtids G o C que hi trobem. Nota: per saber quantes posicions te un vector podem utilitzar la funció scalar que ens retorna aquest numero, de la seguent forma $longitutvector = scalar(@v). Per simplicitat, assumiu que la seqüència sempre l'entrem pel teclat en majúscules.

Comptar paraules d'una frase

Suposem que tenim una frase escrita dins una variable de Perl $f. Ficarem la frase dins un vector @v mitjançant la funció Perl split d'aquesta forma:

@v = split(//,$f);

on cada símbol dins de $f anirà a parar a una posició dins de @v. El tenir la frase escrita dins un vector @v ens permet tractar individualment cada símbol de la frase per la posició que ocupa dins el vector. Feu ara un programa en Perl al qual li entrem una frase pel teclat i ens diu quantes paraules te la frase, assumint que la frase no conte signes de puntuacio i les paraules van separades unes de les altres per un o més espais. Nota: per saber quantes posicions te un vector podem utilitzar la funció scalar que ens retorna aquest numero, de la seguent forma $longitutvector = scalar(@v).

Comptar les ocurrències de cada paraula en una frase

Ampliarem el programa de contar paraules dins una frase per tal de que al final de contar el nombre total de paraules tambe ens digui quantes vegades apareix cada paraula diferent que te la frase. Per fer això necessitareu concatenar símbols individuals i això ho podeu fer en Perl mitjançant l'operador de concatenació de texte '.' (el punt). Per exemple, si fem $x = "hola"."com estas" el resultat sera que $x contindrà el texte "holacom estas". Pista: necessitareu un vector per emmagatzemar les paraules diferents i un altre per emmagatzemar les vegades que apareix cada paraula diferent.

Correspondència exacta de símbols amb l'algorisme simple

Feu un programa en Perl que ens demani que li entrem pel teclat dues seqüències d'ADN, una més llarga, que anomenarem ``seqüència'', i una altra més curta, que anomenarem ``patró'', i ens digui a quines posicions de la seqüència, apareix replicat el patró de forma exacta. Implementeu l'algorisme simple pel qual comparem per cada posició possible de la seqüencia si s'hi correspon el patró de forma exacta. Feu que també ens digui el nombre total de comparacions de dos nucleòtids que ha fet el programa un cop ha acabat.

Correspondència exacta de símbols amb l'algorisme de Knuth-Morris-Pratt

Feu el programa que ens troba totes les correspondències exactes d'un patró d'ADN dins una seqüència però utilitzant un algorisme més eficient que l'algorisme simple, implementareu l'algorisme de Knuth-Morris-Pratt que és d'ordre lineal en la llargada de la seqüència i el patró (mentre que el simple és quadràtic).

L'algorisme de Knuth-Morris-Pratt va ser dissenyat per tres autors que donen nom a l'algorisme i que el van publicar a l'article:

KNUTH D.E., MORRIS (Jr) J.H., PRATT V.R. (1977)
Fast pattern matching in strings SIAM Journal on Computing 6(1):323-350.

la seva idea fonamental consisteix en utilitzar el fet de que, després de trobar el primer símbol que no coincideix entre el patró i la seqüència nosaltres ja coneixem els símbols del patró que hem comparat fins aquell punt. Per exemple, suposem que estem fent aquesta comparació:

posicions   0 1 2 3 4 5 6 7 8 9 
sequencia   A A A A C G T A C G
patro             A C G T T
comparacio        = = = = X

on hem començat a comparar el patro ACGTT a la posicio 3 de la seqüència, un cop fetes 4 comparacions que coincideixen, al fer la cinquena no coincideix. En aquest punt sabem que les comparacions del patró que comencen a les posicions de la seqüència 4, 5, i 6 no poden donar lloc a una ocurrencia exacta del patró, es a dir, les tres comparacions:

posicions   0 1 2 3 4 5 6 7 8 9 
sequencia   A A A A C G T A C G
patro               A C G T T
comparacio          X X X X X

posicions   0 1 2 3 4 5 6 7 8 9 
sequencia   A A A A C G T A C G
patro                 A C G T T
comparacio            X X X X X

posicions   0 1 2 3 4 5 6 7 8 9 
sequencia   A A A A C G T A C G
patro                   A C G T T
comparacio              X X X X X

eren innecessaries perque ja sabiem que no podrien donar lloc a una correspondència exacta del patro. Això ho sabiem perquè, encara que assumissim que no coneixem la seqüència on busquem, si que coneixem la composició de nucleòtids del patró. Per tant, es tracta d'aprofitar aquest fet, i això ho farem construïnt una taula de desplaçaments coincidents dins del patró, ABANS DE COMENÇAR LA CERCA.

Aquesta taula que pre-calcularem s'anomena típicament la ``next table'' i te una posició per cada símbol del patró, on a cada posició $n$ ficarem el nombre màxim de símbols que coincideixen amb el patró abans d'aquella posició (sense coincidir el prefix sencer de $n$ símbols). Per exemple, per al patró ACGTACT, la ``next table'' seria:

posicions   0 1 2 3 4 5 6
patro       A C G T A C T 
despcoinc  -1 0 0 0 0 1 2

i la cerca es faria de la següent forma:

posicions   0 1 2 3
sequencia   A C G G A C G G A C G T A C G T A C T
cerques     A C G T
                  A
                    A C G T
                          A
                            A C G T A C T
                                    A C G T A C T

on quan tenim dos símbols diferents comencem a buscar el patró a partir de la posició que ens indica la next table.

Feu que el programa ens digui quantes comparacions en total de dos nucleòtids ha fet, i proveu aquest programa i el de l'algorisme simple, amb la seqüència

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC

i el patró

AAAAAAAC

i compareu el nombre total de comparacions dels dos algorismes.