Gap penalty
Una Gap penalty, o penalització per buit, com podria dir-se en català, és, en Bioinformàtica, una puntuació típicament negativa assignada a un gap, o buit, en un alineament de dues o més seqüències.[1][2]
Per entendre millor d'on prové el concepte, cal conèixer que les seqüències homòlogues, siguin de nucleòtids (ADN o ARN) o de proteïnes, han divergit d’un ancestre comú, i que l’alineament resultant ens mostra les regions conservades i les regions que han passat per esdeveniments evolutius com ara mutacions, insercions, delecions, duplicacions i inversions. Aquestes seqüències acostumen a ser de diferent longitud degut a les insercions i delecions (indels) produïdes des que les seqüències van divergir. Si són d’un o dos nucleòtids poden generar el desplaçament de la pauta de lectura i sovint tenen conseqüències deletèries. En canvi, si tenen lloc en tri-nucleòtids (el que es traduiria en un aminoàcid), el resultat és una extensió o escurçament de la seqüència que pot tenir implicacions en la funció de la proteïna. Quan es duu a terme una alineació entre dues o més seqüències, aquestes indels es refereixen conjuntament com a buits, els quals es representen amb un guió “-”.[3][4][5]
Fonaments
modificaEl nivell de similitud entre dues seqüències es mesura fent servir un mecanisme de puntuació aplicat en l’alineament obtingut. Donat un mecanisme de puntuació, l’objectiu de l’alineament de seqüències és alinear dues seqüències introduïdes de forma que la puntuació final obtinguda sigui òptima. Un mecanisme de puntuació simple té tres paràmetres: una puntuació de coincidència (match score), una penalització de no-coincidència (mismatch score) i una penalització per buit (gap penalty). Per a limitar la introducció de buits en excés, els algorismes d’alineament de seqüències utilitzen gap penalties. D’aquesta manera, cada cop que s’assigna un buit, aquest tindrà una puntuació de penalització que es restarà de la puntuació total de l’alineament. La puntuació total que s’assigna a un alineament serà la suma dels termes per a cada parell alineat de residus, més els termes corresponents a cada buit. Aquesta puntuació correspon al logaritme de la probabilitat relativa que les seqüències introduïdes estiguin relacionades, en comparació a no estar relacionades. Els alineaments òptims són aquells amb una puntuació màxima. Per tant, la introducció de gap penalties té com a objectiu aconseguir el millor aparellament possible del total de les seqüències sense obtenir un alineament poc significatiu.[3][4][5][6]
Mitjançant anàlisis estructurals s’ha pogut mostrar que en seqüències d’importància estructural les insercions i delecions ocorren poc sovint, i que les insercions acostumen a ser de més d’un residu. Aquesta informació pot estar inclosa a l'esquema de puntuació, assignant una penalització més petita als buits d’extensió (gap extension penalty) que la penalització que s’aplicaria en introduir un nou buit (gap opening penalty). D’aquesta manera es penalitzen més els buits d’un sol residu.[4]
El millor alineament serà aquell que resulti amb la màxima puntuació a partir del menor nombre de buits introduïts.[4]
Si el gap penalty s’estableix amb un valor negatiu alt, s’inseriran pocs gaps a l’alineament perquè en incloure’ls el valor màxim d’aparellament baixarà destacablement.[4]
Si el gap penalty que s’escull té un valor negatiu baix, s’introduiran més buits, i de major longitud.[4]
Per tant, si s’estan buscant seqüències que tenen un aparellament més estricte respecte la seqüència de referència, aquest gap penalty serà massa permissiu, de forma que s’haurà d’augmentar el seu valor negatiu. Així, s’obtindran regions de les seqüències estretament relacionades. Si el que es busca són seqüències distantment relacionades, el valor de la penalització ha de ser baix per tal que l’algorisme d’alineament de seqüències pugui introduir més buits d’un o de diversos residus però obtenint una puntuació màxima final igualment òptima.[4]
En alguns algorismes d’alineament de seqüències la puntuació del buit depèn del tipus de residu amb el qual el buit s’alinea. Alguns tipus de residu tenen major predisposició per ser conservats que d’altres perquè les seves cadenes laterals tendeixen a ser més importants en la determinació de l'estructura o funció. Un exemple és el triptòfan, un aminoàcid amb una conservació molt major que l'esperada per atzar. Per tant, alinear un buit amb un triptòfan exigirà una gap penalty major.[4]
A la pràctica, quasi sempre és necessari inserir buits a les seqüències mentre que s’estan alineant. La manera més òbvia de trobar el millor alineament amb buits seria generant tots els possibles alineaments que continguin buits, calcular la puntuació de cadascun i seleccionar l’alineament que resultés amb la puntuació òptima. Aquest exercici requeriria molt de temps. Per tant, només va ser possible incorporar buits als alineaments quan es van desenvolupar algorismes de programació dinàmica en els quals només es pot establir el comportament exacte de l’algorisme quan aquest està duent a terme alineament de seqüències. Aquests eviten l'exploració innecessària d’aquells alineaments no-òptims.[4]
Història
modificaEl primer algorisme que va emprar programació dinàmica per la comparació de seqüències va ser el de Needleman i Wunsch amb l’algorisme d’alineament global, publicat l’any 1970. La seva tècnica encara és el centre de molts mètodes d’alineament i cerca de seqüències en l’actualitat. [4][7]
Amb el propòsit d'avaluar la significància de l’algorisme de Needleman-Wunsch, Dayhoff (1978), la pionera en anàlisis mitjançant matrius de substitució, el va aplicar per un gran nombre de seqüències aleatòries de proteïnes no relacionades. Va emprar una matriu amb un logaritme de probabilitats de 250 PAM i va resultar en puntuacions que seguien una distribució normal.[2][8]
Poc després, el 1981, Smith i Waterman van modificar l’algorisme de Needleman i Wunsch, d’alineament global, per crear-ne un d’alineament local. El seu principi fonamental es basa en el fet que les regions de major significat biològic a les seqüències d’ADN i proteïnes eren subregions que alineaven correctament i que la resta de regions estaven constituïdes per seqüències menys relacionades i, per tant, menys significatives. [2][9]
Pel que respecta als mètodes d'alineament de múltiples seqüències, Gotoh va proposar una millora de l'algorisme de Smith-Waterman el 1982. En aquest tipus d’alineament s’inclouen els conceptes de gap opening penalty i gap extension penalty amb l’objectiu de distingir les gap penalties per un sol residu de les gap penalties per buits de major longitud.[2][10]
Tipus
modificaHi ha cinc tipus principals de gap penalties: constant, lineal, afí, convex i basat en perfils.
En el gràfic es mostra la funció que seguirà cadascun d’ells, depenent del valor inicial de gap penalty establert i del nombre de buits consecutius (determinat a l'eix x). En tres dels quatre tipus representats, el valor absolut del gap penalty (determinat a l'eix y) està directament relacionat amb l’augment de l'extensió del buit. En el cas del tipus constant, el valor de la penalització serà independent a la longitud del buit.
Constant
modifica
Aquest és el tipus de penalització per buit més simple. En aquest cas, s’assigna una puntuació negativa que és independent a la quantitat de buits de residus consecutius que s'introdueixen. Aquest tipus, per tant, en buits de major nombre de residus contigus resultarà en una penalització final de la puntuació total de l’alineament menor.[1]
En l’alineació de dues seqüències curtes d'ADN mostrada a la imatge, amb '-' es representen els buits d'un parell de bases. Si el gap penalty valia -1 punt i els emparellaments +1, la puntuació total equival a: 11 -2 = +9.
Lineal
modificaEn comparació amb la gap penalty constant, la gap penalty lineal té en compte la longitud del buit de cada indel. Per tant, si la penalització per a cada indel és ID i la longitud del buit és L, la penalització total per buit seria el producte dels dos (G = ID * L). Aquest mètode afavoreix buits més curts, amb una puntuació total que disminueix amb cada buit addicional.[11]
En aquest exemple, tenint en compte que la gap penalty equival a -1, la penalització pel total de buits serà: -1 * 4 = -4. D’aquesta manera s'obté una puntuació final que es calcula: 11 -4 = +7.
Afins
modificaLa funció de gap penalty més utilitzada és la de tipus afí. Aquesta combina els components tant de les gap penalty constant com lineal. La seva fórmula serà representada amb nous termes: gap opening penalty (GOP) representarà la penalització per obrir un nou buit i gap extension penalty (GEP) penalitzarà els buits introduïts com a extensió d’un buit prèviament obert, ampliant-los un residu més.[10][12][13][14]
Si l’interès és trobar coincidències estretament relacionades (per exemple, l'eliminació de la seqüència vectorial durant la seqüenciació del genoma), s’hauria d’utilitzar una gap extension penalty més gran per reduir les gap opening. D'altra banda, s'hauria de reduir la gap extension penalty quan estigués interessat a trobar un partit més distant.[13][14]
La relació entre GOP i GEP també té un efecte sobre la mida del buit; si importa controlar-la, s’utilitza una GOP petita i una GEP gran (més costos d’ampliar un buit) i viceversa.[13][14]
La fórmula que representaria el valor del total de les gap penalties es representarà com: G = GOP + (GEP * L).[13][14]
En l'exemple, la puntuació final òptima (aparellaments - gap penalties) que s’obtindria correspondria a: 11 -1 -1 + (-2 * 2) = 11 -6 = +5.
Convex
modificaL’ús de la gap penalty afí requereix l’assignació de valors de penalització fixos tant per obrir com per ampliar un gap. Això pot ser massa rígid per utilitzar-lo en un context biològic. En canvi, el de tipus convex (o log-affine gap cost) té el potencial suficient per dur a terme recerca de seqüències en algoritmes d’alineament, proveint uns alineaments més precisos biològicament.[13][14]
La funció de les gap penalties, en aquesta ocasió, inclou una funció logarítmica que es veu afectada per la variació de l'extensió del buit: G = GOP + (GOP*GEP) * ln L.[13][14]
Aquest nou tipus de gap penalty es va inventar per modificar la gap penalty afí de manera que fossin preferibles els buits més llargs, en contrast amb el tipus afí, que afavoreix els buits més curts. A més, es va demostrar que la distribució de les mides de les indel responen a una funció exponencial.[13][14]
Basat en perfils
modificaEls algoritmes d'alineació perfil-perfil són eines que detecten relacions d'homologia de proteïnes amb una precisió d'alineament millorada.[11]
Els mètodes tradicionals d'alineació de seqüències de proteïnes utilitzen matrius de substitució per mesurar la similitud dels parells d'aminoàcids, mentre que els mètodes d'alineació perfil-perfil requereixen una funció de puntuació basada en el perfil per mesurar la similitud. L'alineació perfil-perfil, de la mateixa manera que els mètodes tradicionals, utilitzen gap penalties al seu sistema de puntuació.[11]
Algunes de les funcions de puntuació s'integren amb informació estructural, com l'estructura secundària, l'accessibilitat del dissolvent, les regions hidròfobes i els perfils estructurals. Amb la integració d'informació estructural, l'alineació perfil-perfil s'ha convertit en un enfocament capaç de reconèixer homòlegs distants i proporcionar alineacions d'alta qualitat per a la predicció d'estructures de proteïnes com un mètode únic.[11]
Les gap penalties basades en perfils adquireixen informació de buits de perfils o alineacions de seqüència múltiple (MSA) generades per la recerca PSI-BLAST. La informació del buit s'usa generalment en forma de perfils de freqüència indel, que és més específica per a les seqüències que s’han d’alinear.[11]
Aplicació en Bioinformàtica
modificaEls algorismes de programació dinàmica, permeten fer un més alineaments de seqüències biològiques. Els alineaments són generats començant als extrems de dues seqüències, intentant aparellar tots els parells de caràcters possibles entre les seqüències, tot assignant una puntuació. La inclusió de buits i de gap penalties és necessària per a poder obtenir el millor alineament possible entre dues seqüències.
Tenint en compte el paper dels gap penalties als mecanismes de puntuació en alineaments de seqüències, les seves aplicacions bioinformàtiques estan relacionades amb: alineaments global, semiglobal o local i matrius de substitucions.
Alineament global
modifica
Article principal: Algorisme de Needleman-Wunsch
Un alineament global realitza un alineament d’extrem a extrem de la seqüència consultada amb la seqüència de referència. És l’alineament més adient per a comparar seqüències homòlogues estretament relacionades, de longitud similar.[4]
Un dels primers i més importants algorismes per a l’alineament global de seqüències de proteïna és l’algorisme de Needleman-Wunsch. Aquest és una tècnica de programació dinàmica emprada per a portar a terme alineaments globals de dues seqüències.[2][4][15][16]
Essencialment, l’algorisme de Needleman-Wunsch divideix el problema en un conjunt de subproblemes, i, seguidament, fa servir els resultats dels subproblemes per a reconstruir la solució de la consulta original. Realitza un alineament global residu per residu, seguint tres passos principals: establir una matriu bidimensional en què es comparen les dues seqüències (sent una seqüència alineada verticalment en l'eix y i l’altra horitzontalment en l'eix x); puntuar cada parell de residus emparellats, i finalment traçar l’alineació en funció de les millors puntuacions.[2][4][15][16]
En aquest mètode, els buits, independentment de la seva llargària, només tenen una possible puntuació de gap penalty associada, donat que no distingeix entre introduir tres buits d’un caràcter de longitud cadascun i introduir un sol buit de tres caràcters de longitud, el qual és poc realista des d’un punt de vista evolutiu.[2][4][15][16]
Alineament local
modificaArticle principal: Algorisme de Smith-Waterman
Un alineament de seqüència local aparella una subsecció contigua d’una seqüència amb la subsecció contigua d’una altra seqüència. Aquest tipus d’alineament és el més adequat per a casos en què només algunes parts d’ambdues seqüències estan relacionades (per exemple, en les proteïnes multi-domini, formades per petits dominis proteics units, com ara les quinases PI3K). També és molt útil quan es consulta una seqüència de consulta d’una proteïna desconeguda en una base de dades de seqüències: un cop es troben seqüències amb regions d’alta similitud dins la base de dades amb l’alineament local, es pot fer servir l’alineament global per alinear la resta de la seqüència que no té tanta similitud. Els alineaments locals acostumen a ser més significatius que els globals, perquè inclouen patrons altament conservats dins les seqüències. A diferència de l’alineament global, els alineaments locals tendeixen a ser més curts i no inclou molts buits.[4]
L’algorisme de Smith-Waterman és àmpliament utilitzat per a fer alineaments locals. És una modificació de l'algorisme de Needleman-Wunsch que permet localitzar les regions més significatives biològicament en seqüències de DNA i proteïna, les quals són subregions que tenen molt bon alineament en comparació a la resta de regions, menys significatives. Les normes per a calcular la matriu de substitucions presenten variacions respecte a les emprades en el mètode de Needleman-Wunsch. En l’algorisme de Smith-Waterman, en addició als tres possibles valors de puntuació (per a match, mismatch i gap penalty) descrits per a Needleman-Wunsch, hi ha un quart valor possible, el zero. Quan el valor de la matriu de puntuació de programació dinàmica esdevé negatiu, aquest valor s’estableix a zero, de forma que es termina qualsevol alineament produït fins a aquest punt. D’aquesta forma, s’evita que la puntuació d’alineació sigui negativa. L’alineament, a diferència de l’algorisme de Needleman-Wunsch, en comptes de començar-se a traçar des de la cel·la inferior dreta de la matriu, es comença a traçar des de la cel·la amb la puntuació més alta.[2][16]
Sovint, l’algorisme que actualment s’anomena de Smith-Waterman es tracta d’una optimització d’aquest algorisme, combinat amb el proposat per Gotoh el 1982, el qual fa servir gap penalties de tipus afí. És l’anomenat algorisme de Smith-Waterman-Gotoh, i és capaç d'avaluar millor els esdeveniments biològics que l’algorisme de Smith-Waterman original.[10][17][18]
Comparació en l’ús de gap penalties en l’alineament global i en l’alineament local
modificaEn l’alineament global, les regions emparellades són llargues i cobreixen la major part de les seqüències, depenent de la presència de molts buits. D’altra banda, l’alineament local tendeix a ser més curt i a no incloure molts buits. La puntuació de les gap penalties contribueix a determinar si l’alineament serà local o global.[2]
Donat que un alineament global emparella la major part de la seqüència, la puntuació de mismatch i de les gap penalties s’estableixen perquè siguin baixes en comparació a les puntuacions de match, el qual permet realitzar alineaments més llargs, ja que d’aquesta forma tenen més pes els aparellaments, i la puntuació és proporcional a la llargada de l’alineament. És a dir, si la matriu de puntuacions dona de mitja una puntuació positiva per a cada posició alineada, i això es combina amb gap penalties prou petites com per poder permetre l'extensió de regions pobrament emparellades, el resultat serà un alineament global.[2]
En canvi, per a un alineament local, s’estableixen puntuacions negatives de mismatch i de gap penalties, per a així poder contrarrestar la puntuació positiva d’un match, La matriu de puntuacions donarà, de mitja, valors negatius per a les posicions emparellades, i el gap penalty serà prou llarg per a evitar que els buits extenguin l’alineament. La puntuació, a diferència dels alineaments globals, no augmenta proporcionalment amb la longitud de la seqüència, donat que la puntuació positiva dels emparellaments és compensada per les puntuacions de mismatch i de les gap penalties.[2]
| Alineament global | Alineament local |
|---|---|
| Gap penalty baixa | Gap penalty alta |
| Permet extensió de l'alineament malgrat que hi hagi regions pobrament emparellades. | Evita l'extensió de l'alineament en regions que no tenen un bon emparellament. |
Alineament semiglobal
modificaL’ús d’un alineament semiglobal existeix per a trobar una coincidència (match) particular dins una seqüència gran. Els buits que es troben a l’inici o al final en qualsevol de les dues seqüències no contribueixen a la puntuació de l’alineament. Es compten els buits a l’interior de l’alineament, però no el dels extrems.[19][20]
Penalitzacions per buits als extrems dels alineaments
modificaSovint es produeixen alineaments de seqüència que als extrems inclouen buits oposats amb caràcters sense emparellar. Aquests buits o bé poden tenir la mateixa puntuació gap penalty que els buits de l’interior de l’alineament o bé poden no rebre cap puntuació de penalització.[2]
Quan es comparen seqüències homòlogues i de longitud similar, és preferible incloure gap penalties per als buits que es troben als extrems de l’alineament. En canvi, per a seqüències d’homologia desconeguda de diferents longituds, és preferible emprar un alineament que no inclou aquestes gap penalties per als extrems.[2]
Matriu de substitucions
modificaLes matrius de substitució defineixen els valors de probabilitat d’un residu sent substituït per un altre en un alineament, donant el valor per a cada possible parell de residus en un alineament de seqüències.[21]
Si es fa servir una gap penalty massa alta en relació amb el rang de puntuacions que trobem en la matriu de substitució, mai apareixeran buits en l’alineació. D’altra banda, si la gap penalty és massa baixa en comparació a les puntuacions de la matriu, apareixeran buits molt sovint al llarg de tot l’alineament. Tanmateix, la majoria de programes d’alineació suggereixen les gap penalties més adients per a cada matriu de puntuacions en la majoria de situacions. Per exemple, en els programes de GCG i FASTA, el format de la matriu de puntuacions inclou valors de puntuació de gap penalties preestablerts.[2]
Complexitat de temps
modificaNeedleman i Wunsch, en el seu mètode de programació dinàmica per l’alineament de seqüències, determinen el temps que trigarà el programa dur a terme tots els possibles alineaments amb un gap penalty constant amb la fórmula O(mn) on m i n són les longituds d’ambdues seqüències. Aquesta mesura del temps es mantindria per l’alineament local de Smith i Waterman i també per l’alineament global de Gotoh, que utilitza gap penalty afí.[14]
Per acabar, en el cas del gap penalty convex la fórmula que indica el temps que trigaria en efectuar-se l’algoritme seria: O(mn lg(m + n)).[14]
Limitacions
modificaÉs difícil determinar de forma precisa quines són les gap penalties més adients per a un parell de seqüències donat. Per aquest motiu, sovint s’empren valors de penalització preestablerts. De totes maneres, l’ús de gap penalties té una sèrie de problemes associats. En primer lloc, els resultats de l’alineament poden variar en funció del valor de gap penalty utilitzat. A més, la significació estadística de la puntuació d’un alineament es basa típicament en models teòrics d’alineaments en què no s’han introduït buits, amb l'error que pot comportar. Finalment, no es pot controlar el nombre de buits que es pot introduir per a un parell donat de seqüències, malgrat que el nombre de buits es conegui per endavant.[22]
Referències
modifica- ↑ 1,0 1,1 ROSALIND [Internet]. [cited 2020 Dec 20]. Available from: Glossary - Gap Penalty
- ↑ 2,00 2,01 2,02 2,03 2,04 2,05 2,06 2,07 2,08 2,09 2,10 2,11 2,12 2,13 Bioinformatics: Sequence and Genome Analysis. Second Edition. By David W Mount. Cold Spring Harbor (New York): Cold Spring Harbor Laboratory Press. 2004;80. Available from: {{format ref}} http://dx.doi.org/10.1086/431054
- ↑ 3,0 3,1 miRNomics: MicroRNA Biology and Computational Analysis. Methods in Molecular Biology. 2014. Available from: {{format ref}} http://dx.doi.org/10.1007/978-1-62703-748-8
- ↑ 4,00 4,01 4,02 4,03 4,04 4,05 4,06 4,07 4,08 4,09 4,10 4,11 4,12 4,13 4,14 Zvelebil MJ, Zvelebil M, Baum JO. Understanding Bioinformatics. Garland Science. 2008;772.
- ↑ 5,0 5,1 Durbin R, Eddy SR, Krogh A, Mitchison G. Biological Sequence Analysis. 1998. Available from: {{format ref}} http://dx.doi.org/10.1017/cbo9780511790492
- ↑ Chao K-M, Zhang L. Sequence Comparison: Theory and Methods. Springer Science & Business Media; 2008.
- ↑ Needleman SB, Wunsch CD. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970 Mar;48(3):443–53.
- ↑ Dayhoff MO, Schwartz RM, Orcutt BC. Matrices for detecting distant relationships. In: Dayhoff MO (ed). Atlas of Protein sequence and Structure. Washington, DC: National Biomedical Research Foundation. 1978;5.
- ↑ Smith TF, Waterman MS. Identification of common molecular subsequences. J Mol Biol. 1981;147(1).
- ↑ 10,0 10,1 10,2 Gotoh O. An improved algorithm for matching biological sequences. Vol. 162, Journal of Molecular Biology. 1982. Available from: {{format ref}} http://dx.doi.org/10.1016/0022-2836(82)90398-9
- ↑ 11,0 11,1 11,2 11,3 11,4 Wang C, Yan R-X, Wang X-F, Si J-N, Zhang Z. Comparison of linear gap penalties and profile-based variable gap penalties in profile–profile alignments. Computational Biology and Chemistry. 2011;35. Available from: {{format ref}} http://dx.doi.org/10.1016/j.compbiolchem.2011.07.006
- ↑ Mullan L. Pairwise sequence alignment - it’s all about us! Briefings in Bioinformatics. 2006;7. Available from: {{format ref}} http://dx.doi.org/10.1093/bib/bbk008
- ↑ 13,0 13,1 13,2 13,3 13,4 13,5 13,6 Cartwright RA. Logarithmic gap costs decrease alignment accuracy. BMC Bioinformatics. 2006;7:527.
- ↑ 14,0 14,1 14,2 14,3 14,4 14,5 14,6 14,7 14,8 Cartwright RA. Ngila: global pairwise alignments with logarithmic and affine gap costs [Internet]. Bioinformatics. 2007;23. Available from: {{format ref}} http://dx.doi.org/10.1093/bioinformatics/btm095
- ↑ 15,0 15,1 15,2 Sangita. Bio-Informatics. Firewall Media. 2006
- ↑ 16,0 16,1 16,2 16,3 Rosenberg MS. Sequence Alignment: Methods, Models, Concepts, and Strategies. Univ of California Press. 2009.
- ↑ Flouri T, Kobert K, Rognes T, Stamatakis A. Are all global alignment algorithms and implementations correct? Available from: {{format ref}} http://dx.doi.org/10.1101/031500
- ↑ Suzuki H, Kasahara M. Introducing difference recurrence relations for faster semi-global alignment of long sequences. BMC Bioinformatics. 2018;19.
- ↑ ROSALIND [Internet]. [cited 2020 Dec 20]. Available from: Glossary - Semiglobal Alignment
- ↑ Jones NC, Pevzner PA, Pevzner P. An Introduction to Bioinformatics Algorithms. MIT Press. 2004.
- ↑ Xiong J. Essential Bioinformatics [Internet]. 2006. Available from: {{format ref}} http://dx.doi.org/10.1017/cbo9780511806087
- ↑ Nozaki Y, Bellgard M. Statistical evaluation and comparison of a pairwise alignment algorithm that a priori assigns the number of gaps rather than employing gap penalties. Bioinformatics. 2005;21(8).
Enllaços externs
modifica- Demostració interactiva de l'algorisme de Needleman-Wunsch [en anglès]: http://experiments.mostafa.io/public/needleman-wunsch/index.html