Calea Mărășești, Nr. 157, Bacău, 600115, Tel.Fax 40 234 [603518]

MINISTERUL EDUCA ȚIEI NAȚIONALE
UNIVERSITATEA “VASILE ALECSANDRI” din BAC ĂU
FACULTATEA de INGINERIE
Calea Mărășești, Nr. 157, Bacău, 600115, Tel./Fax +40 234
580170
http://inginerie.ub.ro, [anonimizat]
UNIVERSITATEA EUROPEI DE SUD-EST LUMINA
DEPARTAMENTUL DE ȘTIINȚE ȘI INGINERIE
PROGRAMUL DE STUDIU TEHNOLOGIA INFORMAȚIEI

LUCRARE DE DIPLOMĂ

Îndrumător:
Conferențiar Universitar D octor Beteringhe Adrian

Absolvent: [anonimizat] 2017

MINISTERUL EDUCA ȚIEI NAȚIONALE
UNIVERSITATEA “VASILE ALECSANDRI” din BAC ĂU
FACULTATEA de INGINERIE
Calea Mărășești, Nr. 157, Bacău, 600115, Tel./Fax +40 234
580170
http://inginerie.ub.ro, [anonimizat]
UNIVERSITATEA EUROPEI DE SUD-EST LUMINA
DEPARTAMENTUL DE ȘTIINȚE ȘI INGINERIE
PROGRAMUL DE STUDIU TEHNOLOGIA INFORMAȚIEI

METODE DE CALCUL ÎN BIOINFORMATICĂ

Cuprins
Capitolul I. Introducere …………………………………………………….. …………………………………………… 5  
Capitolul II. Date și structuri …………………………………………………….. …………………………………… 7  
Capitolul III. Baze de date …………………………………………………….. ……………………………………….. 9  
Capitolul IV. Fundamentel e analizei secvențiale …………………………………………………….. …….. 11 
Capitolul V. Aplicația Matlab …………………………………………………….. ………………………………… 14  
V.1. Algoritmul Needleman-Wunch …………………………………………………….. ………………………… 14  
V.1.1 Crearea matricei …………………………………………………….. ……………………………………… 16  
V.1.2 Marcarea Traseului (Traceback) …………………………………………………….. ……………….. 17  
V.1.3 Sistemul de scor …………………………………………………….. ………………………………………. 18  
V.1.4 Aplica ția Matlab-Algoritmul Needleman-Wunsch ……………………………………………….. 19  
V.2 Algoritmului Smith-Waterman …………………………………………………….. …………………………. 25  
V.2.1 Crearea matricii …………………………………………………….. ……………………………………… 26  
V.2.2 Marcarea Traseului (Traceback) …………………………………………………….. ……………….. 28  
V.2.3 Aplica ția Matlab- Algoritmul Smith-Waterman ………………………………………………….. 30  
V.3 Aliniamentului Multiplu …………………………………………………….. ………………………………….. 32  
Concluzii …………………………………………………….. ……………………………………………………… ……….. 37  
Bibliografie …………………………………………………….. ……………………………………………………… ……. 39

Capitolul I. Introducere
Bioinformatica s-a creat prin legătura strânsă pe care o are cu informatica medicală, cu
scopul de a stoca și analiza date le survenite din biologie. În ultimul timp, aceste date au început
sa aibă o cantitate foarte mare de detalii structurale, în mod deosebit de secvențe moleculare.
Informațiile noi, care trebuiau stocate și analizate cu o caden ță sporită forțau dezvoltarea unor noi
abordări în organizarea și sistematizarea datelor avănd algorit mi specifici și performanți de
prelucrare, dezvoltare care a impus pregătirea unor specialiști în bioinformatică. S-au creat foarte
multe aplicații în domeniul medical și farmaceutic și există o mare presiune creată de cererile de
implementare a aplicațiilor din acest domeniu,astfel incât, în ultimul deceniu al secolului
precedent s-au creat clasificări, la nivel de masterat, în dome niul bioinformaticii.
Caracterul interdisciplinar al bioinformaticii este foarte deta liat, continănd foarte multe
cunoștințe care sunt studiate la alte discipline similare. Bioi nformatica conține un ansamblu de
cunoștințe solide din biologia moleculară, care ea insăși forme ază un domeniu interdisciplinar ,
informații de biochimie și biologie celulară. Pe lângă aceste d omenii, este nevoie de cunoștințe
din fizică si biofizică, în primul rănd pentru întelegerea meca nismelor și proprietățiilor
structurilor analizate dar și pentru partea de prelucrare și an alizare a datelor. Acestă multitudine
de informații provenite de la mai multe discipline, uneori fară nicio similitudine între ele fac ca
acest domeniu sa fie foarte captivant și să constituie unul din tre motivele pentru care am ales
această temă.
În final, există numeroase discipline din știința calculatoarel or: sisteme de operare, baze
de date, limbaje de programare. La ora actuală există un număr mare de algoritmi utilizați în
aplicații pentru a forma o interfață menită să confere utilizat orilor accesul la bazele de date
curente și existente. Datorită bazelor de date, compararea de s ecvențe noi cu cele stocate în
bazele de date au ca soluție un rezultat în câteva minute. Chia r și cu acest ajutor, în unele
momente este nevoie de o căutare mult mai detaliată, folosindu -se un filtru de selecție mult mai
complex. Astfel, se poate determina rapid diferențierea dintre unele specii, diferențele dintre o
persoana sănătoasa și o persoana bolnavă. Ca atare, bioinformat ica ajută la o întelegere mai bună
a vieții si a diferențelelor moleculare dintre boli.
Unul dintre scopurile bioinformaticii este acela care se referă la crearea și gestionarea bazelor de
date cu caracter de informații biologice.

