Untitled
unknown
plain_text
4 years ago
7.7 kB
6
Indexable
import React from 'react'; import classes from '../Lesson.module.scss'; import CodeEditor from '../../../../components/CodeEditor'; const Lesson22 = () => ( <div className={classes.root}> <h1> PROBLEM PRIBLIŽNOG PODUDARANJA </h1> <p className={classes.indent1x}> U prethodnim delovima smo diskutovali o različitim načinima za rešavanje problema tačnog podudaranja. Naivni algoritam za tačno podudaranje, Boyer-Moore algoritam i offline algoritmi koji koriste indeksiranje. Međutim, tačno podudaranje očitavanja sa odgovarajućim delom genoma nije ono što tražimo. </p> <p className={classes.indent1x} /> <p className={classes.indent1x}> Sekvencionirana očitavanja ne moraju da se tačno podudaraju sa referentim genomom. Postoje određeni razlozi zbog kojih možemo očekivati razlike između očitavanja i referentnog genoma i oni su: </p> <p className={classes.indent2x}> 1. Greške pri sekvencioniranju očitavanja o kojima smo pričali u prvom delu; </p> <p className={classes.indent2x}> 2. Referentni genom ne mora biti u potpunosti isti kao genom koji sekvencioniramo, na primer, genom dva različita čoveka koji nisu u srodstvu je 99,8% isti, što znači da će se povremeno dešavati da imamo različite baze na istim pozicijama tih genoma. </p> <p className={classes.indent1x}> Za rešavanje ovog problema biće nam potrebni algoritmi za približno podudaranje očitavanja sa genomom. </p> <h2 className={classes.indent1x}>Algoritmi za približno podudaranje</h2> <p className={classes.indent1x}> U ovim algoritmima dopuštamo postojanje razlika između teksta i šablona. Razlike koje dopuštamo su sledeće: </p> <p className={classes.indent2x}>1. Nepodudaranje određenog broja karaktera.</p> <p className={classes.indent2x}>PRIMER</p> <img alt="" src="/assets/lesson22/pic1.svg" className={classes.indent3x} /> <p className={classes.indent2x}>2. Umetanje određenog broja karaktera.</p> <p className={classes.indent2x}>PRIMER</p> <img alt="" src="/assets/lesson22/pic2.svg" className={classes.indent3x} /> <p className={classes.indent3x}> Umetanje karaktera u šablon P u odnosu na tekst T je ekvivalento brisanju karaketera iz teksta T u odnosu na šablon P: </p> <img alt="" src="/assets/lesson22/pic3.svg" className={classes.indent4x} /> <p className={classes.indent2x}>3. Brisanje određenog broja karaktera.</p> <p className={classes.indent2x}>PRIMER</p> <img alt="" src="/assets/lesson22/pic4.svg" className={classes.indent3x} /> <p className={classes.indent3x}> Brisanje karaktera iz šablona P u odnosu na tekst T je ekvivalento umetanju karaketera u tekst T u odnosu na šablon P: </p> <img alt="" src="/assets/lesson22/pic5.svg" className={classes.indent4x} /> <p className={classes.indent1x}> Određivanje broja tih razlika, odnosno broja razlika između šablona P i odgovarajućeg dela teksta T, radićemo pomoću sledećih rastojanja: </p> <p className={classes.indent1x}> <b>Hamingovo rastojanje</b> </p> <p className={classes.indent2x}>Neka su X i Y dve niske iste dužine.</p> <p className={classes.indent2x}> hamingovoRastojanje(X,Y) = minimalni broj substitucija pomoću kojih od jedne niske dobijamo drugu nisku. </p> <p className={classes.indent2x}>PRIMER</p> <img alt="" src="/assets/lesson22/pic6.svg" className={classes.indent3x} /> <p className={classes.indent1x}> <b>Edit rastojanje</b> </p> <p className={classes.indent2x}> editRastojanje(X,Y) = minimalni broj promena (brisanje/umetanje, substitucija) pomoću kojih od jedne niske dobijamo drugu nisku. </p> <p className={classes.indent2x}>PRIMER</p> <img alt="" src="/assets/lesson22/pic7.svg" className={classes.indent3x} /> <p className={classes.indent3x}>Na prvi pogled možemo zapaziti sledeću substituciju:</p> <img alt="" src="/assets/lesson22/pic8.svg" className={classes.indent4x} /> <p className={classes.indent3x}> Daljom analizom ove dve niske možemo uočiti da u niski X (koji ima jedan element više od Y) imamo jedno A više nego što to imamo u niski Y, što nas dovodi do zaključka da treba izvršiti umetanje karaktera A u nisku Y ili brisanje karaktera A iz niske X. </p> <img alt="" src="/assets/lesson22/pic9.svg" className={classes.indent4x} /> <p className={classes.indent3x}>editRastojanje(X, Y) = 2</p> <p className={classes.indent2x}>PRIMER</p> <img alt="" src="/assets/lesson22/pic10.svg" className={classes.indent3x} /> <p className={classes.indent3x}> Posmatrajući samo substitucije deluje nam da je edit rastojanje između ove dve niske veliko. Međutim, kada uočimo sledeća umetanja/brisanja karaktera vidimo da će ono biti 2: </p> <img alt="" src="/assets/lesson22/pic11.svg" className={classes.indent4x} /> <p className={classes.indent3x}>editRastojanje(X, Y) = 2</p> <p className={classes.indent1x}> U ovom delu se fokusiramo na <b>Hamingovo rastojanje.</b> </p> <p className={classes.indent1x} /> <p className={classes.indent1x}> Modifikovaćemo naivni algoritam tačnog podudaranja tako da će dopuštati određen broj razlika, odnosno tražićemo pojavljivanja šablona P u tekstu T tako da njihovo Hamingovo rastojanje nije veće od unapred zadatog broja koji je veći od nula (kod algoritama tačnog podudaranja on je nula). </p> <p className={classes.indent1x} /> <p className={classes.indent1x}>Implementacija naivnog algoritma za tačno podudaranje:</p> <CodeEditor code={` def naivni(p, t): pojavljivanja = [] for i in range(len(t) - len(p) + 1): nadjen = True for j in range(len(p)): if t[i+j] != p[j]: nadjen = False break if nadjen: pojavljivanja.append(i) return pojavljivanja `} customClass={classes.indent2x} /> <p className={classes.indent1x}> U njegovoj modifikaciji, kada naiđemo na prvo nepodudaranje karaktera šablona sa karakterom iz teksta ne izlazimo iz unutrašnje while petlje, nego izlazimo iz nje tek kada broj nepodudaranja pređe unapred određeno Hamingovo rastojanje (u ovom slučaju to će biti smešteno u promenljivoj maxRastojanje): </p> <CodeEditor code={` def naivniHaming(p, t, maxRastojanje): pojavljivanja = [] for i in range(len(t) - len(p) + 1): brojNepodudaranja = 0 for j in range(len(p)): if t[i+j] != p[j]: brojNepodudaranja += 1 if brojNepodudaranja > maxRastojanje: break if brojNepodudaranja <= maxRastojanje: pojavljivanja.append(i) return pojavljivanja `} customClass={classes.indent2x} /> <p className={classes.indent1x}> Lako možemo modifikovati naivni algoritam tačnog podudaranja u algoritam približnog podudaranja, dok je sa Boyer-Moore algoritmom to teže uraditi. Kako smo već detaljno radili algoritme tačnog podudaranja, sledeće što ćemo raditi jesu univerzalne metode koje nam omogućavaju modifikaciju tih algoritama u algoritme približnog podudaranja. </p> </div> ); export default Lesson22;
Editor is loading...