Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
15 kB
2
Indexable
Never
import React from 'react';
import classes from '../Lesson.module.scss';
import CodeEditor from '../../../../components/CodeEditor';

const Lesson21 = () => (
  <div className={classes.root}>
    <h1>PROBLEM TAČNOG PODUDARANJA</h1>
    <p className={classes.indent1x}>
      U ovom problemu tražimo sve pozicije na kojima šablon P počinje u tekstu T. Šablon P je kao
      igla, a tekst T kao plast sena u kojem tražimo tu iglu.
    </p>
    <p className={classes.indent1x}>Posmatrajmo sledeći primer:</p>
    <img alt="" src="/assets/lesson21/pic1.svg" className={classes.indent2x} />
    <p className={classes.indent2x}>
      U ovom primeru imamo šablon P koji je engleska reč word i imamo tekst T u kojem se šablon P
      pojavljuje jednom i to pred sam kraj, počevši na poziciji 40.
    </p>
    <p className={classes.indent2x}>
      Ovo je pojednostavljena verzija problema poravnjanja očitavanja, ali je sjajno mesto za
      početak njegove analize.
    </p>
    <h2 className={classes.indent1x}>Naivna implementacija algoritma za tačno podudaranje</h2>
    <p className={classes.indent1x}>
      Kako bismo definisali algoritam za dati problem, prvo moramo da precizno definišemo problem:
    </p>
    <p className={classes.indent1x}>PROBLEM TAČNOG PODUDARANJA</p>
    <p className={classes.indent2x}>
      ulaz: niska P koji predstavlja šablon, niska T koji predstavlja tekst
    </p>
    <p className={classes.indent2x}>izlaz: sve pozicije u tekstu T gde počinje šablon P</p>
    <p className={classes.indent1x}>
      Prvo ćemo pokušati da rešimo dati problem na što jednostavniji način. Posmatrajmo opet isti
      primer kao na početku. Probaćemo sva moguća poravnanja šablona P sa tekstom T, odnosno za
      svaku poziciju ćemo proveriti da li dati šablon P počinje na njoj:
    </p>
    <img alt="" src="/assets/lesson21/pic2.svg" className={classes.indent2x} />
    <p className={classes.indent1x}>
      Implementacija u Python-u naivnog algoritam koji funkioniše na ovaj način će biti sledeća:
    </p>
    <CodeEditor
      code={`
      def naivni(p, t):
        # sadrži sve pozicije gde počinje poklapanje šablona p sa delom teksta t
        pojavljivanja = []
        # petlja koja prolazi sva poravnanja                   
        for i in range(len(t) - len(p) + 1):
            nadjen = True
            # petlja koja prolazi karaktere šablona p
            for j in range(len(p)):
                if t[i+j] != p[j]:
                    # neslaganje karaktera, odbacujemo ovo poravnanje                                   
                    nadjen = False
                    break
            if nadjen:
                pojavljivanja.append(i)`}
      customClass={classes.indent2x}
    />
    <p className={classes.indent1x}>
      Pre nego što nastavimo dalje, odgovorićemo na sledeća pitanja:
    </p>
    <p className={classes.indent2x}>
      1. Ako imamo šablon P dužine x i tekst T dužine y, koliko ćemo imati poravnanja?
    </p>
    <img alt="" src="/assets/lesson21/pic3.svg" className={classes.indent3x} />
    <p className={classes.indent3x}>Imaćemo y - x + 1 poravnanja.</p>
    <p className={classes.indent2x}>
      2. Ako imamo šablon P dužine x i tekst T dužine y, koliki je najveći mogući broj poređenja
      karaktera?
    </p>
    <img alt="" src="/assets/lesson21/pic4.svg" className={classes.indent3x} />
    <p className={classes.indent3x}>
      Najveći mogući broj poređenja karaktera će biti x(y- x + 1), tj. to će biti ona situacija u
      kojoj će se šablon poklapati sa svakim poravnanjem koje postoji, na primer:
    </p>
    <img alt="" src="/assets/lesson21/pic5.svg" className={classes.indent4x} />
    <p className={classes.indent4x}>
      U ovom primeru moraćemo da prođemo kroz proveru svih poravnanja i svako poravnanje će
      rezultirati uspehom.
    </p>
    <p className={classes.indent2x}>
      3. Ako imamo šablon P dužine x i tekst T dužine y, koliki je najmanji mogući broj poređenja
      karaktera?
    </p>
    <img alt="" src="/assets/lesson21/pic6.svg" className={classes.indent3x} />
    <p className={classes.indent3x}>
      Najmanji mogući broj poređenja karaktera će biti y- x + 1, tj. to će biti ona situacija u
      kojoj ćemo odmah na početku svakog poravnanja doći do neslaganja karaktera, na primer:
    </p>
    <img alt="" src="/assets/lesson21/pic7.svg" className={classes.indent3x} />
    <p className={classes.indent1x}>Vratimo se na primer sa početka:</p>
    <img alt="" src="/assets/lesson21/pic8.svg" className={classes.indent2x} />
    <p className={classes.indent2x}>
      Ono što nas zanima jeste koliko smo ovde poređenja karaktera imali?
    </p>
    <img alt="" src="/assets/lesson21/pic9.svg" className={classes.indent3x} />
    <p className={classes.indent3x}>
      Imali smo ukupno 40 neslaganja i 6 slaganja, odnosno 46 poređenja karaktera.
    </p>
    <pre className={classes.indent3x}>
      {`Kako je x = |P| = 4
               y = |T| = 44`}
    </pre>
    <p className={classes.indent3x}>
      U najboljem slučaju to bi bilo 44 - 4 + 1 = 41, a u najgorem 4*(44 - 4 + 1) = 164 poređenja
      karaktera. Samim tim, rezultat broja poređenja karaktera je mnogo bliži najboljem slučaju,
      nego što je najgorem. Ovo važi za ovaj primer, ali se ispostavlja da to nije samo za njega
      tako, nego i za mnoge druge primere u praksi.
    </p>
    <h2>Primena naivnog algoritma</h2>
    <p className={classes.indent1x}>
      Genom nad kojim ćemo testirati naivni algoritam biće genom od phi X organizma.
    </p>
    <p className={classes.indent1x}>Njega preuzimamo pomoću komande:</p>
    <CodeEditor
      code={`
      !wget http://d28rh4a8wq0iu5.cloudfront.net/ads1/data/phix.fa`}
      customClass={classes.indent2x}
    />
    <CodeEditor
      code={`
    def procitajGenom(imeDatoteke):
        genom = ''
        with open(imeDatoteke,'r') as f:
            for line in f:
                if not line[0] == '>':
                    genom += line.rstrip()
        return genom
    genom = procitajGenom('phix.fa')
    genom`}
      result={`
      GAGTTTTATCGCTTCCATGACGCAGAAGTTAACACTTTCGGATATTTCTGATGAGTCGAAAAAT
      TATCTTGATAAAGCAGGAATTACTACTGCTTGTTTACGAATTAAATCGAAGTGGACTGCTGGCG
      GAAAATGAGAAAATTCGACCTATCCTTGCGCAGCTCGAGAAGCTCTTACTTTGCGACCTTTCGC
      CATCAACTAACGATTCTGTCAAAAACTGACGCGTTGGATGAGGAGAAGTGGCTTAATATGCTTG
      GCACGTTCGTCAAGGACTGGTTTAGATATGAGTCACATTTTGTTCATGGTAGAGATTCTCTTGT
      TGACATTTTAAAAGAGCGTGGATTACTATCTGAGTCCGATGCTGTTCAACCACTAATAGGTAAG
      AAATCATGAGTCAAGTTACTGAACAATCCGTACGTTTCCAGACCGCTTTGGCCTCTATTAAGCT
      CATTCAGGCTTCTGCCGTTTTGGATTTAACCGAAGATGATTTCGATTTTCTGACGAGTAACAAA
      GTTTGGATTGCTACTGACCGCTCTCGTGCTCGTCGCTGCGTTGAGGCTTGCGTTTATGGTACGC
      TGGACTTTGTGGGATACCCTCGCTTTCCTGCTCCTGTTGAGTTTATTGCTGCCGTCATTGCTTA
      TTATGTTCATCCCGTCAACATTCAAACGGCCTGTCTCATCATGGAAGGCGCTGAATTTACGGAA
      AACATTATTAATGGCGTCGAGCGTCCGGTTAAAGCCGCTGAATTGTTCGCGTTTACCTTGCGTG
      TACGCGCAGGAAACACTGACGTTCTTACTGACGCAGAAGAAAACGTGCGTCAAAAATTACGTGC
      `}
      customClass={classes.indent2x}
    />
    <CodeEditor
      code={`
      def naivni(p, t):
        # u sledećem nizu beležimo svaki ofset gde se pojavljuje naš šablon u tekstu
        pojavljivanja = []
        # prolazimo sva poravnanja
        for i in range(len(t) - len(p) + 1):
            # promenljiva nadjen će biti True ako smo pronašli traženi šablon u tekstu
            nadjen = True
            # prolazimo karaktere šablona
            for j in range(len(p)):
                # čim dođemo do prvog neslaganja šablona sa delom teksta koji posmatramo, izlazimo iz unutrašnje for petlje
                if t[i+j] != p[j]:
                    nadjen = False
                    break
            if nadjen:
                pojavljivanja.append(i)
        return pojavljivanja`}
      customClass={classes.indent2x}
    />
    <p className={classes.indent1x}>Testirajmo ovu funkciju na sledećem, jednostavnom primeru:</p>
    <CodeEditor
      code={`
        t = 'AGCTTAGATAGC'
        p = 'AG'
        naivni(p, t)`}
      result={`
        [0, 5, 9]`}
      customClass={classes.indent2x}
    />
    <CodeEditor
      code={`
        t[5:7]`}
      result={`
        AG`}
      customClass={classes.indent2x}
    />
    <h2 className={classes.indent1x}>Podudaranja sa veštački napravljenim očitavanjima</h2>
    <p className={classes.indent1x}>Sledeća funkcija generiše nasumična očitavanja.</p>
    <CodeEditor
      code={`
      import random
      def generisiOcitavanja(genom, brojOcitavanja, duzinaOcitavanja):
        ocitavanja = []
        for _ in range(brojOcitavanja):
          start = random.randint(0, len(genom) - duzinaOcitavanja) - 1
          ocitavanja.append(genom[start : start + duzinaOcitavanja])
        return ocitavanja`}
      customClass={classes.indent2x}
    />
    <p className={classes.indent1x}>
      Primenjujemo naivni algoritam nad veštački napravljenim očitavanjima:
    </p>
    <CodeEditor
      code={`
    #kontruišemo 100 očitavanja dužine 100
    ocitavanja = generisiOcitavanja(genom, 100, 100)
    #brojimo koliko se očitavanja poklapa sa nekim delom genoma
    brojPodudaranja = 0
    for o in ocitavanja:
        podudaranja = naivni(o, genom)
        # ako je njegova dužina nula, onda nemamo podudaranje, inače imamo
        if len(podudaranja) > 0:
            brojPodudaranja += 1
    print('%d / %d ocitavanja se poklapa!' % (brojPodudaranja, len(ocitavanja)))`}
      result={`
    100 / 100 ocitavanja se poklapa!`}
      customClass={classes.indent2x}
    />
    <h2 className={classes.indent1x}>Podudaranja sa realnim sekvencionim očitavanjima</h2>
    <p className={classes.indent1x}>
      Sada ćemo koristiti realna sekvenciona očitavanja. Preuzimamo ih na sledeći način:
    </p>
    <CodeEditor
      code={`
      !wget http://d28rh4a8wq0iu5.cloudfront.net/ads1/data/ERR266411_1.first1000.fastq`}
      customClass={classes.indent2x}
    />
    <p className={classes.indent1x}>
      Za čitanje ove datoteke koristimo funkciju koju smo radili u prethodnom delu.
    </p>
    <CodeEditor
      code={`
    def procitajFASTQ(imeDatoteke):
        sekvence = [] 
        with open(imeDatoteke) as f:
            while True:
                f.readline() 
                sekv = f.readline().rstrip() 
                f.readline() 
                f.readline() #ovde preskačemo i kvalitet baza
                if len(sekv) == 0: 
                    break
                sekvence.append(sekv)   
        return sekvence
    phix_ocitavanja= procitajFASTQ('ERR266411_1.first1000.fastq')`}
      customClass={classes.indent2x}
    />
    <p className={classes.indent1x}>Posmatramo odnos između baza u datim očitavanjima:</p>
    <CodeEditor
      code={`
      import collections
      count = collections.Counter()
      for ocitavanje in phix_ocitavanja:
          count.update(ocitavanje)
      count`}
      result={`
      Counter({'A': 28426, 'C': 21890, 'G': 19147, 'N': 6, 'T': 30531})`}
      customClass={classes.indent2x}
    />
    <p className={classes.indent1x}>
      Posmatramo koliko imamo poklapanja ovih očitavanja sa delovima referentnog genoma.
    </p>
    <CodeEditor
      code={`
    brojPodudaranja = 0
    n = 0
    for ocitavanje in phix_ocitavanja:
        podudaranja = naivni(ocitavanje, genom)
        n += 1
        if len(podudaranja) > 0:
            brojPodudaranja += 1
    print('%d / %d ocitavanja se poklapa!' % (brojPodudaranja, n))`}
      result={`
      7 / 1000 ocitavanja se poklapa!`}
      customClass={classes.indent2x}
    />
    <p className={classes.indent1x}>
      Ovo je iznenađujuće jer su ovo baš očitavanja koja su uzeta iz ovog genoma. Razlozi toga mogu
      biti sledeći:
    </p>
    <p className={classes.indent2x}>- Greške sekvencione mašine pri čitanju azotnih baza</p>
    <p className={classes.indent2x}>
      - Razlike između referentnog genoma i genoma kojeg želimo da sekvencioniramo.
    </p>
    <p className={classes.indent1x}>
      U našem slučaju verovatno je ovakav rezultat zbog grešaka sekvencione mašine. Zato ćemo umesto
      celih očitavanja (100 nukleotida) gledati samo prvih 30 nukleotida (jer ove greške su češće
      pri kraju očitavanja, stoga gledanjem prvog dela očitavanja izbegavamo te greške).
    </p>
    <CodeEditor
      code={`
      brojPodudaranja = 0
      n = 0
      for ocitavanje in phix_ocitavanja:
        ocitavanje = ocitavanje[:30]
        podudaranja = naivni(ocitavanje, genom)
        n += 1
        if len(podudaranja) > 0:
          brojPodudaranja += 1
      print('%d / %d ocitavanja se poklapa!' % (brojPodudaranja, n))`}
      result={`
      459 / 1000 ocitavanja se poklapa!`}
      customClass={classes.indent2x}
    />
    <p className={classes.indent1x}>
      Još uvek broj poklapanja nije zadovoljavajući. Kao razlog toga može biti to što je genom
      dvolančani i očitavanja mogu doći sa bilo kog lanca. Mi smo ovde postavili kao da su sva
      očitavanja sa istog lanca, što ne mora biti slučaj.
    </p>
    <p className={classes.indent1x}>
      Ovaj problem rešavamo tako što ćemo osim poređenja očitavanja, porediti i njegov inverzni
      komplement sa genomom. To će obuhvatiti slučaj u kome je očitavanje došlo sa drugog lanca
      genoma.
    </p>
    <CodeEditor
      code={`
    def obrnutiKomplement(s):
        komplement = {'A':'T', 'C':'G', 'G':'C', 'T':'A', 'N':'N'}
        t = ''
        for i in range(len(s)):
            t = komplement[s[i]] + t
        return t`}
      customClass={classes.indent2x}
    />
    <CodeEditor
      code={`
      brojPodudaranja = 0
      n = 0
      for ocitavanje in phix_ocitavanja:
        ocitavanje = ocitavanje[:30]
        podudaranja = naivni(ocitavanje, genom)
        podudaranja.extend(naivni(obrnutiKomplement(ocitavanje), genom))
      
        n += 1
        if len(podudaranja) > 0:
          brojPodudaranja += 1
      print('%d / %d ocitavanja se poklapa!' % (brojPodudaranja, n))`}
      result={`
        932 / 1000 ocitavanja se poklapa!`}
      customClass={classes.indent2x}
    />
    <p className={classes.indent2x}>
      Imamo 932 poklapanja od 1000. Još uvek nije 100%, ali to je i očekivano zbog grešaka koje se
      dešavaju. Kada smo uzeli prvi deo očitavanja i uključili i njihove inverze komplmente rezultat
      očitavanja koja se poklapaju se drastično povećao. Mada, sama činjenica da smo uzimali prvih
      30 od 100 nukleotida svakog očitavanja nam govori da ovo i nije ono što želimo da radimo jer
      želimo da dozvolimo razlike koje postoje između različitih jedinki. Zato ćemo posle algoritama
      tačnog podudaranja razmatrati algoritme za približno podudaranje.
    </p>
  </div>
);

export default Lesson21;