Alfabets, paraules i llenguatges.
Introducció als algorismes

Bioinformàtica - 2on trimestre curs 2006/2007 - UPF

Sovint podem representar característiques biològiques funcionals o estructurals mitjançant el que es coneix com a patrons. Podeu trobar una molt bona descripció de la utilització dels patrons per l'anàlisi de seqüències biològiques en les següents transparencies fetes a la Universitat de Skövde a Suecia.

La construcció de patrons es pot fer mitjançant el que es coneix com expressions regulars que es un formalisme matemàtic del qual els tres conceptes principals que heu d'entendre són:

• la paraula buida: $\lambda$, $\backslash\!<$, $\backslash\!>$
• la clausura positiva: $A^+$, A+
• l'estrella de kleene: $A^*$, A*

De l'introducció als algorismes els conceptes més importants que heu d'entendre són:

• la constant
• la variable
• la composició seqüencial
• la composició alternativa
• la composició iterativa

Alfabets i paraules

alfabet: conjunt finit d'elements no buit

$$\Sigma=\{a,b,c,\dots,z\}$$

els elements s'anomenen simbols o lletres, per exemple:

$$\Sigma=\{A,C,T,G\}$$

paraula: seqüència finita de símbols d'un alfabet, per exemple:

$$w=ACCTGT$$

paraula buida: paraula que no té cap símbol, la denotarem amb la lletra grega $\lambda$.

concatenació de paraules: donades dues paraules $w = ATTC$ i $w'= GTCA$, $ww'$ denotarà la concatenació de $w$ i $w'$ que correspon a

$$ww'= ATTCGTCA \;\;\;\;\; w\lambda= w$$

longitut d'una paraula: nombre de símbols

$$\vert ww'\vert=8$$

revessat d'una paraula: invertim l'ordre dels símbols

$$w=ACT\;\;\;\;\;w^R=TCA$$

palíndrom: es una paraula $w$ tal que $w=w^R$.

potència d'una paraula:

$$w^0=\lambda, \;\;\;\; w^{n+1}=ww^n$$

per exemple per una paraula $w=ACCT$,

$$w^0=\lambda, \;\;\; w^1=ACCT, \;\;\; w^2=ACCTACCT$$

subparaula: $w$ és subparaula de $v$ si

$$\exists x,y \;\; {\rm tal\;\;que} \;\; v=xwy$$

Llenguatges

llenguatge: conjunt de paraules sobre un alfabet, com ara

$$\Sigma=\{A,C,T,G\} \;\;\;\; L=\{A,CT,AG,ACTTG\}$$

concatenació de llenguatges: donat dos llenguatges

$$L_1=\{A,CT,AG\} \;\;\;\; L_2=\{G,T,C\}$$

la seva concatenació és

$$L_1L_2=\{AG,AT,AC,CTG,CTT,CTC,AGG,AGT,AGC\}$$

potència d'un llenguatge: $L^0=\{\lambda\}$, $L^i=LL^{i-1}$

$$L=\{AT,GC\}\;\;\; L^0=\{\lambda\}, \;\; L^1=L=\{AT,GC\}, \;\; L^2=\{ATAT,ATGC,GCAT,GCGC\}$$

clausura positiva d'un llenguatge: $L^+=\bigcup_{i=1}^\infty L^i$

estrella de Kleene d'un llenguatge:

$$L^*=\bigcup_{i=0}^\infty L^i=L^0\cup \bigcup_{i=1}^\infty L^i=\{\lambda\} \cup L^+$$

llenguatge universal: el denotarem per $\Sigma^*$ i correspon al conjunt de totes les paraules que es poden formar a partir d'un alfabet $\Sigma$, es a dir:

1. $\lambda\in\Sigma^*$.
2. si $w\in\Sigma^*$ llavors $aw\in\Sigma^*, \forall a\in\Sigma$.
3. no hi ha mes paraules que les generades per (1) i (2).

Reconeixedors de llenguatges

Un reconeixedor de llenguatges és un dispositiu que ens diu si una paraula donada $w$ pertany, o no a un determinat llenguatge $L$.

exemples de reconeixedors de llenguatges són:

• autòmats finits
• màquines de Turing

un autòmat finit determinista (AFD/DFA) és un vector de 5 elements:

$$M=(Q,\Sigma,\delta,q_0,q_F) \;\;\;\; {\rm on}$$

• $Q$ és un conjunt d'estats.
• $\Sigma$ és un alfabet de símbols.
• $\delta:Q\times\Sigma\rightarrow Q$ és una funció de transició que donat un estat i un símbol ens retorna un nou estat.
• $q_0$ estat inicial.
• $q_F$ estat final.

anomenem una configuració de l'autòmat al parell $(q,w)$ on $q\in Q$ es un estat i $w\in\Sigma^*$ és una paraula.

es diu que una paraula $w$ es acceptada, o reconeguda, per $M$ si a partir de la configuració $(q_0,w)$ arribem a la configuració $(q_F,\lambda)$.

