Informație

2.5: Algoritmul Needleman-Wunsch - Biologie


Vom folosi acum programarea dinamică pentru a aborda problema mai dificilă a alinierii secvenței generale. Algoritmul pe care îl vom dezvolta în următoarele secțiuni pentru a rezolva alinierea secvenței este cunoscut sub numele de algoritm Needleman-Wunsch.

Programare dinamică vs. memoizare

Înainte de a ne scufunda în algoritm, este în ordine o notă finală despre memoizare. La fel ca problema Fibonacci, problema alinierii secvenței poate fi rezolvată fie printr-o abordare de sus în jos, fie de jos în sus.

Într-o abordare recursivă de sus în jos putem folosi memoizarea pentru a crea un dicționar potențial mare indexat de fiecare dintre subproblemele pe care le rezolvăm (secvențe aliniate). Acest lucru necesită spațiu (O left (n ^ {2} m ^ {2} right) ) dacă indexăm fiecare subproblemă după punctele de început și de sfârșit ale subsecvențelor pentru care trebuie calculată o aliniere optimă. Avantajul este că rezolvăm fiecare subproblemă cel mult o dată: dacă nu este în dicționar, problema se calculează și apoi se introduce în dicționar pentru referință ulterioară.

Într-o abordare iterativă de jos în sus putem folosi programarea dinamică. Definim ordinea de calculare a subproblemelor în așa fel încât o soluție la o problemă să fie calculată odată ce subproblemele relevante au fost rezolvate. În special, subproblemele mai simple vor veni înainte de cele mai complexe. Aceasta elimină necesitatea de a urmări care subprobleme au fost rezolvate (dicționarul din memoizare se transformă într-o matrice) și asigură faptul că nu există nici o lucrare duplicată (fiecare subaliniere este calculată o singură dată).

Astfel, în acest caz particular, singura diferență practică între memoizare și programare dinamică este costul apelurilor recursive suportate în cazul memoizării (utilizarea spațiului este aceeași).

Declarație problemă

Să presupunem că avem o aliniere optimă pentru două secvențe (S_ {1 ldots n} ) și (T_ {1 ldots m} ) în care Si se potrivește cu Tj. Înțelegerea cheie este că această aliniere optimă este compusă dintr-o aliniere optimă între ( left (S_ {1}, ldots, S_ {i-1} right) ) și ( left (T_ {1}, ldots, T_ {i-1} right) ) și o aliniere optimă între ( left (S_ {i + 1}, ldots, S_ {n} right) ) și ( left (T_ {j + 1}, ldots, T_ {m} right) ). Acest lucru rezultă dintr-un argument de tăiere și lipire: dacă una dintre aceste alinieri parțiale este suboptimă, atunci tăiem și lipim o aliniere mai bună în locul celei suboptime. Acest lucru atinge un scor mai mare al alinierii globale și, prin urmare, contrazice optimitatea alinierii globale inițiale. Cu alte cuvinte, fiecare subpath dintr-o cale optimă trebuie să fie, de asemenea, optim. Observați că scorurile sunt aditive, astfel încât scorul alinierii globale este egal cu adunarea scorurilor aliniamentelor subsecvențelor. Aceasta presupune implicit că subproblemele de calcul al alinierilor optime de notare ale subsecvențelor sunt independente. Trebuie să motivăm biologic că o astfel de presupunere duce la rezultate semnificative.

Spațiul index al subproblemelor

Acum trebuie să indexăm spațiul subproblemelor. Fie (F_ {i, j} ) scorul alinierii optime a ( left (S_ {1}, ldots, S_ {i} right) ) și ( left (T_ {1 }, ldots, T_ {i} right) ). Spațiul subproblemelor este ( left {F_ {i, j}, i in [0, | S |], j in [0, | T |] right } ). Acest lucru ne permite să menținem o matrice F ((m + 1) × (n + 1) ) cu soluțiile (adică scoruri optime) pentru toate subproblemele.

Optimitate locală

Putem calcula soluția optimă pentru o subproblemă făcând o alegere locală optimă pe baza rezultatelor din subproblemele mai mici. Astfel, trebuie să stabilim o funcție recursivă care să arate modul în care soluția la o anumită problemă depinde de subproblemele sale. Și folosim această definiție recursivă pentru a umple tabelul F într-un mod ascendent.

Putem lua în considerare cele 4 posibilități (inserare, ștergere, înlocuire, potrivire) și evaluarea fiecăreia dintre ele pe baza rezultatelor pe care le-am calculat pentru subprobleme mai mici. Pentru a inițializa tabelul, setăm (F_ {0, j} = −j · d ) și (F_ {i, 0} = −i · d ) deoarece acestea sunt scorurile alinierii ( left ( T_ {1}, ldots, T_ {i} right) ) cu j goluri și ( left (S_ {1}, ldots, S_ {i} right) ) cu (i ) goluri (aka suprapunere zero între cele două secvențe). Apoi traversăm coloana matricei prin coloană calculând scorul optim pentru fiecare subproblemă de aliniere luând în considerare cele patru posibilități:

• Secvența S are un decalaj în poziția actuală de aliniere.

• Secvența T are un decalaj în poziția actuală de aliniere.

• Există o mutație (substituție nucleotidică) în poziția actuală.

• Există o potrivire la poziția actuală.

Apoi folosim posibilitatea de a produce scorul maxim. Exprimăm acest lucru matematic prin formula recursivă pentru (F_ {i, j} ):

[F (0,0) = 0 nonumber ]

[Inițializare: F (i, 0) = F (i - 1, 0) - d nonumber ]

[F (0, j) = F (0, j - 1) - d nonumber ]

