Нидлман–Вуншов алгоритам: Разлика помеѓу преработките
[проверена преработка] | [проверена преработка] |
Избришана содржина Додадена содржина
с →Матрица на сличност: Јазично подобрување, replaced: фреквенција → честота |
с Јазична исправка, replaced: секвенци → низи (11), Секвенци → Низи (2) |
||
Ред 1:
{{Инфокутија Алгоритам|name=<!-- Defaults to article name -->|class=[[Порамнување на
[[Податотека:Needleman-Wunsch_pairwise_sequence_alignment.png|десно|рамка|Слика 1: Нидлман-Вуншов алгоритам за порамнување во парови<pre>
Резултати:
--------- ----------------------
GCATGCU GCATG-CU GCA-TGCU GCAT-GCU
Ред 37:
</pre>]]
== Вовед ==
Овој алгоритам може да се користи за кои било две низи. Следниот водич ќе користи две мали [[Нуклеотидна низа|ДНК
GCATGCU
GATTACA
Ред 469:
|4
|}
Статистички се конструирани различни матрици за бодување, кои даваат тежина на различни активности соодветни за одредено сценарио. Ова е особено важно кај порамнувањето на белковинските
* [[PAM]]
Ред 475:
=== Казнени бодови за празнина ===
При порамнувањето на
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''. На овој начин, ако се порамнуваат
Како што алгоритмот напредува, <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> операција, па затоа на временската комплексност на алгоритмот за две
== Поврзано ==
* [[Смит–Вотерманов алгоритам]]
* [[
* [[Левенштајново растојание]]
* [[Динамичко временско свиткување]]
* [[Порамнување на
== Наводи ==
|