els AFD's reconeixen els anomenats llenguatges regulars. Per exmple, construïm un AFD que reconegui el llenguatge regular format per les paraules sobre l'alfabet $\Sigma=\{a,b\}$ que tenen una única $b$. Necessitem 3 estats $Q=\{0,1,2\}$ on l'estat inicial $q_0=0$ i l'estat final $q_F=2$. La funció de transició $\delta:Q\times\Sigma\rightarrow Q$ seria la següent:

$delta$	a	b
0	0	1
1	1	2
2	2	2

una forma més intuitiva de representar l'AFD es mitjançant un graf com el següent:

en la representació gràfica anterior, el conjunt d'estats és $Q=\{0,1,2\}$ is els representem dins un cercle. Les fletxes entre els cercles representen les transicions entre estats. Cada fletxa te un o més símbols associats que corresponen als símbols que porten a la transició d'estat corresponent. D'aquesta forma podem representar gràficament la funció de transició $delta$. L'estat inicial està indicat amb una fletxa que l'apunta i que no surt de cap altre estat, en aquest cas doncs $q_0=0$. L'estat final es representa amb un doble cercle, en aquest cas doncs $q_F=1$.

per tal de veure si la paraula $abaaa$ seria reconeguda per l'AFD anterior començarem per la configuració inicial $(0,abaaa)$, i hem de veure si arribem a la configuració final $(1,\lambda)$, de la següent forma:

$$(0,abaaa)$$

$$(0,baaa)$$

$$(1,aaa)$$

$$(1,aaa)$$

$$(1,aa)$$

$$(1,a)$$

$$(1,\lambda)$$

per lo tant, la paraula $abaaa$ és reconeguda per l'AFD. Ara fem el mateix per la paraula $abab$:

$$(0,abab)$$

$$(0,bab)$$

$$(1,ab)$$

$$(1,b)$$

$$(2,\lambda)$$

per lo tant, la paraula $abab$ no és reconeguda per l'AFD.

Expressions Regulars

s'anomena expressió regular sobre $\Sigma$ a tota expressió que satisfà la definició recursiva següent:

1. $\emptyset,\lambda$ són expressions regulars.
2. $a$ és una expressió regular, $\forall a\in\Sigma$.
3. si $E_1$ i $E_2$ són expressions regulars, aleshores $E_1+E_2$ i $E_1E2$ són expressions regulars.
4. si $E$ és una expressió regular, aleshores $E^*$ es una expressió regular.

llenguatge associat a una expressió regular: és el llenguatge $L(E)$ definit com

1. $L(\emptyset)=\emptyset\;\;\;\; L(\lambda)=\{\lambda\}$.
2. $L(a)=\{a\}$
3. $L(E_1+E_2)=L(E_1)\cup L(E_2)$
4. $L(E_1E_2)=L(E_1)L(E_2)$
5. $L(E^*)=L(E)^*$

exemple: $\Sigma=\{A,C\}$, llavors $\lambda, A, A+C, (A+C)^*$ són expressions regulars.

quin és el llenguatge associat a l'expressió regular $(A+C)^*$ ?

$$L((A+C)^*)=(L(A+C))^*=\{A,C\}^*=\Sigma^*$$

quin és el llenguatge associat a l'expressió regular $(b+ba)^*$?