[ text {Iteration}: quad F (i, j) = max left { begin {array} {l}
F (i-1, j) -d text {introduceți gol în S}
F (i, j-1) -d text {introduceți gol în T}
F (i-1, j-1) + s left (x_ {i}, y_ {j} right) text {potrivire sau mutație}
end {array} right. nonumber ]

Încheiere: în partea dreaptă jos

După parcurgerea matricei, scorul optim pentru alinierea globală este dat de (F_ {m, n} ). Ordinea de traversare trebuie să fie astfel încât să avem soluții pentru subprobleme date atunci când avem nevoie de ele. Și anume, pentru a calcula (F_ {i, j} ), trebuie să cunoaștem valorile din stânga, în sus și în diagonală deasupra (F_ {i, j} ) din tabel. Astfel putem parcurge tabelul în rândul sau coloana ordinea majoră sau chiar în diagonală de la celula din stânga sus la celula din dreapta jos. Acum, pentru a obține alinierea reală, trebuie doar să ne amintim alegerile pe care le-am făcut la fiecare pas.

Soluție optimă

Căile prin matrice (F ) corespund aliniamentelor secvenței optime. În evaluarea fiecărei celule (F_ {i, j} ) facem o alegere selectând maximul celor trei posibilități. Astfel, valoarea fiecărei celule (neinițializate) din matrice este determinată fie de celula din stânga sa, deasupra acesteia, fie în diagonală în stânga deasupra acesteia. Un meci și o înlocuire sunt ambele reprezentate ca călătorind în direcția diagonală; cu toate acestea, se poate aplica un cost diferit pentru fiecare, în funcție de faptul dacă cele două perechi de baze pe care le aliniez se potrivesc sau nu. Pentru a construi alinierea optimă efectivă, trebuie să retragem prin alegerile noastre din matrice. Este util să mențineți un indicator pentru fiecare celulă în timp ce completați tabelul care arată ce alegere a fost făcută pentru a obține scorul pentru acea celulă. Apoi, putem doar să ne urmărim indicii înapoi pentru a reconstrui alinierea optimă.

Analiza soluției

Analiza în timp de execuție a acestui algoritm este foarte simplă. Fiecare actualizare durează (O (1) ) și, deoarece există mn elemente în matricea F, timpul total de rulare este (O (mn) ). În mod similar, spațiul total de stocare este O (mn). Pentru cazul mai general în care regula de actualizare este mai complicată, timpul de rulare poate fi mai scump. De exemplu, dacă regula de actualizare necesită testarea tuturor dimensiunilor golurilor (de exemplu, costul unei goluri nu este liniar), atunci timpul de rulare ar fi (O (mn (m + n)) ).

Needleman-Wunsch în practică

Să presupunem că dorim să aliniați două secvențe S și T, unde

S = AGT

T = AAGC

Primul pas este plasarea celor două secvențe de-a lungul marginilor unei matrice și inițializarea celulelor matricei. Pentru inițializare, atribuim un 0 primei intrări din matrice și apoi completăm primul rând și coloană pe baza adăugării incrementale a penalităților de spațiu, ca în Figura 2.9 de mai jos. Deși algoritmul ar putea completa primul rând și coloană prin iterație, este important să definiți clar și să stabiliți limite pentru problemă.

Următorul pas este iterația prin matrice. Algoritmul se desfășoară fie de-a lungul rândurilor, fie de-a lungul coloanelor, luând în considerare o singură celulă la un moment dat. Pentru fiecare celulă se calculează trei scoruri, în funcție de scorurile a trei celule matrice adiacente (în mod specific intrarea de mai sus, una în diagonală în sus și în stânga și cea în stânga). Scorul maxim al acestor trei trasee posibile este atribuit intrării și pointerul corespunzător este, de asemenea, stocat. Încheierea are loc atunci când algoritmul ajunge în colțul din dreapta jos. În Figura 2.10, matricea de aliniere pentru secvențele S și T a fost completată cu scoruri și indicatori.

Pasul final al algoritmului este urmărirea optimă a căii. În exemplul nostru, începem din colțul din dreapta jos și urmăm indicatoarele disponibile până în colțul din stânga sus. Prin înregistrarea deciziilor de aliniere luate la fiecare celulă în timpul traceback-ului, putem reconstrui alinierea optimă a secvenței de la sfârșit la început și apoi o putem inversa. Rețineți că, în acest caz particular, există mai multe căi optime (Figura 2.11). O implementare pseudocod a algoritmului Needleman-Wunsch este inclusă în Anexa 2.11.4

Optimizări

Algoritmul dinamic pe care l-am prezentat este mult mai rapid decât strategia de forță brută de enumerare a alinierilor și se comportă bine pentru secvențe de până la 10 kilograme. Cu toate acestea, la scara alinierilor genomului întreg algoritmul dat nu este fezabil. Pentru a alinia secvențe mult mai mari putem aduce modificări algoritmului și îmbunătățim în continuare performanța acestuia.

Programare dinamică limitată

O posibilă optimizare este de a ignora alinierile ușor plictisitoare (MBA) sau alinierile care au prea multe goluri. În mod explicit, ne putem limita să rămânem la o anumită distanță W de diagonala din matrice

F de subprobleme. Adică, presupunem că calea de optimizare în F de la (F_ {0,0} ) la (F_ {m, n} ) se află la distanța W de-a lungul diagonalei. Aceasta înseamnă că recursivitatea (2.2) trebuie aplicată numai intrărilor în F la distanța W în jurul diagonalei, iar acest lucru generează un cost timp / spațiu de (O ((m + n) W) ) (consultați Figura 2.12).

Rețineți, însă, că această strategie este euristică și nu mai garantează o aliniere optimă. În schimb, atinge o limită inferioară a scorului optim. Acest lucru poate fi utilizat într-o etapă ulterioară în care eliminăm recursiunile din matricea F care, având în vedere limita inferioară, nu poate duce la o aliniere optimă.

Alinierea spațiului liniar

Recursivitatea (2.2) poate fi rezolvată folosind doar spațiu liniar: actualizăm coloanele din F de la stânga la dreapta, timp în care ținem evidența ultimei coloane actualizate care costă spațiul (O (m) ). Cu toate acestea, pe lângă scorul (F_ {m, n} ) al alinierii optime, dorim să calculăm și o aliniere corespunzătoare. Dacă folosim urmărirea înapoi, atunci trebuie să stocăm pointeri pentru fiecare dintre intrările în F, iar acest lucru costă spațiul (O (mn) ).

De asemenea, este posibil să găsiți o aliniere optimă folosind doar spațiu liniar! Scopul este de a folosi divide și cuceri pentru a calcula structura alinierii optime pentru o intrare matricială în fiecare pas. Figura 2.13 ilustrează procesul. Ideea cheie este că o aliniere dinamică de programare poate continua la fel de ușor în direcția inversă, începând din colțul din dreapta jos și terminând în partea stângă sus. Deci, dacă matricea este împărțită în jumătate, atunci atât o trecere înainte cât și o trecere inversă pot rula în același timp și converg în coloana din mijloc. La punctul de trecere putem adăuga împreună cele două scoruri de aliniere; celula din coloana din mijloc cu scorul maxim trebuie să se încadreze în calea optimă generală.

Putem descrie acest proces mai formal și cantitativ. Mai întâi calculați indexul de rând (u ∈ {1, ..., m} ) care se află pe calea optimă în timp ce traversați coloana ( frac {n} {2} th ). Pentru (1 ≤ i ≤ m ) și (n ≤ j ≤ n ), let (C_ {i, j} ) indică indicele rândului care se află pe calea optimă către (F_ {i, j} ) în timp ce traversați coloana ( frac {n} {2} a ). Apoi, în timp ce actualizăm coloanele lui F de la stânga la dreapta, putem actualiza și coloanele lui C de la stânga la dreapta. Deci, în (O (mn) ) timp și (O (m) ) spațiu suntem capabili să calculăm scorul (F_ {m, n} ) și de asemenea (C_ {m, n} ), care este egal cu indicele rândului (u ∈ {1,., m} ) care se află pe calea optimă în timp ce traversează coloana ( frac {n} {2} th ). Acum începe ideea de divizare și cucerire. Repetăm ​​procedura de mai sus pentru submatrixul stânga sus (u times frac {n} {2} ) și repetăm ​​și procedura de mai sus pentru dreapta jos (( mu) times frac {n} {2} ) submatricea lui F. Acest lucru se poate face folosind spațiul liniar alocat (O (m + n) ). Timpul de funcționare pentru submatricea din stânga sus este (O left ( frac {un} {2} right) ), iar timpul de funcționare pentru submatricea din dreapta jos este (O left ( frac {(mu) n} {2} right) ), care se adaugă împreună dă un timp de funcționare de (O left ( frac {mn} {2} right) = O (mn) ).

Continuăm să repetăm ​​procedura de mai sus pentru submatricele din ce în ce mai mici ale lui F, în timp ce adunăm tot mai multe intrări ale unui aliniament cu scor optim. Durata totală de rulare este (O (mn) + O left ( frac {mn} {2} right) + O left ( frac {mn} {4} right) + ldots = O (2mn ) = O (mn) ). Deci, fără a sacrifica timpul total de funcționare (până la un factor constant), împărțiți și cuceriți duce la o soluție de spațiu liniar (a se vedea, de asemenea, Secțiunea ?? din Lectura 3).


Detalii despre algoritmul Needleman – Wunsch

Încerc să înțeleg detaliile algoritmului Needleman – Wunsch și folosesc un exemplu din carte [Nello Cristianini, Matthew W. Hahn. Introducere în Genomica Computațională. O abordare a studiilor de caz, www.computational-genomics.net].

După părerea mea, algoritmul este descris nu foarte bine, așa că apare întrebarea.

De asemenea, calculul scorului pentru vecinul diagonal este de asemenea clar,

deoarece aceasta este o aliniere fără gol:

Momentul neclar este alinierea pentru vecinul din stânga (sau deasupra). Spune, vecinul stâng


3.1 Algoritmi de aliniere și programare dinamică

Una dintre primele încercări de a alinia două secvențe a fost efectuată de Vladimir Levenstein în 1965, numită „distanță de editare”, iar acum este adesea numită Distanță Levenshtein. Distanța de editare este definită ca numărul de editări de un singur caracter necesare ”pentru a schimba un cuvânt în altul. Inițial, el a descris texte scrise și cuvinte, dar această metodă a fost aplicată ulterior secvențelor biologice. Unul dintre cei mai frecvent utilizați algoritmi pentru calcularea distanței de editare este algoritmul Wagner-Fischer, un algoritm de programare dinamică.

Programarea dinamică formulează în mod optim întreaga problemă ca soluție optimă pentru piesele mai mici (subprobleme). Problema generală poate fi apoi exprimată ca o compoziție a subproblemelor. În plus față de algoritmul Wagner-Fischer, au fost dezvoltați numeroși alți algoritmi de programare dinamică pentru alinierea secvențelor biologice, inclusiv algoritmii Needleman-Wunsch [22] și Smith-Waterman [23].


Algoritmi de aliniere a secvenței

Algoritmii de programare dinamică sunt algoritmi recursivi modificați pentru a stoca rezultate intermediare, ceea ce îmbunătățește eficiența pentru anumite probleme. Algoritmul Smith-Waterman (Needleman-Wunsch) folosește un algoritm de programare dinamică pentru a găsi alinierea locală (globală) optimă a două secvențe - și. Algoritmul de aliniere se bazează pe găsirea elementelor unei matrice în care elementul este scorul optim pentru alinierea secvenței (,.) Cu (,.). Doi aminoacizi similari (de exemplu, arginina și lizina) primesc un scor mare, doi aminoacizi diferiți (de exemplu, arginina și glicina) primesc un scor scăzut. Cu cât scorul unei căi prin matrice este mai mare, cu atât este mai bună alinierea. Matricea se găsește prin găsirea progresivă a elementelor matricei, începând de la și continuând în direcțiile de creștere și. Fiecare element este setat în funcție de:

unde este scorul de similaritate al comparării aminoacidului cu aminoacidul (obținut aici din tabelul de similaritate BLOSUM40) și este pedeapsa pentru un singur decalaj. Matricea este inițializată cu. Când se obține alinierea locală Smith-Waterman, se modifică:

Penalitatea gap poate fi modificată, de exemplu, poate fi înlocuită cu, unde este penalizarea pentru o singură lacună și este numărul de lacune consecutive.

Odată găsit scorul optim de aliniere, se găsește „traceback” de-a lungul căii optime, care corespunde alinierii secvenței optime pentru scor. În următorul set de exerciții, veți implementa manual alinierea Needleman-Wunsch pentru o pereche de secvențe scurte, apoi veți efectua alinieri de secvență globală cu un program de computer dezvoltat de Anurag Sethi, care se bazează pe algoritmul Needleman-Wunsch cu o penalizare a decalajului afin ,, unde este penalizarea decalajului de extensie. Fișierul de ieșire va fi în format GCG, unul dintre cele două formate standard din bioinformatică pentru stocarea informațiilor de secvență (celălalt format standard este FASTA).

Efectuați manual o aliniere Needleman-Wunsch

În primul exercițiu veți testa algoritmul Smith-Waterman pe secvențe scurte de părți ale hemoglobinei (codul PDB 1AOW) și ale mioglobinei 1 (codul PDB 1AZI).

    Aici veți alinia secvența HGSAQVKGHG la secvența KTEAEMKASEDLKKHGT.

H G S A Î V K G H G
0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
K -8
T -16
E -24
A -32
E -40
M -48
K -56
A -64
S -72
E -80
D -88
L -96
K -104
K -112
H -120
G -128
T -136

    Primul pas este să completați scorurile de similitudine S de la căutarea meciurilor în tabelul BLOSUM40, prezentat aici etichetat cu coduri de aminoacizi de 1 literă:

    Completăm scorurile de similitudine BLOSUM40 pentru dvs. în Tabelul 4.

, folosind convenția că valorile apar în partea de sus a unui pătrat cu caractere mari, iar valorile apar în partea de jos a unui pătrat cu caractere mici. Pedeapsa noastră este de 8.

Notă: considerăm că este „predecesorul”, deoarece a ajutat valoarea decisă. Mai târziu, predecesorii se vor califica pentru a fi pe calea traceback.

Tabelul 4: Foaia de lucru a scorului de aliniere. În toate casetele de aliniere, scorul de similaritate din matricea BLOSUM40 este furnizat (text mic, partea inferioară a pătratului). Patru scoruri de aliniere sunt furnizate ca exemple (text mare, partea de sus a pătratului), încercați și calculați încă cel puțin patru, urmând direcția prevăzută în text pentru calcul.
H G S A Î V K G H G
0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
K -8
T -16
E -24
A -32
E -40
M -48
K -56
A -64
S -72
E -80
D -88
L -96
K -104
K -112
H -120
G -128
T -136
Tabelul 5: Foaie de lucru Traceback. Matricea scorului de aliniere completată (text mare, partea de sus a fiecărui pătrat) cu căutarea BLOSUM40 scorează S (text mic, partea de jos a fiecărui pătrat). Pentru a găsi alinierea, urmăriți înapoi începând din dreapta jos (T vs G, scor -21) și continuați în diagonală (în stânga și în sus), în stânga sau în sus. Totuși, procedați doar dacă pătratul din acea direcție ar fi putut fi un predecesor, în conformitate cu condițiile descrise în text.
H G S A Î V K G H G
0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
K -8
T -16
E -24
A -32
E -40
M -48
K -56
A -64
S -72
E -80
D -88
L -96
K -104
K -112
H -120
G -128
T -136

    Acum, pentru a vă verifica rezultatele cu un program de computer. Am pregătit un program de aliniere Needleman-Wunsch pereche, pereche, pe care îl veți aplica aceleași secvențe pe care tocmai le-ați aliniat manual.

/tbss.work/Bioinformatics/pairData
apoi porniți executabil aliniere pereche tastând:
pereche targlist
. Toate alinierile vor fi realizate folosind matricea BLOSUM40, cu o penalizare de spațiu de 8. Căile către fișierele de intrare și matricea BLOSUM40 utilizate sunt definite în lista de fișiere, matricea BLOSUM40 este primele 25 de linii ale fișierului blosum40. (Alte matrice de substituție pot fi găsite pe site-ul NCBI / Blast.)

Notă: În unele instalații, perechea executabilă este
în

/tbss.work/Bioinformatics/pairData și aici trebuie
tastați ./pair targlist pentru al rula.
Dacă nu puteți accesa deloc executabilul pereche, puteți vedea ieșirea din acest pas

Găsirea perechilor omoloage de clasa II ARNt sintetaze

Proteinele omoloage sunt proteine ​​derivate dintr-o genă ancestrală comună. În acest exercițiu cu algoritmul Needleman-Wunsch, veți studia identitatea secvenței mai multor sintetaze ARNt de clasa II, care sunt fie din Eucarya, Eubacteria sau Archaea sau diferă în ceea ce privește tipul de reacție de aminoacilare pe care o catalizează. Tabelul 6 rezumă tipul de reacție, organismul și codul de acces PDB și numele lanțului domeniilor de clasă II tRNA sintetază utilizate.

Specificitate Organism Cod PDB: lanț Domeniul catalitic ASTRAL
Aspartil Eubacterii 1EQR: B d1eqrb3
Aspartil Archaea 1B8A: A d1b8aa2
Aspartil Eukarya 1ASZ: A d1asza2
Glic Archaea 1ATI: A d1atia2
Histidil Eubacterii 1ADJ: C d1adjc2
Lysl Eubacterii 1BBW: A d1bbwa2
Aspartil Eubacterii 1EFW: A d1efwa3

    Am pregătit un program de calculator multiplu care va alinia mai multe perechi de proteine.


Indel este un termen folosit atât pentru operațiile de inserție, cât și pentru cele de ștergere în secvențe biologice.

Alsmirat MA, Jararweh Y, Al-Ayyoub M, Shehab MA, Gupta BB (2017) Accelerarea calculării algoritmilor de segmentare a imaginii medicale intensive folosind implementări hibrid cpu-gpu. Multimed Tools Appl 76 (3): 3537–3555

Balhaf K, Alsmirat MA, Al-Ayyoub M, Jararweh Y, Shehab MA (2017) Accelerating levenshtein and damerau edit distance algorithms using gpu with unified memory. În: 2017 a 8-a conferință internațională privind sistemele de informații și comunicații (ICICS). IEEE, pp. 7-11

Balhaf K, Shehab MA, Wala’a T, Al-Ayyoub M, Al-Saleh M, Jararweh Y (2016) Utilizarea gpus pentru a accelera calculul distanței de editare a levenshteinei. În: 2016 a 7-a conferință internațională privind sistemele de informații și comunicații (ICICS). IEEE, pp 80-84

Butenhof DR (1997) Programare cu fire POSIX. Addison-Wesley Professional, Boston

Chan S, Wong A, Chiu D (1992) O anchetă a metodelor multiple de comparare a secvențelor. Bull Math Biol: 563-598

Programare CUDA Cook S (2012): un ghid al dezvoltatorului pentru calcul paralel cu GPU-uri. Newnes, p. 16-25

De Oliveira Sandes E, Miranda G, Martorell X, Ayguade E, Teodoro G, Magalhaes Alves de Melo AC (2016) Cudalign 4.0: traceback speculativ incremental pentru alinierea exactă la nivel de cromozom în clustere GPU. IEEE Trans Parallel Distrib Syst 27 (10): 2838-2850

Durbin R, Eddy S, Krogh A, Mitchison G (1998) Analiza secvenței biologice. Cambridge University Press, Cambridge

El-Metwally S, Ouda O, Helmy M (2014) Tehnologii de secvențiere de generație următoare și provocări în asamblarea secvenței. Springer Sci Bus 7: 16-25

Fakirah M, Shehab MA, Jararweh Y, Al-Ayyoub M (2015) Accelerating needleman-wunsch algorithm global alignment algorithm with gpus. În: 2015 IEEE / ACS a 12-a conferință internațională de sisteme și aplicații informatice (AICCSA). IEEE, pp. 1-5

Farrar M (2007) Striped smith-waterman accelerează căutările bazei de date de șase ori peste alte implementări SIM. Bioinformatică 23 (2): 156-161

Gebali F (2011) Algoritmi și calcul paralel, vol 84. Wiley, New York

Gotoh O (1982) Un algoritm îmbunătățit pentru potrivirea secvențelor biologice. J Mol Biol 162 (3): 705-708

Jones C, Pevzner P (2004) O introducere în algoritmii bioinformatici. Presa MIT, Cambridge

Katoh K, Toh H (2008) Dezvoltări recente în programul de aliniere a secvențelor multiple mafft. Brief Bioinform 92: 86–98

Liu Y, Schmidt B (2015) Gswabe: aliniere mai rapidă a secvenței accelerate prin gpu cu recuperare optimă a alinierii pentru secvențe ADN scurte. Concurr Comput: Practica Experimentului 27 (4): 958–972

Lomont C (2011) Introducere în extensiile vectoriale avansate intel. Hârtie albă, Intel

Needleman SB, Wunsch CD (1970) O metodă generală aplicabilă căutării asemănărilor în secvența de aminoacizi a două proteine. J Mol Biol 48 (3): 443-453

Rognes T (2011) Caută mai rapid în baza de date Smith-Waterman cu paralelizare SIMD între secvențe. BMC Bioinform 12: 221. https://doi.org/10.1186/1471-2105-12-221

Rognes T, Seeberg E (2000) Accelerarea de șase ori a căutărilor în baza de date de secvențe smith-waterman folosind procesarea paralelă pe microprocesoare comune. Bioinformatică 16 (8): 699-706

Sanders J, Kandrot E (2010) CUDA de exemplu: o introducere în programarea GPU de uz general. Addison-Wesley Professional, Boston

Serrano JP, De Oliveira Sandes E, Magalhaes Alves de Melo A, Ujaldon M (2017) Accelerația Smith-waterman în multi-gpus: o analiză a performanței per watt. În: Bioinformatică și inginerie biomedicală - a 5-a conferință internațională de lucru, IWBBIO 2017, Granada, Spania, 26-28 aprilie 2017, Proceedings, Part II, pp 512-523

Setubal J, Meidanis J (1997) Introducere în biologia moleculară de calcul. PWS Pub, Boston

Shehab MA, Al-Ayyoub M, Jararweh Y (2015) Îmbunătățirea performanței algoritmilor fcm și t2fcm folosind gpus pentru segmentarea imaginilor medicale. În: 2015 a 6-a conferință internațională privind sistemele de informații și comunicații (ICICS), pp. 130-135

Siriwardena P, Ranasinghe N (2010) Accelerarea alinierii secvenței globale folosind cpu multi-core compatibil cuda. În: a 5-a conferință internațională de informare și automatizare pentru durabilitate (ICIAFS), pp 201-206

Vermij P (2011) Alinierea secvenței genetice pe o platformă de supercomputere. Disertație de doctorat, TU Delft, Universitatea de Tehnologie Delft

Wozniak A (1997) Folosind instrucțiuni orientate spre video pentru a accelera compararea secvenței. Comput Appl Biosci: CABIOS 13 (2): 145-150

Zhou W, Zhanxiu C, Lian B, Wang J, Jianping M (2017) Căutare în baza de date de proteine ​​a algoritmului de aliniere hibridă bazat pe accelerarea paralelă a gpu. J Supercomput. https://doi.org/10.1007/s11227-017-2030-x

Zhu X, Li K, Salah A, Shi L, Li K (2015) Implementarea paralelă a MAFFT pe hardware-ul grafic activat de cuda. IEEE / ACM Trans Comput Biol Bioinform 12 (1): 205-218. https://doi.org/10.1109/TCBB.2014.2351801


Concluzie

O euristică eficientă de aliniere a secvenței ARN în perechi, care consideră intrinsec perechi de baze suboptimale, discriminează cu exactitate între familiile de ARN structurate distincte. Atunci când este combinată cu un algoritm de concentrare bazat pe densitate tolerant la zgomot, această abordare identifică motive cunoscute și noi ale structurii ARN dintr-un set de secvențe de intrare fără cunoștințe a priori. Motivele rezultate ale structurii ARN sunt ulterior utilizate pentru a identifica omologi în genomul uman, îmbunătățind adnotarea lncRNA și crescând repertoriul elementelor genetice funcționale.


Alinierea și importanța secvenței:

Alinierea secvențeisau compararea secvenței se află în centrul bioinformaticii, care descrie modul de aranjare a ADN / ARN sau a secvențelor proteice, pentru a identifica regiunile de similaritate dintre ele. Este folosit pentru a deduce relația structurală, funcțională și evolutivă între secvențe. Alinierea găsește un nivel de similaritate între secvența de interogare și diferite secvențe de baze de date. Algoritmul funcționează prin abordare de programare dinamică, care împarte problema în subprobleme independente mai mici. Acesta găsește alinierea mai cantitativ prin atribuirea scorurilor.

Când se găsește o nouă secvență, structura și funcția pot fi ușor de prezis făcând alinierea secvenței. Din moment ce se crede că, o secvență care împarte strămoșul comun ar prezenta o structură sau o funcție similară. Cu cât este mai mare similitudinea secvenței, cu atât este mai mare șansa ca aceștia să aibă o structură sau o funcție similară.

Metode de aliniere a secvenței:

Există în principal două metode de aliniere a secvenței:

Alinierea globală: Secvențele strâns legate de aceeași lungime sunt foarte potrivite pentru alinierea globală. Aici, alinierea se efectuează de la începutul până la sfârșitul secvenței pentru a afla cea mai bună aliniere posibilă.

Algoritmul Needleman-Wunsch (O formulă sau un set de pași pentru rezolvarea unei probleme) a fost dezvoltat de Saul B. Needleman și Christian D. Wunsch în 1970, care este un algoritm de programare dinamică pentru alinierea secvenței. Programarea dinamică rezolvă problema inițială împărțind problema în subprobleme independente mai mici. Aceste tehnici sunt utilizate în multe aspecte diferite ale informaticii. Algoritmul explică alinierea secvenței globale pentru alinierea secvențelor de nucleotide sau proteine.

Aliniere locală: Secvențele despre care se suspectează că au similarități sau chiar secvențe diferite pot fi comparate cu metoda de aliniere locală. Acesta găsește regiuni locale cu un nivel ridicat de similitudine.

Aceste două metode de aliniere sunt definite de algoritmi diferiți, care utilizează matrici de notare pentru a alinia cele două serii diferite de caractere sau tipare (secvențe). Cele două metode diferite de aliniere sunt în mare parte definite prin abordarea de programare dinamică pentru alinierea a două secvențe diferite.

Programare dinamică:

Programarea dinamică este utilizată pentru alinierea optimă a două secvențe. Acesta găsește alinierea într-un mod mai cantitativ, oferind câteva scoruri pentru meciuri și nepotriviri (matrici de scor), mai degrabă decât aplicând doar puncte. Căutând cele mai mari scoruri din matrice, alinierea poate fi obținută cu precizie. Programarea dinamică rezolvă problema inițială împărțind problema în subprobleme independente mai mici. Aceste tehnici sunt utilizate în multe aspecte diferite ale informaticii. Algoritmii Needleman-Wunsch și Smith-Waterman pentru alinierea secvenței sunt definiți prin abordarea de programare dinamică.

Matrici de notare:

În procedurile optime de aliniere, majoritatea algoritmilor Needleman-Wunsch și Smith-Waterman folosesc sistemul de notare. Pentru alinierea secvenței de nucleotide, matricele de notare utilizate sunt relativ mai simple, deoarece frecvența mutației pentru toate bazele este egală. O valoare pozitivă sau mai mare este atribuită pentru o potrivire și o valoare negativă sau mai mică este atribuită pentru nepotrivire. Aceste scoruri bazate pe presupuneri pot fi utilizate pentru punctarea matricelor. Există alte matrice de notare care sunt predefinite în cea mai mare parte, utilizate în cazul substituțiilor de aminoacizi.

Principalele matrice predefinite utilizate sunt PAM și BLOSUM.

Matrici PAM: Margaret Dayhoff a fost prima care a dezvoltat matricea PAM, PAM înseamnă Point Accepted Mutations. Matricile PAM sunt calculate prin respectarea diferențelor în proteinele strâns legate. O unitate PAM (PAM1) specifică o mutație punctuală acceptată la 100 de resturi de aminoacizi, adică o modificare de 1% și 99% rămâne ca atare.

BLOSUM: BLOcks SUbstitution Matrix, dezvoltată de Henikoff și Henikoff în 1992, a folosit regiuni conservate. Aceste matrice sunt valori procentuale reale ale identității. Pur și simplu să spun, acestea depind de similitudine. Blosum 62 înseamnă că există o asemănare de 62%.

Scorul decalajului sau penalizarea decalajului: Algoritmii de programare dinamică utilizează penalizări ale lacunelor pentru a maximiza semnificația biologică. Penalitatea decalajului este scăzută pentru fiecare decalaj introdus. Există diferite penalizări ale decalajului, cum ar fi deschiderea decalajului și extinderea decalajului. Scorul gap definește o penalizare acordată alinierii atunci când avem inserare sau ștergere. În timpul evoluției, poate exista un caz în care putem vedea goluri continue de-a lungul secvenței, astfel încât penalizarea spațiului liniar nu ar fi adecvată alinierii. Astfel, gap-ul deschis și extensia gap-ului au fost introduse atunci când există goluri continue (cinci sau mai multe). Penalizarea deschisă se aplică întotdeauna la începutul decalajului, iar apoi celelalte decalaje care urmează acestuia se acordă cu o penalizare de extensie a decalajului care va fi mai mică în comparație cu penalizarea deschisă. Valorile tipice sunt –12 pentru deschiderea decalajului și –4 pentru extensia decalajului.


Introducere

Astăzi, conceptul de rețea Internet of Things (IoT) a devenit o parte integrantă a infrastructurii informaționale moderne a societății. IoT este o rețea unică care conectează obiectele inteligente ale lumii reale și obiectele virtuale din jurul nostru. Numărul și variabilitatea acestor obiecte (dispozitive inteligente) continuă să crească, afectând diferite aspecte ale vieții umane, de la vehicule la electronice mobile și asistență medicală [26]. In other words, the IoT is not just a set of different devices and sensors connected by wired and wireless communications and the global cyber space of the Internet, but it is a closer integration of the real and virtual worlds, in which communication takes place between people and devices.

The sustainability of IoT is the availability of the system to perform its functions in the context of external influence [6]. Considering that the subsystems and components of the IoT have many horizontal connections, thus forming a heterogeneous cyber infrastructure with a large number of entities, most of which lack built-in protection mechanisms the problem of network security in such networks is especially actual. Main attack vectors are aimed for overtaking the control by the IoT device and capturing the confidential data, as well as the purposeful node deactivation [1]. Not only objects of the virtual world�ta, files, personal information𠅊re under threat, but also physical objects of the real world. According to a report by Kaspersky Laboratory, in the first half of 2019, more than 100 million attacks were detected on the smart IoT devices, which are seven times more than in the <"type":"entrez-nucleotide","attrs":<"text":"H12018","term_id":"876838","term_text":"H12018">> H12018 [10]. Network infrastructure and wireless data transmission channels are the most vulnerable objects of the modern infocommunication environment [27]. Attackers using wireless links can remotely invade a target subnet or device (group of devices), intercept traffic, launch denial of service attacks (including distributed attacks), and take control of the IoT devices to create megabotnets.

In 2020, the world is facing with the COVID-2019 coronavirus pandemic, and life has almost completely moved to the network, people around the world work, study, shop and have fun online. This could not affect the goals of the cybercriminals, medical organizations, educational services, delivery, etc., faced massive DDoS attacks. A large network of hospitals in France fell victim to one of these attacks, when attackers tried to disable the infrastructure of medical institutions. As a result of the attack, hospital staff working remotely was unable to use work programs and corporate e-mail for some time. In Germany, on the first day of distance learning, a distance learning platform was attacked. The service through which teachers exchange teaching materials, homework, and tests with students was not available. In the Netherlands, the food delivery service Thuisbezorgd was unable to process orders as a result of a DDoS attack and had to refund customers. In the first quarter of 2020, there was a significant increase in the number and quality of DDoS attacks. In particular, the popularity of smart attacks that exploit vulnerabilities in the network infrastructure is noted. SYN flood is the leader among the types of attacks (92.6%) the share of attacks via ICMP continued to grow and exceeded the share of UDP and TCP floods (Kaspersky [11].

To counter cyber attacks at the IoT, as in traditional networks, various intrusion detection systems (IDS) are applied (e.g., [17]. There are two main approaches on which most the IoT IDSs are based: anomaly detection and misuse detection. The advantages of the former are a global view on the network, the ability to detect new attacks, and the use of fewer rules (compared to signature methods) their disadvantages include a high level of errors of the first and second kind and low adaptation for changing conditions (new profiles, dynamic anomalies). The advantages of an IDS based on search for abuse are reliability, speed, low false positives for known intrusions. Its disadvantages are the strict dependence on the relevance of the signature base and the impossibility of detecting new attacks.

The work of an IDS usually consists of three stages: (1) monitoring, (2) sequence extraction and misuse detection by pattern matching, (3) signaling of attack to provide the attack response. Matching with attack patterns is currently the main method for IDS when detecting malicious activity [13] however, it has two significant drawbacks. Firstly, the IoT-specific attacks, such as forced power consumption, forced topology change, etc., have a split sequence of operations, time intervals in the chain of actions, and some attacks may also have a non-linear sequence of actions. Secondly, there is a class of polymorphic attacks that have mutations (namely local differences, omissions, delays) in the sequences of actions during the implementation of the attack. These polymorphic attacks adapt to a wide range of conditions, operating systems, and circumstances and try to avoid scanning by defenses to infect endpoints [8]. They are called the polymorphic attacks because they have different signatures that make them difficult to identify using a single signature. For example, in order to disguise ongoing network attacks, attackers can use polymorphic shellcode to create unique attack patterns. This method usually involves encoding the payload, with the decoder placed at the front of the payload before sending it. All known the pattern matching methods do not detect such variations of a single sample.

Our research proposes new, the nature inspired, technologies, namely a genetic sequence alignment computing and a sequence similarity calculation, instead of massive equity checking of multiple packets and signatures traditionally used for the IDS composing. The aim of our research is to assess the prospects of using the biological coded sequence alignment algorithms for solving the task of detection the specific network intrusions. The novelty of our results is the fact that it has been proposed to encode network packets (or the chain of activity acts) into the sequences of the nucleotide codes for their subsequent alignment and matching with patterns. The matching operation is based on the similarity checking, not equity checking, as it was usually applied for the intrusion detection. Therefore, our contribution to the cyber security is the proposed bio-inspired approach that, in contrast to traditional methods, makes it possible to detect new variations of the attacks in the IoT networks, to reduce the signature database, and to increase the detection effectiveness on the low-resource devices.

The following material is organized in the next manner: Sect.ਂ reviews successful cases of applying modern nature-inspired methods in solving cyber security issues Sect.ਃ discusses methods for aligning sequences: global, local, and additive approaches Sect.਄ presents the proposed coding and alignment technique Sect.ਅ presents our results of the experiments on detecting the DDoS attacks using a BoT-IoT dataset on the portative IoT Raspberry Pi4 platform Sect.ਆ presents a discussion of the results of applying the bio-inspired methods Sect.ਇ concludes our contribution.


Fundal

Biological sequence alignment is a cornerstone of bioinformatics and is widely used in such fields as phylogenetic reconstruction, gene finding, genome assembly. The accuracy of the sequence alignments and similarity measures are directly related to the accuracy of subsequent analysis. CDS alignment methods have many important applications for gene tree and protein tree reconstruction. In fact, they are useful to cluster homologous CDS into groups of orthologous splicing isoforms [1, 2] and combine partial trees on orthology groups into a complete protein tree for a gene family [3, 4]. Aligning and measuring the similarity between homologous CDS requires to account for frameshift (FS) translations that cannot be detected at the amino acid (AA) level, but lead to a high similarity at the nucleotide level between functionnaly different sub-sequences.

FS translation consists in alternative AA translations of a coding region of DNA using different translation frames [5]. It is an important phenomenon resulting from different scenarios such as, insertion or deletion of a nucleotide sequence whose length is not a multiple of 3 in a CDS through alternative splicing [6, 7] or evolutionary genomic indels [8, 9], programmed ribosomal frameshifting [10], or sequencing errors [11]. Recent studies have reported the role of FS translations in the appearance of novel CDS and functions in gene evolution [6, 12]. FS translation has also been found to be linked to several diseases such as the Crohn’s disease [13]. The computational detection of FS translations requires the alignment of CDS while accounting for their codon structure. A classical approach for aligning two CDS used in most alignment tools [14, 15] consists in a three-step method, where the CDS are first translated into AA sequences using their actual coding frame, then AA sequences are aligned, and finally the AA alignment is back-translated to a CDS alignment. This approach does not account for alternative AA translations between two CDS and it leads to incorrect alignment of the coding regions subject to FS translation. The opposite problem of aligning protein sequences while recovering their hypothetical nucleotide CDS sequences and accounting for FS translation was also studied in several papers [16, 17].

Here, we consider the problem of aligning two CDS while accounting for FS translation, by simultaneously accounting for their nucleotide and AA sequences. The problem has recently regained attention due to the increasing evidence for alternative protein production through FS translation by eukaryotic gene families [18, 19].

The problem was first addressed by Hein et al. [20, 21] who proposed a DNA/protein model such that the score of an alignment between two CDS of length n și m is a combination of its score at the nucleotide level and its score at the AA level. They described a O(n 2 m 2 ) algorithm in [20], later improved to a O(nm) algorithm in [21] for computing an optimal score alignment, under the constraint that the search space of the problem is restricted. Arvestad [22] later proposed a CDS alignment scoring model with a O(nm) alignment algorithm accounting for codon structures and FS translations based on the concept of generalized substitutions introduced in [23]. In this model, the score of a CDS alignment depends on its decomposition into a concatenation of codon fragment alignments, such that a codon fragment of a CDS is defined as a substring of length w, (0le w le 5) . This decomposition into codon fragment alignments allows to define a score of the CDS alignment at the AA level. More recently, Ranwez et al. [18] proposed a simplification of the model of Arvestad limiting the maximum length of a codon fragment to 3. Under this model, a O(nm) CDS alignment algorithm was described and extended in the context of multiple sequence alignment [18]. In the models of Arvestad [22] and Ranwez et al. [18], several scores may be computed for the same alignment based on different decompositions into codon fragment alignments. The corresponding algorithms for aligning two CDS then consist in computing an optimal score decomposition of an alignment between the two CDS. This optimal score exclusively accounts for FS translation initiations, i.e a FS translation in an alignment is penalized by adding a constant FS cost, which only penalizes the initiation of the FS, not accounting for the length of this FS translation. However, taking account of FS translation lengths is important in order to increase the precision of CDS alignment scores, as these lengths induce more or less disruptions between the protein sequences.

In this paper, we propose the first alignment algorithm that accounts for both the initiation and the length of FS translations in order to compute the similarity scores of CDS alignments. The remaining of the paper is organized as follows. In the “Motivation”, we illustrate the importance of accounting for FS translation length when aligning CDS. In the “Preliminaries”, we give some preliminary definitions and we introduce a new CDS alignment scoring model with a self-contained definition of the score of an alignment penalizing both the initiation and the extension of FS translations. In the “Methods”, a dynamic programming algorithm for computing an optimal score alignment between two CDS is described. Finally, in the “Results”, we present and discuss the results of a comparison of our method with other CDS alignment methods for a pairwise comparison of CDS from homologous genes of ten mammalian gene families.

Motivation: importance of accounting for FS translation length

The two main goals of aligning biological sequences are to evaluate the similarity and to identify similar regions between the sequences, used thereafter to realize molecular analyses such as evolutionary, functional and structural predictions. In practice, CDS alignment can be used to exhaustively identify the conserved features of a set of proteins. Thus, the definition of CDS similarity must account for sequence conservation and disruptions at both the nucleotide and the protein levels.

Figure 1 illustrates the importance of accounting for AA translations and FS translation length in order to compute an adequate similarity score for a CDS alignment. It describes an example of three CDS Seq1 , Seq2 and Seq3 . Seq1 has a length of 45. The CDS Seq2 has length 60 and is obtained from Seq1 by deleting the nucleotide ‘G’ at position 30 and adding 16 nucleotides at the end. The CDS Seq3 has length 60 and is obtained from Seq1 by deleting the nucleotide ‘G’ at position 15 and adding 16 nucleotides at the end.

Top an example of three CDS Seq1 , Seq2 and Seq3 . Mijloc an optimal alignment between Seq1 and Seq2 with a FS translation region of length 15. Partea de jos an optimal alignment between Seq1 and Seq3 with a FS translation region of length 30

When looking at the AA translations of Seq1 , Seq2 and Seq3 , we observe that the similarity between Seq2 and Seq1 is higher than the similarity between Seq3 and Seq1 at the protein level, because Seq1 and Seq2 share a longer AA prefix “M T E S K Q P W H” (amino acids in black characters in the alignments). However, the pairwise CDS alignment algorithms that do not account for the length of FS translations would return the same score for the two following optimal alignments of Seq1 with Seq2 and Seq1 with Seq3 , penalizing only the initiation of one FS translation in both cases (positions marked with a “!” symbol in the alignments), and not penalizing the sequence disruptions at the protein level.

From an evolutionary point of view, a good scoring model for evaluating the similarity between two CDS in the presence of FS translations should then penalize not only the initiation of FS but also the length of FS translations extension (amino acids in gray characters in the alignments). The alignment of Seq1 with Seq2 would then have a higher similarity score than the alignment of Seq1 with Seq3 .

Preliminaries: score of CDS alignment

In this section, we formally describe a new definition of the score of a CDS alignment that penalizes both the initiation and the extension of FS translations.

Definiția 1

[Coding DNA sequence (CDS)] A coding DNA sequence (CDS) is a DNA sequence on the alphabet of nucleotides (Sigma _N=) whose length n is a multiple of 3. A coding sequence is composed of a concatenation of (frac<3>) codons that are the words of length 3 in the sequence ending at positions 3eu, (1 le i le frac<3>) . The AA translation of a CDS is a protein sequence of length (frac<3>) on the alphabet (Sigma _A) of AA such that each codon of the CDS is translated into an AA symbol in the protein sequence.

Note that, in practice an entire CDS begins with a start codon “ATG” and ends with a stop codon “TAA” , “TAG” or “TGA” .

Definiția 2

(Alignment between DNA sequences) An alignment between two DNA sequences A și B is a pair ((A',B')) where (A') and (B') are two sequences of same length L derived by inserting gap symbols ('-') in A și B, such that (forall i,

1 le i le L) , in the alignment is called a column of the alignment.

Given an alignment ((A',B')) of length L between two CDS A și B, let S be the sequence (A') or (B') . We denote by (S[k

1 le k le l le L) , the substring of S going from position k to position l. (left| ight|) denotes the number of letters in () that are different from the gap symbol ('-') . For example, if (A'= exttt) and (B'= exttt) , (|A'[4

8]| = | exttt| = 3) . A codon of A sau B este grouped in the alignment ((A',B')) if its three nucleotides appear in three consecutive columns of the alignment. For example, the first codon ACC of A is grouped, while the first codon ACT of B is not grouped.

An alignment ((A',B')) of length 48 between two CDS, A (13 codons) and B (14 codons). The number arrays indicate the positions of the consecutive alignment columns. Codons of A și B sunt colored according to the set to which they belong: IM codons in blue color, FSext codons in red color, InDel codons in green color and FSinit codons in black color. MFS nucleotides contained in FSinit codons are underlined

In the following, we give our definition of the score of an alignment ((A',B')) between two CDS A și B. It is based on a partition of the codons of A (resp. B) into four sets depending on the alignment of codons (see Fig. 2 for an illustration):

The set of In-frame Matching codons (IM) contains the codons that are grouped in the alignment and aligned with a codon of the other CDS.

The set of Frameshift extension codons (FSext) contains the codons that are grouped in the alignment and aligned with a concatenation of three nucleotides that overlaps two codons of the other CDS.

The set of Deleted/Inserted codons (InDel) contains the codons that are grouped in the alignment and aligned with a concatenation of 3 gap symbols.

All other codons constitutes Frameshift initiation codons (FSinit) . The set of Matching nucleotides in FSinit codons (MFS) contains all the nucleotides belonging to FSinit codons and aligned with a nucleotide of the other CDS.

The following notations and conventions are used in Definition 3 to denote the different sets of codons and nucleotides in A și B. The set of IM codons in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). The set of FSext codons in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). The set of InDel codons in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). The set of MFS nucleotides in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). In these sets, the codons of A și B are simply identified by the position (column) of their last nucleotide in the alignment. In this case, we always have ( exttt_ = exttt_) as in the example below. The MFS nucleotides are also identified by their positions in the alignment.

