navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha4-2011 [2011/12/07 02:23] nardi |
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 55: | Řádek 56: | ||
| * 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 ====== | |
| - | ===== Řešení za 10/10 ===== | + | |
| * vytvorit si tabulku hammingovyc vzdalenosti pro vsechny pozice vsech genu tedy int hamming[N][dna.length] a klidne ji uuplne celou vypocitat | * vytvorit si tabulku hammingovyc vzdalenosti pro vsechny pozice vsech genu tedy int hamming[N][dna.length] a klidne ji uuplne celou vypocitat | ||