$$L((b+ba)^*)=(L(b+ba))^*=\{b,ba\}^*=\{w\vert w\;\;{\rm comenca... ...b \;\;{\rm i\;\;no\;\;te\;\;dues}\;\;a\;\;{\rm consecutives}\}$$

el llenguatge associat a una expressió regular és un llenguatge regular i per tant el podem reconeixer amb un AFD.

les expressions regulars s'utilitzen a la biologia per al reconeixement de patrons de consens.

Introducció als algorismes

Noció d'Algorisme

acció: és un aconteixement que té lloc en un periode de temps finit i produeix un resultat ben definit i previst.

el fet de que una acció duri un temps finit vol dir que es pot trobar l'instant del temps en què comença i l'instant del temps en què acaba.

informació: per tal de poder entendre el resultat de l'algorisme, és necessari que durant el temps entre l'instant en què comença l'algorisme i l'instant en què acaba, poguéssim observar o obtenir informació sobre el que està passant.

estat: el conjunt d'informació observat en un instant de temps donat (entre el principi i el final) s'anomena ''estat''.

algorisme: un algorisme és una seqüència d'accions que ens porta d'un estat inicial a un estat final en el qual obtenim el resultat.

la construcció d'un algorisme consisteix en descobrir quines accions elementals cal organitzar en el temps i, també, consisteix en escollir la forma d'organitzar-les per tal d'obtenir el resultat.

això requereix:

• capacitat d'abstracció a differents nivells, fent el que es coneix com disseny descendent.
• utilització d'un llenguatge amb notació i sintaxi precises.
• capacitat de formular i analitzar problemes.

un programa és la implementació d'un algorisme en un llenguatge de programació determinat (per exemple el Perl).

Estructures algorísmiques bàsiques

constants: són valors explícits que no varien en el curs d'execució de l'algorisme. També es coneixen com a literals. Per exemple:

1, 2, 10, 3.1416, ''hola''

variables: una variable és un nom associat a un espai a la memòria de l'ordinador on s'emmagatzema una constant o be una estructura de dades.

considerarem dues classes de variables: les variables singulars i les variables plurals.

les variables que anomenarem singulars seran aquelles que estan associades a un únic valor, mentre que les variables que anomenarem plurals seran aquelles que estan associades a dos o mes valors.

ens podem referir a una variable escrivint simplement el seu nom, com ara x, v o i. No obstant, sovint utilitzarem la notació del llenguatge Perl que distingeix explícitament el caràcter singular o plural d'una variable, de la següent forma:

• variables singulars: escrivirem el símbol del Dólar $ davant el nom de la variable, com ara $x, $i o $n.
• variables plurals: escrivirem el símbol de l'arroba @ davant el nom de la variable, com ara @v, @t o @h.

direm que a una variable li assignem un valor quan especifiquem quin valor volem que prengui la variable. Exemples d'assignacions són:

$a = 2
$a = 2 + 1
$a = $a + 1

expressions: anomenarem expressió a l'especificació sintàcticament correcta d'una o més operacions sobre un conjunt de variables, constants i funcions. Exemples d'expressions són:

1 + 1
$a + 2
3 * log($a)
($a + $b) * 2

el conjunt d'operadors aritmètics en el llenguatge Perl és el següent:

Operador	Exemple	Resultat
Suma	$a + $b	suma de a i b
Resta	$a - $b	resta de a menys b
Multiplicació	$a * $b	producte de a i b
Divisió (quocient)	$a / $b	divisió de a per b
Divisió (residu, mòdul)	$a % $b	residu de dividir a per b

les expressions regulars són un tipus (no aritmètic) d'expressió.

la composició seqüencial:

$a = 2;
$b = $a;
$b = $b + $a * 4;
print $b;

quin valor imprimirà l'algorisme anterior ?

operadors de comparació:

Comparació	Numèrica	Alfabètica
Igual	==	eq
No igual	!=	ne
Més petit que	<	lt
Més gran que	>	gt
Més petit o igual que	<=	le
Més gran o igual que	>=	ge

la composició alternativa (o condicional):

$a = 4;
$b = 7;
$c = (a * b) + 1;

if ($a % 2 == 0) {
  print "parell\n";
}
else {
  print "senar\n";
}

què imprimirà l'algorisme anterior, ''parell'' o ''senar'' ?

la composició iterativa:

$i = 0;
$s = 0;
while ($i < 10) {
  $i = $i + 1;
  $s = $s + $i;
}
print $s;

què fa l'algorisme anterior ?

Disseny d'algorismes iteratius

vector: és un tipus de variable que pot emmagatzemar més d'un valor i que permet l'accés indexat dels seus valors. També es coneix sovint com a taula o array. Per exemple:

@v = (1,2,3,4,5);

print $v[0];

emmagatzema a un vector que es diu ''v'' els valors de l'u al cinc, i la darrera instrucció imprimeix el primer valor del vector, es a dir un 1. Teniu en compte que els valors d'un vector van indexats des de la posició 0 fins a la n-1, per un vector amb n valors.

els algorismes iteratius consisteixen principalment d'un esquema algorísmic en el que una o més accions poden executar-se repetidament sense have d'especificar-les mes d'un cop. Per exemple, utilitzarem un algorisme iteratiu per sumar els valors d'un vector:

@v = (1,2,3,4,5);
$i = 0;
$s = 0;

while ($i < 5) {
  $s = $s + $v[$i];
  $i = $i + 1;
}
print $s;

suposem que al vector ''v'' tenim una seqüència d'ADN i volem contar quants nucleòtids T hi ha en aquesta seqüència. Això es pot resoldre de la següent forma:

  @v=('A','T','T','G','C','C','T','A');
  $i=0;
  $n=0;
  while ($i < 8) {
                                                                                
    if ($v[$i] eq 'T') {
      $n = $n + 1;
    }
                                                                                
    $i = $i + 1;
  }
  print "hi han ",$n," nucleotids T\n";

al programa anterior fem anar una composició alternativa amb una condició formada per una sola comparació alfanumèrica ($v[$i] eq 'T'). Si volguéssim contar el nombre de dinucleòtids TT necessitariem construir una expressió lògica formada per dues comparacions i un operador lògic de conjunció. Els operadors lògics en Perl són:

Operador	Significat
cond1 && cond2	conjunció cond1 i cond2
cond1 || cond2	disjunció cond1 o cond2
!cond	negació no cond

on cond, cond1 i cond2 fan referencia a condicions com ara:

$a == 2

$v[$i] eq 'b'

$x != 3.5

$j >= 10

$v[0] ne ' '

etc..

el programa que ens contaria els dinucleòtids TT podria ser aquest:

  @v=('A','T','T','G','C','C','T','A');
  $i=1;
  $n=0;
  while ($i < 8) {
                                                                                
    if ($v[$i] eq 'T' && $v[$i-1] eq 'T') {
      $n = $n + 1;
    }
                                                                                
    $i = $i + 1;
  }
  print "hi han ",$n," dinucleotids TT\n";