În ultima perioadă, datele biologice cresc într-un ritm alert d atorită progreselor biologice
pe care cercetătorii le efectuează în domenii precum: biologie moleculară, genomică și
proteomică. În luna August, anul 2000, baza de date SWISS-PROT conținea aproximativ 90000
de secvențe proteice iar baza de date GenBank gestiona aproxim ativ 8220000 de secvențe de
acizi nucleici. Aceste baze de date se dublează cantitativ la f iecare 15 luni. Ca o consecință,
datorită acestui val de informații biologice, informatica a dev enit indispensabilă, fiind nevoie de
computere care să gestioneze și să prelucreze o enormă cantitat e de date pentru ca cercetarea
biologică să obtină cât mai multe progrese. În prezent, scopul bioinformaticienilor este de a
decodifica aceste enorme cantități de date, pentru a se putea î ntelege mult mai bine cum genele pe
care fiecare organism le posedă definesc ceea ce suntem, cum ev oluează genomul și cum
funcționează organismele.
Cercetând cărți de bioinformatică, documente și tutoriale, frec ventând cursurile pe care le-
am susținut în Universitate, am constatat o dificultate aparte de întelegere a aplicabilității alinierii
secvențiale față de teoria și analiza matematică specifică aces tui domeniu.
Din acest punct de vedere, am creat o aplicație care să-i ajute pe studenți sau persoanele
interesate de acest domeniu să perceapă mult mai ușor și să poa tă să fie autodidacți, nefiind
nevoiti să platească sume consid erabile pentru achiziționarea d e aplicații foarte performante.
Lucrarea pe care am redactat-o este formată din 3 scopuri gener ale ale Bioinformaticii:
Primul scop prezintă formele și gestionarea bazelor de date în care se stochează toată
cantitatea de informații.
Al doilea obiectiv constă în metodele de calcul și algoritmi ut ilizati la efectuarea
aliniamentelor și metodelor de comparare între secvențe noi și cele deja stocate în bazele de date
curente.
Al treilea scop constituie crearea aplicațiilor pe baza acestor algoritmi și metode de calcul
pentru a se putea analiza datele informatice din punct de veder e biologic.
Lucrarea va trata aceste scopuri menționate mai sus și în conti nuare analizăm tipurile de
date și structuri utilizate în p rezent, bazele de date în care informațiile sunt stocate și utilizarea lor
în aplicații practice în Bioinformatică.

Capitolul II. Date și structuri
Pentru a defini datele utilizate în bioinformatică va voi preze nta relația dintre pacient și un
doctor. Dialogul dintre aceștia începe uzual cu prezentarea mot ivelor pentru care s-a prezentat la
medic pacientul. Aceste motive reprezintă informațiile transmis e de la pacient la medic.
Informațiile care sunt transmise în acest act medical semnifică informația medicală. Pe de altă
parte, medicul colectează informații despre pacient, informații cu un caracter individual fiind
valabile doar pentru acest pacient. Aceste informații se define sc ca fiind date. Ca atare, datele se
completează cu informații provenite din alte surse precum radio grafii, probe de laborator, etc. și
indiferent de complexitatea lor, ele ramân date, existând pentr u un anumit individ. Asadar,
datele,respectiv informațiile pe care medicul le-a aflat despre pacient pot fi de mai multe forme:

 Datele calitative (descriu simptomele)
 Datele de ordin numeric (ele sunt obținute în urma unei analize de laborator)
 Datele grafice [procedeul prin care se observă evoluția în timp (semnalul ECG)]
 Sunetele
 Imagini (radiografia, ecografia, etc.)
 Imaginile dinamice (filme)
Tipurile de date și structurile care sunt analizate în Bioinfor matică sunt evidențiate prin
descrierea valorilor numerice ale datelor care sunt studiate. A ceste date informatice pot fi de mai
multe feluri: secvențe proteice,secvențe genomice, secvențe înt regi sau parțiale de ADN, ARN,
structuri macromoleculare și alte date care fac parte din între gul genom.
Structurile secvențelor de ARN sunt formate din 4 baze azotate:
 A- reprezintă adenina
 U-reprezintă uracilul ( apare in locul timinei, față de structu rile ADN)
 C-reprezintă citozina
 G- reprezintă guanine
O înșiruire sau un grup de 3 baze azotate făcând parte din ADN poartă numele de codon și
are rolul de a purta informația pentru decodificarea aminoacizi lor în secvențe proteice. Codul
genetic, reprezintă ansamblul de corespondențe dintre aminoaciz i și codoni. Gena reprezintă o
porțiune dintr-un lanț de ADN care efectuează sinteza de protei ne. Totalitatea genelor pe care le

are un organism poartă numele de genom. Spre exemplu, genomul u man este format din
aproximativ 30.000 de gene.
Structurile secvențelor de ADN sunt formate din șiruri de câte 4 caractere, fiecare dintre
ele fiind formate dintr-o lungime nucleotidă de aproximativ 100 0 de baze. Baza de date
GenBank, stochează in prezent un total de 228719437638 de baze nucleotidice și 199341377 de
secvențe (Februarie 2017)1.

Tabel nr. I.1. Statistica GenBank la un interval de 5-7 ani

Analizând informația de-a lungul timpului, din momentul în car e aceasta este generată
până în momentul în care se utilizează, putem evidenția anumite o operații:
 Colectarea informației- semnificând tipul de informație.
 Stocarea informației- baze d e date sau de cunoștiințe.
 Transmiterea informației- existând o multidudine de metode de t ransmitere a datelor.
 Prelucrarea informației- are scopul de a sustrage elementele ch eie pentru a putea fi
analizate și utilizate.
 Protecția informației- procedeele de asigurare a integrității ș i confidențialității datelor.
 Interpretarea informației- canti tatea de date este finisată și poate fi utlizată.  

1 Statistica GenBank privind totalul bazelor nucleotidice și d e secvențe biologice
Sursa: https: //www.ncbi.nlm.nih.gov/genbank/statistics/

