Нидлман–Вуншов алгоритам: Разлика помеѓу преработките

[проверена преработка][проверена преработка]
Избришана содржина Додадена содржина
с →‎Матрица на сличност: Јазично подобрување, replaced: фреквенција → честота
с Јазична исправка, replaced: секвенци → низи (11), Секвенци → Низи (2)
Ред 1:
{{Инфокутија Алгоритам|name=<!-- Defaults to article name -->|class=[[Порамнување на секвенцинизи]]|image=|caption=|data=|time=<math>O(mn)</math>|best-time=|average-time=|space=<math>O(mn)</math>}}'''Нидлман–Вуншовиот алгоритам''' е [[алгоритам]] кој се користи во [[биоинформатика]]та за [[Порамнување на секвенцинизи|порамнување]] на [[Нуклеотидна низа|нуклеотидни]] или [[Белковина|белковински]] секвенцинизи. Овој алгоритам претставувал една од првите апликации на [[Динамичко програмирање|динамичкото програмирање]] за споредување на биолошките секвенцинизи. Тој бил развиен од Саул Б. Нидлман и Кристијан Д. Вунш и објавен во 1970 година.<ref name="Needleman">{{Наведено списание|last=Needleman, Saul B.|last2=Wunsch, Christian D.|last-author-amp=yes|year=1970|title=A general method applicable to the search for similarities in the amino acid sequence of two proteins|url=http://linkinghub.elsevier.com/retrieve/pii/0022-2836(70)90057-4|journal=Journal of Molecular Biology|volume=48|issue=3|pages=443–53|doi=10.1016/0022-2836(70)90057-4|pmid=5420325}}</ref> Во суштина алгоритмот го дели поголемиот проблем (на пр. целосната секвенца) на серија помали проблеми, а потоа ги користи решенијата на помалите проблеми за реконструкција на решението на поголемиот проблем.<ref>{{Наведена мрежна страница|url=http://www.britannica.com/EBchecked/topic/1334661/bioinformatics/285871/Goals-of-bioinformatics#ref1115380|title=bioinformatics|accessdate=10 September 2014}}</ref> Алгоритмот, исто така, е познат како алгоритам на оптимално совпаѓање, или како техника на [[глобално порамнување]]. Тој сѐ уште е широко применуван за оптимално глобално порамнување на секвенцинизи, особено кога квалитетот на глобалното порамнување е од најголема важност.
[[Податотека:Needleman-Wunsch_pairwise_sequence_alignment.png|десно|рамка|Слика 1: Нидлман-Вуншов алгоритам за порамнување во парови<pre>
Резултати:
 
СеквенциНизи Најдобри порамнувања
--------- ----------------------
GCATGCU GCATG-CU GCA-TGCU GCAT-GCU
Ред 37:
</pre>]]
== Вовед ==
Овој алгоритам може да се користи за кои било две низи. Следниот водич ќе користи две мали [[Нуклеотидна низа|ДНК секвенцинизи]] како примери, прикажани во дијаграмот:
GCATGCU
GATTACA
Ред 469:
|4
|}
Статистички се конструирани различни матрици за бодување, кои даваат тежина на различни активности соодветни за одредено сценарио. Ова е особено важно кај порамнувањето на белковинските секвенцинизи поради различната честота на различните аминокиселини. Постојат две поголеми семејства на матрици за бодување, од кои секоја претрпува дополнителни измени за прилагодување кон специфични сценарија:
 
* [[PAM]]
Ред 475:
 
=== Казнени бодови за празнина ===
При порамнувањето на секвенцинизи, често се јавуваат празнини (т.е. индели), кои понекогаш можат да бидат доста големи. Од биолошка гледна точка, поголема е веројатноста да една поголема празнина се јави како резултат на една голема бришењето, а не како резултат на повеќе мали бришења. Затоа, два мали индела треба да имаат полош бод од еден голем индел. Наједноставниот и најчестиот начин да се направи ова е преку голем бод за нов индел и помал бод за продолжување на празнина за секоја буква која го продолжува инделот. На пример, нов индел може да чини -5 бода, а продолжување на индел може да чини -1 бод. На овој начин порамнувањето, како што е:
GAAAAAAT
G--A-A-T
Ред 524:
: = -3 + 7 + 10 - (3 × 5) + 7 + (-4) + 0 + (-1) + 0 = 1
 
За да се најде порамнувањето со највисок бод, се распределува дво-димензионална низа (или [[Матрица (математика)|матрица]]) ''F''. Записот во ред ''i'' и колона ''j'' е означен со <math>F_{ij}</math>. Постои еден ред за секој карактер на секвенцата ''A'', и една колона за секој карактер на секвенцата ''B''. На овој начин, ако се порамнуваат секвенцинизи со големини ''n'' и ''m'', количината на меморија која се користи е во <math>O(nm)</math>. [[Хиршбергов алгоритам|Хиршберговиот алгоритам]] содржи само подмножество на низата во меморија и користи <math>\Theta(\min \{n,m\})</math>простор, а во секој друг поглед е сличен на Нидлман-Вуншовиот алгоритам (и исто така бара <math>O(nm)</math>време).
 
Како што алгоритмот напредува, <math>F_{ij}</math> ќе биде назначен да биде оптималниот бод за порамнувањето на првите <math>i=0,\dotsc,n</math> карактери во ''A'' и првите <math>j=0,\dotsc,m</math> карактери во ''B''. Потоа се применува принципот на оптималност на следниов начин:
Ред 580:
 
== Комплексност ==
Пресметувањето на бодот <math>F_{ij}</math>за секоја ќелија во табелата е <math>O(1)</math> операција, па затоа на временската комплексност на алгоритмот за две секвенцинизи со должина <math>n</math> и <math>m</math> е <math>O(mn)</math>.<ref name=":0">{{Наведена книга|title=Algorithms in bioinformatics : a practical introduction|last=Wing-Kin.|first=Sung|date=2010|publisher=Chapman & Hall/CRC Press|isbn=9781420070330|location=Boca Raton|pages=34–35|oclc=429634761}}</ref> Било покажано дека е можно да се подобри времето на извршување на <math>O(mn/ \log n)</math>со употреба на т.н. Метод на Четирите Руси.<ref name=":0" /><ref>{{Наведено списание|last=Masek|first=William|last2=Paterson|first2=Michael|date=February 1980|title=A faster algorithm computing string edit distances|url=https://www.sciencedirect.com/science/article/pii/0022000080900021|journal=Journal of Computer and System Sciences|volume=20|pages=18–31|doi=10.1016/0022-0000(80)90002-1|via=Elsevier Science Direct}}</ref> Бидејќи алгоритмот пополнува <math>n \times m</math> табела, просторната комплексност е <math>O(mn)</math>.<ref name=":0" />
 
== Поврзано ==
 
* [[Смит–Вотерманов алгоритам]]
* [[СеквенцијалнаНизијална анализа на податоци]]
* [[Левенштајново растојание]]
* [[Динамичко временско свиткување]]
* [[Порамнување на секвенцинизи]]
 
== Наводи ==