Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

courses:a4m33pal:uloha4-2011 [2011/11/14 17:01]
hnatuluk vytvořeno
courses:a4m33pal:uloha4-2011 [2025/01/03 18:28] (aktuální)
Řádek 1: Řádek 1:
 http://​cw.felk.cvut.cz/​courses/​a4m33pal/​task.php?​task=geny http://​cw.felk.cvut.cz/​courses/​a4m33pal/​task.php?​task=geny
  
-====== Zadání ​====== +====== Zadání ​Pomozte Craigu Venterovi hledat geny v DNA ======
- +
-===== Pomozte Craigu Venterovi hledat geny v DNA ===== +
  
 V ústavu Všeobecné Pozemské Genomiky, který nedávno založil světoznámý neúnavný průkopnik v biologii Craig Venter, vytvořili nový přístroj, jímž lze bezdotykově během 3 minut přečíst celou DNA libovolné osoby. Přístroj je založen na velmi přesné laserové techologii a využívá kvantové efekty probíhající při kontrakci podkožních svalů. Přístroj, resp. jeho detekční část v podobě malé plastikové pistolky stačí zaměřit na např. na vnitřek dlaně a požádat měřenou osobu, aby během tří minut zlehka pohybovala palcem této ruky. Během snímání posílá detekční část bezdrátově vysokou rychlostí data do připojeného počítače,​ kde pokročilé algoritmy rekonstruují nejvýše do 30 sekund po skončení snímání celou sekvenci DNA.  V ústavu Všeobecné Pozemské Genomiky, který nedávno založil světoznámý neúnavný průkopnik v biologii Craig Venter, vytvořili nový přístroj, jímž lze bezdotykově během 3 minut přečíst celou DNA libovolné osoby. Přístroj je založen na velmi přesné laserové techologii a využívá kvantové efekty probíhající při kontrakci podkožních svalů. Přístroj, resp. jeho detekční část v podobě malé plastikové pistolky stačí zaměřit na např. na vnitřek dlaně a požádat měřenou osobu, aby během tří minut zlehka pohybovala palcem této ruky. Během snímání posílá detekční část bezdrátově vysokou rychlostí data do připojeného počítače,​ kde pokročilé algoritmy rekonstruují nejvýše do 30 sekund po skončení snímání celou sekvenci DNA. 
Řádek 13: Řádek 10:
  
 Abychom výzkumníkům pomohli, máme sestavit program, který na základě přečtené sekvence DNA, znalosti genů S1, S2, ..., SN a čísla MEGSR určí, zda daná osoba má tento soubor genů ve své DNA. Z testovacích důvodů se neomezíme jen na standardní čtyři písmena A, C, T, G označující báze DNA, ale budeme předpokládat libovolnou abecedu, z níž je sestavena DNA i jednotlivé geny. Budeme předpokládat,​ že geny se vždy vyskytují v libovolném pořadí těsně za sebou, mezi sousedními dvěma v dané DNA není žádné další písmeno. Délka každého genu je nejvýše 20 000 znaků, délka DNA (v našem cvičném případě) je nejvýše 1 000 000 znaků, počet genů nepřesáhne 1000. Abychom výzkumníkům pomohli, máme sestavit program, který na základě přečtené sekvence DNA, znalosti genů S1, S2, ..., SN a čísla MEGSR určí, zda daná osoba má tento soubor genů ve své DNA. Z testovacích důvodů se neomezíme jen na standardní čtyři písmena A, C, T, G označující báze DNA, ale budeme předpokládat libovolnou abecedu, z níž je sestavena DNA i jednotlivé geny. Budeme předpokládat,​ že geny se vždy vyskytují v libovolném pořadí těsně za sebou, mezi sousedními dvěma v dané DNA není žádné další písmeno. Délka každého genu je nejvýše 20 000 znaků, délka DNA (v našem cvičném případě) je nejvýše 1 000 000 znaků, počet genů nepřesáhne 1000.
-==== Vstup ==== 
  
 +===== Vstup =====
  
 První řádek vstupu specifikuje použitou abecedu. Abeceda je zadána jako řetězec bez mezer, v němž jsou všechny znaky navzájem různé. Pořadí znaků v abecedě je nepodstatné. Druhý řádek vstupu obsahuje jediný dlouhý řetězec nad danou abecedou představující přečtenou sekvenci DNA. Na třetím řádku je uvedeno jediné číslo N určující počet genů v souboru. Na dalších N řádcích je uveden seznam genů, na každém řádku jeden gen. Gen, podobně jako DNA, je neprázdným řetězcem znaků nad danou abecedou. Geny jsou v souboru genů indexovány od 1 do N v tom pořadí, v jakém byly načteny. Na posledním řádku vstupu je uvedeno jediné nezáporné celé číslo MEGSR, určující maximální celkový počet chybně přečtených znaků DNA v místě, které je obsazeno geny daného souboru. První řádek vstupu specifikuje použitou abecedu. Abeceda je zadána jako řetězec bez mezer, v němž jsou všechny znaky navzájem různé. Pořadí znaků v abecedě je nepodstatné. Druhý řádek vstupu obsahuje jediný dlouhý řetězec nad danou abecedou představující přečtenou sekvenci DNA. Na třetím řádku je uvedeno jediné číslo N určující počet genů v souboru. Na dalších N řádcích je uveden seznam genů, na každém řádku jeden gen. Gen, podobně jako DNA, je neprázdným řetězcem znaků nad danou abecedou. Geny jsou v souboru genů indexovány od 1 do N v tom pořadí, v jakém byly načteny. Na posledním řádku vstupu je uvedeno jediné nezáporné celé číslo MEGSR, určující maximální celkový počet chybně přečtených znaků DNA v místě, které je obsazeno geny daného souboru.