Capitolul III. Baze de date
Bioinformatica progresează într-un ritm alert, iar principalele aspecte sunt achiziția de
secvențe noi, introducerea și gestionarea lor in baze de date c lasificate, obține rea de informații
oferite de aceste secvențe și integrarea lor cu informațiile pr ovenite de la structuri, dezvoltarea
permanentă a instrumentelor pentru data mining și dezvoltarea u nei platforme comune pentru a
utiliza resursele. Din acest punct de vedere s-a creat Internat ional Nucleotide Sequence Database
Collaboration (INSDC), care include cele mai mari baze de date genomice din lume: GenBank,
EMBL, DDBJ.
În continuare, voi introduce un tabel cu bazele de date în func ție de tipurile pe care le au:
Tipul bazei de date Bază de date URL(adresa web)

Secvențe de
proteine (primare) SWISS-PROT
PIR-International www.expasy.ch/sprot/sprot-top.html
www.mips.biochem.mpg.de/proj/protseqdb
Secvențe de
Proteine (compuse) OWL
NRDB www.bioinf.man.ac.uk/dbbrowser/OWL
www.ncbi.nlm.nih.gov/entrez/query.fcgi?db=Protein
Secvențe de
proteine
(secundare) PROSITE
PRINTS
Pfam www.expasy.ch/prosite
www.bioinf.man.ac.uk/dbbrowser/PRINTS/PRINTS.
html
www.sanger.ac.uk/Pfam/

Structuri
macromoleculare Protein Data Bank
(PDB)
Nucleic Acids Database
(NDB)
HIV Protease Database
ReLiBase
PDBsum
CATH
SCOP
FSSP www.rcsb.org/pdb
ndbserver.rutgers.edu/
www.ncifcrf.gov/CRYS/HIVdb/NEW_DATABASE
www2.ebi.ac.uk:8081/home.html www.biochem.ucl.ac.uk/bsm/pdbsum
www.biochem.ucl.ac.uk/bsm/cath
scop.mrc-lmb.cam.ac.uk/scop
www2.embl-ebi.ac.uk/dali/fssp
Secvențe de
nucleotide GenBank
EMBL
DDBJ www.ncbi.nlm.nih.gov/Genbank www.ebi.ac.uk/embl
www.ddbj.nig.ac.jp
Secvențe de
genomi Entrez genomes
GeneCensus
COGs www.ncbi.nlm.nih.gov/entrez/query.fcgi?db=Genome bioinfo.mbb.yale.edu/genome
www.ncbi.nlm.nih.gov/COG
Baze de date
integrate InterPro
Sequence retrieval
system (SRS)
Entrez www.ebi.ac.uk/interpro
www.expasy.ch/srs5
www.ncbi.nlm.nih.gov/Entrez

Tabel nr. II.1. Baze de date utilizate în Bioinformatic ă

