Lineaarse pilutrahvi kulud on otseselt proportsionaalsed lõhe pikkusega: lõhe maksab 1 ühik järjestikuse puuduva aluse kohta.
Lihtsaim juhtum on iga üksuse määramine (= iga puuduv alus) trahv 1:

g (k) = k

Või üldisemalt, kui soovite trahvi aluse kohta suurendada 2, 3 või n:

g (k) = n * k
k = tühimiku pikkus ja n = ühe puuduva aluse maksumus

Affine gap trahv maksab järgmiselt - nagu nimeski mugavalt öeldud - affine funktsioon.
Selle idee seisneb selles, et joonduse mis tahes lüngad maksavad kaks komponenti:

• "tühimiku avamise" trahv : see on kulu, mida makstakse ainult ühe lõhe kohta, põhimõtteliselt ainult olemasoleva eest.
• karistus "tühimiku pikendamine": mis võrdub lineaarse vahekorra karistusega, see maksab 1 ühiku iga järjestikuse puuduva baasi kohta.

Kulude üldvalem on siis:

g (k) = a + n * k
koos = avamiskaristusega, n = pikendustrahv, k = tühiku pikkus

Võrreldes lineaarse vahekorra trahviga annab see väikese boonuse pikematele järjestikustele lünkadele, võrreldes ühe nukleotiidi vahele jätmisega, ühe sobitamisega, uuesti vahele jätmisega jne (kuna pikemate vahede korral maksate avatrahvi ainult ühe korra) , nii et üldine baasi hind väheneb).

Teie diagrammil olevad lahtrid:
minu arusaamist mööda töötate afiinse trahviga g (k) = 1 + 1 * k. [3,4] puhul olete "tulemas" vasakul olevast punktist 2 (lahter 1,2). Kumbki:

• sobitage A (rida 1) G-ga (veerg 3) ja saate asendamise eest karistuse 1 -> eelmiste 2 kokku + uus 1 = 3
• avage vahe G vahele jätmiseks (veerg 3) ja saate trahvi 2 (1 avamise eest + 1, kuna vahe pikkus on 1) -> eelmiste 2 + uus 2 = 4. kokku

Nii et valite väiksema karistuse ja lähete 3-ga, mis on suuremas kastis valitud number.
Selgitus on täpselt sama teise mainitud lahtri kohta.

Valem, mida teie slaidis näidatakse, kirjeldab dünaamilist programmeerimist üldise tühimaksumusega. Optimaalse lahenduse leidmine võtab aega $ O (n ^ 3) $. Keegi ei kasuta algoritmi tänapäeval. See on esimene kord, kui näen ma proovida selle algoritmiga maatriksit täita. See on huvitav, kuid ma pole kindel, kuidas see töötab. Ehkki affiinide vahe maksumus on üldise lõhe maksumuse erijuhtum, on parima skoori leidmise algoritm väga erinev, samuti aja keerukus. Kaasaegsete afiinse lõhe koostiste korral on igal lahtril kolm väärtust:

1. optimaalne üldskoor (või optimaalne skoor, kui see lahter on vaste, mis annab samaväärse, kuid erineva formulatsiooni)
2. Optimaalne skoor, kui lahter lõpeb kustutamisega
3. Optimaalne skoor, kui lahter lõpeb sisestusega

Iga lahtri väärtused sõltuvad ainult lahtrist maatriksi üles-, vasak- ja vasakpoolsed lahtrid. Maatriksi täidate ülemisest vasakust nurgast paremasse alaossa. See on $ O (n ^ 2) $ algoritm, kuna läbite iga lahtri üks kord. Lisateabe saamiseks lugege seda märkust. Ma soovitaksin õppida afiinse lõhe maksumust tavalisel viisil.