-==== Výstup ==== 
  
 +===== Výstup =====
  
 Na výstupu je seznam možných pozic daného souboru genů v dané DNA. Každý prvek seznamu je uložen na jednom řádku a má následující strukturu. Nechť Sk (1≤k≤N) je první gen daného souboru bráno od počátku DNA, za kterým následují ostatní geny. Nejprve je uvedena pozice prvního znaku genu Sk v DNA. Pozice v DNA jsou číslovány odleva počínaje 1. Za číslem pozice následuje N čísel, určujících pořadí genů v DNA. Nejprve je uveden index k a dále indexy jednotlivých dalších genů v tom pořadí, v jakém se geny vyskytují v DNA. Všechny hodnoty na řádku jsou oddělěny jednou mezerou. ​ Na výstupu je seznam možných pozic daného souboru genů v dané DNA. Každý prvek seznamu je uložen na jednom řádku a má následující strukturu. Nechť Sk (1≤k≤N) je první gen daného souboru bráno od počátku DNA, za kterým následují ostatní geny. Nejprve je uvedena pozice prvního znaku genu Sk v DNA. Pozice v DNA jsou číslovány odleva počínaje 1. Za číslem pozice následuje N čísel, určujících pořadí genů v DNA. Nejprve je uveden index k a dále indexy jednotlivých dalších genů v tom pořadí, v jakém se geny vyskytují v DNA. Všechny hodnoty na řádku jsou oddělěny jednou mezerou. ​
Řádek 29: Řádek 26:
 atd ... atd ...
 Pokud se daný soubor genů v dané DNA i se započtením možných chybných detekcí nemůže vyskytovat, vystoupí jediný řádek obsahující číslo 0. Pokud se daný soubor genů v dané DNA i se započtením možných chybných detekcí nemůže vyskytovat, vystoupí jediný řádek obsahující číslo 0.
-=== Příklad 1 === + 
-== Vstup: ==+==== Příklad 1 ==== 
 +=== Vstup: ​===
   * AbC   * AbC
   * bbbbCAACAAACbbCCAbbAAAb   * bbbbCAACAAACbbCCAbbAAAb
Řádek 39: Řádek 37:
   * 2   * 2
  
-== Výstup: ==+=== Výstup: ​===
  
   * 3 2 3 1   * 3 2 3 1
 +  * 7 3 1 2
   * 8 1 3 2   * 8 1 3 2
   * 10 1 2 3   * 10 1 2 3
   * 11 3 2 1   * 11 3 2 1
-===Příklad 2=== +  * 13 2 3 1 
-== Vstup: ==+ 
 +====Příklad 2==== 
 +=== Vstup: ​===
  
   * 01   * 01
Řádek 54: Řádek 55:
   * 010   * 010
   * 1   * 1
-== Výstup: ==+ 
 +=== Výstup: ​===
  
   * 3 1 2   * 3 1 2
   * 3 2 1   * 3 2 1
  
 +===== Verejna vzorova zadani =====
 +{{:​courses:​a4m33pal:​pal-ukol4-geny-pub.zip}}
  
 +====== Řešení za 10/10 ======
  
-~~DISCUSSION~~+  * vytvorit si tabulku hammingovyc vzdalenosti pro vsechny pozice vsech genu tedy int hamming[N][dna.length] a klidne ji uuplne celou vypocitat 
 +  * jedeme cyklus po sloupeckach teto tabulky a na kazdem miste pustime rekurzivni funkci "​prohledej"​ a predame ji aktualni index sloupecku jako startovaci pozici (tato se pak vypisuje pokud nalezneme reseni, ja si ji k tomu ucelu ukladal nekam stranou) 
 +  * funkce prohledej dela normalne rekurzivni prohledavani do hloubky pres vsechny permutace hledanych genu, pri sestupu napocitavame soucet hammingovych vzdalenosti.  
 +  * Z rekurze se vracime pokud jsme nalezli reseni (kdyz jsme sikovni, a permutujeme v pozadovanem poradi, muzeme ho rovnou vypsat =)   ​Rekurzi take prerusime, pokud soucet hamingovych vzdalenosti presahl povolenou hodnotu, cimz odrezeme spousty seschlych vetvi.  
 +  * Jo! A bacha at na konci dna nevypadnete a nerozbijete si drzku o mitochodrie ( modri vedi =P ). 
  
 +~~DISCUSSION~~
  
courses/a4m33pal/uloha4-2011.1321286495.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)
Nahoru
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0