Bazele de date proteice sunt caracterizate în funcție de caract eristicile lor în: baze de date
primare, compuse și secundare. Cele mai utilizate (fiind cele m ai importante) sunt SWISS-PROT,
OWL și NDRB (care analizează secvențe de date de la diferite ba ze de date primare producând
șiruri de elemente, care conțin secvențe proteice din zonele de codificare în bazele de date cu
secvențe de ADN), dar și PROSITE (care gestionează informații d erivate din secvențele proteice
(lungi sau scurte) pe care le compară cu familiile de proteine deja existente și le adaugă în acele
categorii dacă există o potrivire.
Toate aceste baze de date stocheză informațiile si grupează da tele ținând cont de
similitudinile secvențiale semnificative sau de repetările pe c are le au proteinele pe anumite
poziții. Totodată, proteinele au cel mai mare coeficient de com parabilitate dintre secvențe din
punct de vedere al moștenirii sau a evoluției.
Un aspect cu o importanță sporită este dezvoltarea de metode pe ntru analizarea
similitudinilor dintre biomolecule și evidențierea celor care p rezintă una sau mai multe legături.

Capitolul IV. Fundamentel e analizei secvențiale
De-a lungul timpului, oamenii au descoperit necunoscutul compar ând elementele cu cele
cunoscute, găsind adesea deosebiri sau asemănări între structur i diferite. Pentru a aborda științific
acest lucru, s-au introdus metode prin care se exprimă cantitat iv concluzia comparației, ca să se
poată evalua modul în care anumite structuri seamană sau se deo sebesc.
Bineînteles, o comparație reală se poate efectua în metode dife rite: cantitativ, din punct de
vedere al dimensiunii, forme, proprietăți etc. Pe de altă parte , un anumit număr care să reprezinte
factorul gradului arbitrar va exista întotdeauna, pentru a grad a nivelurile de asemănari si
deosebiri între anumite structuri comparate. Totodata, chiar dacă metodele pe care le creăm,
aplicațiile implementate pentru a aduce un progres sunt imperfe cte, ele reprezintă un factor
important în analizarea cantităților enorme de informații care insoțesc materia vie.
Pentru că există cantități enorme de informații care trebuie st ocate în baze de date,
procesarea, prelucrarea și analiza acestora este foarte greu să se facă manual, astfel ca apelând la
algoritmi matematici, acest proces a fost automatizat.
S-a creat o cantitate foarte mare de soluții software pentru a studia aliniamentul
secvențial, structuri macromoleculare, și genomi. Pentru o mai bună interpretare a informațiilor
între datele folosite, programele dezvoltate pot genera aliniam entele dorite sub formă de text dar
și sub formă grafică. Programele pot fi catalogate în funcție d e algoritmii matematici folositi sau
de metodele de calcul folosite, tipul secvențelor (formatele da telor de intrare), tipul de aliniament
si cel al rezultatelor de la ieșire.
Interogările din bazele de date se pot face online, de regula c u creări de cont folosind
adresa de e-mail și direct pe site-ul corepunzător soft-ului fo losit, dar și prin descărcarea soft-
urilor dedicate pentru diferite sisteme de operare. De regula, variantele online ale bazelor de date
folosesc webservice-uri precum S OAP, POSIX threads sau alte met ode de tipul Client/Server.
Bineînteles, pentru a utiliza un mediu bioinformatic trebuie ca acesta să fie instalat pe un
sistem de operare UNIX sau Windows oferind o performantă mărită asupra datelor dar și
procesarea datelor la scară largă. Pentru a putea instala și ut iliza astfel de medii bioinformatice
sunt necesare cunoștințe aprofundate și specifice dar este nevo ie și de o mentenanță regulată
asupra server-ului și a bazelor de date. Pe de altă parte, pent ru a putea utiliza astfel de medii

bioinformatice profesionale este nevoie de un calculator de ina ltă performantă și memorii foarte
mari pentru bazele de date unde se stocheaza informațiile.
Pe de altă parte, aplicațiile web permit o flexibilitate enormă , utilizarea uneltelor și a
bazelor de date bioinformatice se poate face de oriunde, prin i ntermediul internetului, fară a mai
fi nevoie de consturi de întreți nere pentru un astfel de mediu bioinformatic.
Alte metode de interogare a bazelor de date se fac prin securit atea conexiunii și
gestionarea și utilizarea datelor senzitive (personale), folosi ndu-se protocoale de autentificare și
autorizare cu ajutorul Enterprise Java Beans (EJB) dar și alte arhitecturi existente.
Serviciile Web par ideale, permițând accesul de la distanță pen tru a gestiona și interoga
bazele de date, accesul la istrumente specifice și elaborări de instrumente bioinformatice
independente de un mediu bioinfo rmatic local. Totodată, aceste servicii prezintă căteva
dezavantaje:
 Manipularea datelor foarte mari
 Scalabilitatea și performanța scăzută a procesului de calcul
 Existența unui mecanism care să decodifice rezultatele obținute î n u r m a
aliniamentului [3, 5, 6, 7].
Aliniamentul secvențial poate fi definit ca un procedeu de comp arare a două sau mai
multe secvențe cautând similitudini între caracterele individua l e a l e s e c v e n ț e l o r . E x i s t ă
numeroase metode de calcul și algoritmi creați pentru a satisfa ce aliniamentul secvențial.
Tipuri de aliniament secvențial:
1. Aliniamente Locale și Globale
2. Aliniamente “pe perechi”
 Metode Word
 Metode Dot-Matrix
 Programare dinamică
3. Aliniamente multiple
 Programare dinamică
 Metode progresive și iterative
 Tehnici informatice
4. Aliniere Structurală ( de tip DALI, SSAP, extindere combinatori că
5. Analiză filogenetică

 Evaluarea semnificației
 Evaluarea credibilității
 Funcții de scor
Pentru că unele metode nu fac cursul aplicației create, în cont inuare voi prezenta
Aliniamentul Local (algoritmul Smith-Waterman), Aliniamentul Gl obal (algoritmul Needleman-
Wunch) și aliniamentul multiplu.

Capitolul V. Aplicația Matlab
V.1. Algoritmul Needleman-Wunch
Problema pe care cercetătorii si-au pus-o de-a lungul timpului, este găsirea unui algoritm
pentru analiza secvențială care să permită selecția alinierii o ptime între două secvențe, tinănd
cont și de o schemă de scor dată.
Algoritmul creat de Needleman și Wunsch în anul 1970, este cel mai cunoscut algoritm
pentru aliniamentul Global și poa te fi aplicat atât pe proteine cât și pe acizi nucleici.
În continuare, vom descrie algoritmul, parcurgând toate etapele sale și le exemplificăm
printr-un exemplu.
Se plasează două secvențe pe două axe ale unei matrice, și treb uie să se calculeze căte un
element din acea matrice F(i,j), unde j semnifică linia iar i c oloana.
Cele două secvențe de comparat sunt:
Secvența1=X, cu X b i= 1, n
Secvența2=Y, cu Y j, j=1, m
Se construiește o matrice N x M cu n coloane și m linii și se i ntroduce prima secvență pe axa
X, iar cea de a doua secvență pe axa Y. Vom obține:

Tabel nr. V.1. Matricea elementelor aliniamentului global
Valoarea elementului de matrice F(i,j) se efectuează în funcție de următorul raționament:

F(i,j) este calculat din precedentul număr din secvență, adică F(i-1,j-1), la care se adaugă un
“adaos” pentru similitudinile lui X i ≡ Y j sau se acordă o “penalizare” pentru substituția lui X i cu
un element din Y j ≠ X i. Bonusul sau penalizarea se notează cu S(X i,Yj) și este dată,de regulă, intr-
o matrice se subsituție. Se pot acorda orice valori de substitu ție dar ar trebui ca acestea să fie
diferite. În general, există anumite valori standard care sunt folosite: pentru numărul de potriviri
+1, pentru numărul de substituții -1 si pentru numărul de gap-u ri -2. În funcție de aceste valori
diferite, vom avea următoarea formulă:
F(i,j) = F(i-1,j-1) + S(X i,Yj)
Este posibil ca în secvențe să se introducă un “gap” pentru a crea o potrivire mai bună ale
sevențelor introduse. Bineînteles, introducerea gap-ului pentru a obține cea mai buna potrivire
este foarte greu de anticipat,dar va ieși la iveală dupa calcul ul întregii matrice. Tocmai din acest
punct de vedere, trebuie ca la calcularea matricei să ținem con t și de gap pe care putem să-l
introducem într-una din secvențe. Să presupunem că introducem u n gap în secvența Y, vom
obține:
F(i,j) = F(i-1,j) –d, unde d semnifică “penalizarea” pentru gap .
În cazul în care dorim să introducem un gap în secvența X, vom obține:
F(i,j) = F(i-1,j) –d, unde d semnifică valoarea gap-ului.
Putem a compacta cele scrise, calculul elementului din matrice F(i,j) se efectuează prin
următoarea schemă:

Figura V.1. Calcularea elementului di n matrice,Algoritmul Needleman-Wunch

Alegerea maximă a valorilor este dată de una din relațiile:

F(i,j) = max ቐܨሺ݅െ1,݆െ1 ሻ൅ܵሺXi,Yjሻ
ܨሺ݅െ1 ,݆ሻെ݀
ܨሺ݆,݅െ1ሻെ݀

V.1.1 Crearea matricei
Pentru a demonstra algoritmul vom folosi urm ătorul exemplu:
Secvența1= CGTA
Secvența2= CTA
Sistemul de scor pe care-l vom folosi este: Potriviri=1;Substitu ții=-1;Gol=-2;
Pentru a crea matricea prin Alinia mentul Global-Needleman Wunsch, vom a șeza prima
secvență pe linie, a doua secven ță pe coloan ă și completăm în dreptul fiec ărei celule cu
intervalele urm ătoare: L1=[0,-2,-4,-6,-8,…..] iar pe coloan ă același procedeu: [0,-2,-4,-6,-
8,……].

Tabel nr. V.II. Matricea de aliniere

Elementului F(0,0) îi dăm valoare 0 și vom calcula prin metodel e folosite anterior în Figura
V.1. pentru fiecare celulă. Calculăm primul element al matricei F(1,1) și o bținem :
1. Pornind din partea stânga-sus: F(1,1) = 0+1= 1
2. Pornind din partea stânga: F(1,1) = -2 -2= -4
3. Pornind de sus: F(1,1) = -2 -2= -4
Vom alege valoarea maximă (cazul 1: F(1,1) = 1) și vom completa tabelul. Acest procedeu se
va efectua pentru fiecare celulă din tabel.

Tabel nr. V.III. Completarea matricei de aliniere

V.1.2 Marcarea Traseului (Traceback)
Pentru a se putea efectua marcarea ideală a traseului ,avem nev oie de completarea matricei de
aliniere și sa ținem cont de următoarele criterii:
1. Se va pleca întotdeauna din colțul din dreapta jos F(n,m) în ca zul nostru fiind celula
F(3,4) și vom trasa săgeți spre c el mai mare număr obținut în c elulele alăturate, până vom
ajunge la valoarea 0 inițială (F(0,0)). Practic, vom marca fiec are ”pas” dar de data aceasta
2. pornim de la coadă secvențelor spre început. În final, vom obți ne alinierea globală ideală
a celor două secvențe.
3. Săgeata ”     ” se va introduce în celula din care pleacă marcarea traseului și va arata
direcția traseului spre stânga.

4. Săgeata ” ” se va introduce în celula din care pleacă marcarea traseului și va arata direcția
traseului spre sus.
5. Săgeata ” ” se va introduce în celula din care pleacă marcar ea traseului și va arata
direcția traseului spre diagonală.
Este posibil ca soluția traseului să nu fie unică, în cazul în care avem două sau mai multe
alinieri, având distanțe identice.

Tabel nr. V.IV.Marcarea traseului ideal

V.1.3 Sistemul de scor
Pentru a calcula scorul Aliniamentului Global trebuie să facem următoarele noțații generale:
 Potrivire = Două dintre litere sunt identice (similitudinea lit erelor)
 Substituție = Două dintre litere s unt diferite (diferența liter elor)
 Gol= O litera se aliniază cu un spațiu în cealaltă secvență (ga p)
În cazul studiat vom avea valorile:
 Potrivire = 1
 Substituție = -1
 Gol = -2

Un alt sistem de scor des întalnit este următorul:
 Potrivire = 2
 Substituție = -3
 Gol = -2

Aliniamentul ob ținut este:

Tabel nr. V.V.Aliniamentul Global

Scorul se obține prin efectuarea operației de scădere a numărul ui de potriviri față de
substituții și goluri. Ca atar e, scorul rezultat este:

S = P-G+P+P => 1-2+1+1=1
V.1.4 Aplica ția Matlab-Algoritmul Needleman-Wunsch
Pentru a exemplifica studiul experimental și a demonstra contri buția din acest domeniu
am realizat o aplicație creată în mediul de dezvoltare Matlab c u interfață pentru utilizator, numită
G r a p h i c a l U s e r I n t e r f a c e ( G U I ) ș i a r e s c o p u l d e a c o m p a r a ș i v i zualiza aliniamente globale,
aliniamente locale și aliniamente multiple.
Aplicația se deschide accesând fișierul „start.m” și va apărea interfața grafică pe care
utilizatorul o poate accesa mai departe.

Figura V.2.Aplica ție Matlab- Prezentare Interfa ță grafică inițială

Pentru a naviga mai departe,utilizatorul trebuie să apese buton ul Start și va apărea a doua
interfată grafică în care se poate opta pentru a alege unul din algoritmii utilizați (Vezi codul
Matlab-Anexa ) .

Figura V.2.Aplica ția Matlab-Selectarea algoritmilor

Pentru a realiza Aliniamentul Gl obal trebuie accesat butonul „N eedleman Wunsch” și se
va deschide o fereastră în car e utilizatorul trebuie să introdu că cele două secvențe pe care dorește
să le compare în câmpurile de tip text: Secvență1 și Secvență2 (Vezi codul Matlab-Anexa ) .
Totodată, utilizatorul poate seta Sistemul de penalizare (recom andat fiind să opteze pentru
Potriviri = 1, Substituții = -1, Gol-uri = -2 sau Potriviri = 2 , Substituții =- 3, Gol-uri = -2), ele
fiind setări standard.

Figura V.3.Aplica ția Matlab-Algoritmul Global

Pentru a calcula și vizualiza matricea celor două secvențe, tre buie accesat butonul
„Vizualizare Matrice” care va deschide o fereastră cu matricea dorită (Vezi codul Matlab-Anexa
).

Figura V.4.Aplica ția Matlab-Algoritm Global-Buton Vizualizare Matrice

Urmează procedura de marcare a traseului care se efectuează acc esând butonul “TraceBack” și va
deschide o nouă fereastră, care va conține literele: [ l,u,d ] cu următoarele semnificații: (Vezi
codul Matlab-Anexa )
 l = marcheaz ă direcția stânga a celulei respective
 u = marcheaz ă direcția în sus a celulei respective
 d = marcheaz ă direcția pe diagonal a celulei respective

Figura V.5.Aplica ția Matlab-Algoritm Global-Buton Traceback

Pentru a putea Vizualiza Aliniamentul final al secven țelor respective și scorul acestora, trebuie
să accesăm butoanele:
 “Vizualizare aliniament” care va afi șa în chenarul de tip text localizat mai sus
alinimentul final (Vezi codul Matlab-Anexa )
 “Scor” care va afi șa în chenarul de tip text localizat mai sus scorul (Vezi codul Matlab-
Anexa )

Figura V.6.Aplica ția Matlab-Algoritmul Global-Buton Vizualizare Aliniament și Scor

V.2 Algoritmului Smith-Waterman

Algortimul Needleman-Wunsch a fost creat pentru a obține alinia mentul global pentru
două secvențe, pe întreaga lor lungime. În timp, s-a constatat că structurile biologice s-au
modificat, însă prezintă în proporții mari porțiuni nemodificat e, păstrând funcționalitatea
moleculelor. Din acest punct de vedere, dorim să detectăm cât m ai repede similitudinile
secvențiale din proteine și să le puten compara și analiza. Gen ul acesta de analiză poartă numele
de aliniament local care poate să fie aplicat atât pe secțiuni scurte dar și extinse de ADN, insă el
are ca scop primordial analizarea similarității dintre secvențe care prezintă porțiuni asemănatoare.
Ca atare, aliniamentul local va exclude extremitățile din secv ențe, extremități care puteau
prezenta o cantitate mare de gap-uri și substituții.

În anul 1980 Smith și Waterman au creat aliniamentul local,ase mănător cu cel global dar
care are anumite modificări:
 La inițializarea matricii, marginile coloanelor și a linilor vo r avea numai valorea 0 în
detrimentul șirulu i [-2,-4,-6….]
 La efectuarea calcului pentru elementele din căsuțele matricii, se vor efectua ca în
algoritmul Needleman-Wunsch comparațiile valorilor rezultate di n căsuțele celor trei
vecini apropiați:diagonala stănga-sus, căsuța din partea stângă și cea de sus,alegând numai
valoarea maximă. În schimb, dacă toate elementele sunt negative , trebuie alocată valoarea
0. Păstrând acest raționament, matricea de aliniere o sa aibă n umai elemente pozitive sau
0.
 La trasearea marcajului (Traceback) nu vom mai pleca din ultima căsuță a matricei ci de
la cea mai mare valoare pe care matricea o are.
 Indiferent dacă secvențele aliniate au demersul de a tinde spre început, alinierea se poate
opri oriunde în matrice, ajungând chiar la marginea superioară sau la cea din stânga.

V.2.1 Crearea matricii

Matricea aliniamentui secvețial se creează aproape identic ca c ea din aliniamentul global
cu condiția ca la inițializarea liniilor și coloanelor se va in troduce valoarea 0, pentru a elimina
penalitățiile gap-urilor.
Pentru a exemplifica cele menționate vom analiza următoarele s ecvențe:
S1= GAATTCAGTTA
S2= CGGATCGA
Matricea de substituție va avea următoarele specificați standa rdizatei:
Potriviri= 5
Substituții= -3
Goluri= -4

Tabel nr. V.V.Matricea de aliniere

După ce inițializarea matricei a fost făcută vom proceda ca în cazul aliniamentului Global-
Needleman Wunsch:

 Calculăm: F(1,1)= 0-3= -3
0-4= -4 toate elementele sunt n egative și vom introduce valorea 0
0-4= -4
 Procedeul continuă cu toată linia 1,apoi ca și în aliniamentul global,trecem la următoarea
l i n i e . Î n c a z u l î n c a r e u n a d i n c ă s u ț e l e v e c i n e a r e m a i m u l t e v alori pozitive o vom
introduce pe cea mai mare iar dacă valorile sunt negative vom i sera numai valoarea 0.

Tabel nr. V.VI.Completarea matricei de aliniere

V.2.2 Marcarea Traseului (Traceback)
Procedeul de marcare a traseului (Traceback), nu va mai porni c a în aliniamentul global
din colțul dreapta-jos ci va pleca din punctul valoarei cea mai mare pe care matricea o are.
Așadar, se poate observa că valoarea maximă este 14, corespunză toare elementului F(7,8) și va
merge imediat către celula învecinată cu coeficientul cel mai m are F(7,7). Totodată, mai există
aceeasi valoare 14 și în căsuța corespunzătoare elementului F(8 ,7), fapt pentru care vom avea
două soluții de aliniament local.

Tabel nr. V.VII.Marcarea traseului ideal

După ce am aplicat procedura de marcare a traseului, obținem al iniamentele locale și scorul
acestora.

Tabel nr. V.VIII. Aliniament Local 1

Tabel nr. V.IX. Aliniament Local 2

V.2.3 Aplica ția Matlab- Algoritmul Smith-Waterman
Precum în cazul evidențiat mai sus ( V.1.4 Aplica ția Matlab-Algoritmul Needleman-
Wunsch), procedurile pe care utlizatorul trebuie să le urmeze sunt ident ice.
Pentru a calcula și vizualiza matricea celor două secvențe, tre buie accesat butonul
„Vizualizare Matrice” care va deschide o fereastră cu matricea dorită (Vezi codul Matlab-Anexa
).

Figura V.7.Aplica ția Matlab-Algoritm Local-Buton Vizualizare Aliniament

Urmează procedura de marcare a traseului care se efectuează ac cesând butonul
“TraceBack” și va deschide o nouă fereastră, care va conține li terele: [ l,u,d ] cu următoarele
semnificații: (Vezi codul Matlab-Anexa )

• l = marchează direcția stânga a celulei respective
• u = marchează direcția în sus a celulei respective
• d = marchează direcția pe diagonal a celulei respective

Figura V.8.Aplica ția Matlab-Algoritm Local-Buton Traceback

Pentru a putea Vizualiza Aliniame ntul final al secvențelor resp ective și scorul acestora,
trebuie să accesăm butoanele:
 “Vizualizare aliniament” care va afișa în chenarul de tip text localizat mai sus alinimentul
final (Vezi codul Matlab-Anexa )
 “Scor” care va afișa în chenaru l de tip text lo calizat mai sus scorul (Vezi codul Matlab-
Anexa )

Figura V.8.Aplica ția Matlab-Algoritm Local-Buton Vizualizare Aliniament și Scor

V.3 Aliniamentului Multiplu
Aliniamentul multiplu este rezultatul secvențial format din 3 sau mai multe secvențe
biologice ( în general de proteine, ADN sau ARN) cu scopul de a găsi similitudinile evolutive pe
care acestea le posedă pentru a putea observa daca secvențele a u un numitor comun.
Pentru a putea analiza aceste secvențe, am implementat un pano u (prin intermediul unei
ferestre GUI) numit “Aliniament Multiplu-NCBI-Secvențe GenBank ” cu scopul de a analiza și
vizualiza secvențe multiple putând întoarce informațiile secven țelor pe care le dorim analiza din

baza de date GenBank ( https://www.ncbi.nlm.nih.gov/genbank/ ) introducând identificatorii
(Locus sau Accesion).

Figura V.4.Aplica ția Matlab-Aliniament Multiplu-NCBI-Secven țe GenBank

Pentru a putea introduce informații cu privire la secvențele p e care dorim să le analizam
sau sa aflăm pur și simplu informații despre anumite secvențe t rebuie să accesăm site-ul
internațional ( https://www.ncbi.nlm.nih.gov/genbank/ ) să cautăm identifi catorii Locus sau
Accesion deschizând secvențele dorite de pe site și să-i introd ucem în câmpurile “Introduceti
LOCUS”.
După ce identificatorii au fost introduși în câmpurile respect ive, accesăm butonul
“Informații” care întoarce în chenarele de tip text (poziționat e în partea inferioară a panoului)
informațiile secvențelor dorite din baza de date GenBank (Vezi codul Matlab – Anexa )

Figura V.5.Aplica ția Matlab-Aliniament Multiplu-Buton Informa ții

Pentru a putea efectua aliniame ntul multiplu pentru secvențele d o r i t e , t r e b u i e s ă
introducem (prin apăsarea butonului “Introduceți FASTA”) un fiș ier FASTA de tipul *.txt. După
accesarea butonului se va deschide o nouă fereastră în care est e afișat aliniamentul multiplu.
Trebuie să existe obligatoriu cel puțin 3 secvențe pentru a se efectua aliniamentul
multiplu, în cazul în care dorim să analizăm 2 secvențe trebuie sa utilizăm o altă metoda de calcul
implementată și pretentată anterior.

Figura V.6.Aplica ția Matlab-Aliniament Multiplu-Buton Introduceti FASTA

După ce se introduce fișierul o sa apară în câmpul de tip text din GUI , aflat sub butonul
“Introduceți FASTA” (Vezi codul Matlab- Anexa ).
Pentru a putea afișa aliniamentul multiplu pentru secvențele in troduse în fișierul de tip
FASTA, trebuie să accesăm butonul “Aliniament Multiplu” care va deschide într-o nouă fereastră
aliniamentul multiplu al acestora și numele secvențelor.(Vezi c odul Matlab- Anexa )

Figura V.7.Aplica ția Matlab-Aliniament Multiplu-Buton Aliniament Multiplu

Accesând butonul “Vizualizare A liniament” se va deschide o nouă fereastră cu editorul de
s e c v e n ț e î n c a r e p u t e m v i z u a l i z a , e d i t a ș i i m p o r t a a l i n i a m e n t u l obținut. Procedeul de import
constă în introducerea aliniamentului respectiv în fișiere de t i p FASTA sau î n spațiul de lucru
alocat. (Vezi codul Matlab- Anexa ),

Figura V.8.Aplica ția Matlab-Aliniament Multiplu-Buton Vizualizare Aliniament

Concluzii
Analiza computerizată a secvențelor biologice crește considerab il în ultimul deceniu.
Îmbinarea aplicațiilor pentru analizarea aliniamentelor cu inst rumentele de căutare în bazele de
date curente, reprezintă punctele evolutive pe care acest domen iu le vizează.
Cu toate acestea, metodele computerizate sunt tot mai important e în determinarea
structurii secvențelor biologice. De obicei, procesul se bazeaz ă p e a p l i c a r e a u m a n ă a
cunoștințelor asupra unei cantități mai mici de informații și i mplementând algoritmii respectivi la
o scară mult mai mare, se diminuează considerabil timpul alocat pentru a efectua calculele
respective.
Aplicația creată vizează ca scop pr incipal ajutorul studenților s a u a p e r s o a n e l o r n o i
inițiate în acest domeniu să îmbine teoria și algoritmii matema tici într-un program care să
contribuie la o întelegere mult mai bună într-un mod prielnic. Prin intermediul ei putem efectua
numeroase metode de aliniere, să analizăm secvențe cu scopul de a descoperii similitudinile
acestora și putem avea rezultate considerabile. Totodată, în mo mentul în care analizăm anumite
secvențe biologice, putem edita și exporta rezultatele prin int ermediul algoritmilor de analiza a
aliniamentelor locale,globale și multiple.
Bineînteles, există numeroase aplicații dezvoltate în acest dom eniu și sunt în special
create pentru laboratoare științifice performante care studiază la un nivel foarte ridicat. Din cauza
acestui lucru, achiziționarea programelor și a pachetelor softw are este foarte costisitoare. Ca
atare, aplicația pe care am implementat-o poate fi un mijloc de ajutor gratuit, având în vedere că
mediul de dezvoltare Matlab poate fi instalat și utilizat în va rianta Trial.
Există numeroase metode dezvolta te prin unirea medicinei cu inf ormatica, printre care
enumerăm:
 Cartografierea tridimensională în luarea deciziilor pentru trat amentul cancerului de
prostată în stadiu precoce apărut.
 Diagnosticul genetic preimplantational (PGD) care semnifică o m etodă procedurală
FIV(Fertilizare in Vitro), prin care persoanele care au un risc mare de a transmite o boală
genetică pot să prevină șansele de a transfera această boală că tre copil.
 Analiza filogenetică care reprezintă procesul de descoperire a similitudinilor secvențelor
biologice cu scopul de a construi arborele filogenetic, pentru a obține rata de evoluție a
organismelor.

Un alt rol pe care îl are aplicația este descoperirea de asemăn ări ale aliniamentelor
secvențiale, de a efectua calcule rapide chiar dacă secvențele pe care le dorim să le analizăm sunt
foarte lungi. Pentru a analiza secvențe mari și efectuând toat e calculele manual putem pierde
enorm de mult timp față de o metodă computerizată.
Cele mai multe descoperiri științifice din acest domeniu, au fo st făcute prin compararea
aliniamentelor deja existente cu structuri de secvențe biologic e noi, realizând o conexiune
importantă. Prin aceeastă aplicație putem analiza destul de amă nunțit secvențe biologice, găsind
similitarități la nivel structural și îmbinând informațiile teo retice cu cele practice, utilizatorul
poate să studieze acest domeniu complex într-un mod captivant ș i interesant.

Bibliografie

1. Grasso, C. and Lee, C. (2004), “Combining partial order alignme nt and progressive
multiple sequence alignment increases alignment speed and scala bility to very large
alignment problems”. Bioinformatics 20, 1546–1556.
2. Gerstein M, Jansen R. (2000), “The current excitment in bioinfo rmatics, analysis of
whole-genome expression data: how does it relate to protein str ucture and function”.
Current Opinion in Structural Biology; 10:574-84.
3. Lee C. (2003), “Generating consensus sequences from partial ord er multiple sequence
alignment graphs”. Bioinformatics 19, 999–1008.
4. Needleman SB, Wunsch CD (1970). “A general method applicable to t h e s e a r c h f o r
similarities in the amino acid se quence of two proteins". J Mol Biol 48 (3): 443–53.
5. N.M. Luscombe, D. Greenbaum, M. G erstein (2001), “What is bioin formatics? An
introduction and overview”. Department of Molecular Biophysics and Biochemistry Yale
University New Haven, USA, pag. 1.
6. Altschul SF, Madden TL, Schaffe r AA, Zhang J, Zhang Z, Miller W (1997), ” Gapped
BLAST and SI-BLAST: A new generation of protein database searc h programs”. Nucleic
Acids Research.
7. Manuel Fuentes, Joshua LaBaer (2014), “Proteomics. Targheted Te chnology, Innovations
and Applications”. University of Salamanca, Spain and Arizona S tate University, USA.
8. Ryo Umetsu, Shingo Ohki, Akinobu Fukuzaki, Akihiko Konagaya, Da isuke Shinbara,
Masataka Saito, Kentaro Watanabe , Tetsuji Kitagawa, Teppei Hosh ino, “An architectural
design of open genome services (OGS)”. Advanced Genome Informat ion Technology
Group, Suehiro-cho, Tsurumi,Yokohama, Kanagawa, Japan, pag. 1-5 .
9. Keith, Jonathan M., “Bioinformat ics. Methods in Molecular Biolo gy.Volume 1:Data,
Sequence Analysis and Evolution”.

10. Warren J. Ewens, Gregory R. Grant, “ Statistical Methods in Bio informatics: An
Introduction”. Penn Center for Bioinformatics Computational Bio logy and Informatics
Laboratory, University of Pennylvania Philadelphia, PA 19104 US A.
11. Wei Huang, Brad T. Sherman, Richa rd A. Lempicki, “ Systematic a nd integrative
analysis of large gene lists usi ng DAVID bioinformatics resourc es”. Laboratory of
Immunopathogenesis and Bioinform atics, Clinical Services Progra m, SAIC-Frederick
Ins., National Cancer Institute at Frederick, Maryland 21702, U SA.
12. Jie Mei, Jianfang Gui, “Bioinformatic identification of genes e ncoding C1q-domain-
containing proteins in zebrafish”. State Key Laboratory of Fres hwater Ecology and
Biotechnology, Institute of Hidrobiologz, Chinese Academz of Sc iences, Wuhan 430072,
China.
13. Pei-Chun Hsu, M.S. Evaritus Nwulia, M.D. M.H.S Akira Sawa, M.D, “Images in
Neuroscience:Using Bioinformatic Tools”. The American Journal o f Psychiatry, August
2009, Volume 166.
14. Lesk Arthur M. Introduction to Bioinformatics (edition 3), Oxfo rd Univ Press, Oxford
UK,2008.
15. Matthew B. Scholz, Chien-Chi Lo, Patrick SG Chain, “ Next gener ation sequencing and
bioinformatic bottleneck: current state of metagenomic data ana lysis. Genome Science
Group, Los Alamos National Laboratory, Los Alamos, NM 87545, US A.