In the alignment scoring model described in Definition 3, the substitutions of IM and FSext codons are scored using an AA scoring function (s_) such that aligned codons with silent nucleotide mutations get the same score as identity. A fixed FS extension cost denoted by fs_extend_cost is added for each FSext codon. The insertions/deletions of InDel codons are scored by adding a fixed gap cost denoted by gap_cost for each InDel codon. The alignment of MFS nucleotides are scored independently from each other, using a nucleotide scoring function (s_). The insertions or deletions of nucleotides in FSinit codons are responsible for the initiation of FS translations. They are then scored by adding a fixed FS opening cost denoted by fs_open_cost for each FSinit codon. Note that, by convention, the values of all penalty costs for gap and FS ( gap_cost , fs_open_cost , fs_extend_cost ) are negative. Note also that the scoring scheme assumes that the AA and the nucleotide scoring functions, (s_) and (s_) , are symmetric.

Definition 3

(Score of an alignment) Let ((A',B')) be an alignment of length L between two CDS A și B. The score of the alignment ((A',B')) is defined by:


Title: Pocket arithmetic and Needleman-Wunsch on Cray Research computers

In the interest of providing more efficient computer-based analysis of DNA and protein sequences, Cray Research has developed a high performance implementation of the sequence alignment method of Needleman and Wunsch using the programming technique of pocket arithmetic. The basis for this implementation is the program SEQHDP, which finds locally homologous subsequences of a protein sequence pair and determines the statistical significance of the homology. Pocket arithmetic takes advantage of the 64-bit width of an operand on the Cray Y-MP by packing more than one integer value per word, then performing logical or integer operations on the packed word to yield multiple results per operation. This technique, in combination with the vector processing capabilities of the Cray Y-MP CPU, produces substantially improved performance over the conventionally coded version of the same algorithm. The authors will introduce the programming technique of pocket arithmetic, then describe its implementation in the Needleman-Wunsch sequence comparison function in SEQHDP. Performance results based on actual protein sequence comparisons are presented.


Priveste filmarea: Needleman-Wunsch algorithm (Decembrie 2021).