Témata

Témata jsou hlavním obsahem časopisu M&M. Obvykle představují složitější a obecnější problémy než samostatné úlohy. Navíc je v jejich zadání vždy prostor pro tvůrčí rozšíření. Za pěkný článek k tématu lze získat třeba i 20 bodů, určitě se tedy vyplatí se tématy zabývat.

Jak řešit téma?

Letos jsme pro tebe připravili tato témata:

Téma 1: Krotitelé světla

Laser je přístroj, který dokáže vytvořit světelný svazek natolik koncentrovaný, že ho lze využít k mechanickým úkonům, např. řezání skla. My s ním sice v této úloze přímo pracovat nebudeme, pokusíme se však jeho vlastnostem přiblížit za pomoci nám dostupných jednodušších mechanismů – odrazu a lomu světla. Naším cílem bude ovládnout světlo a donutit ho vytvořit v prostoru oblast s výrazně vyšší intenzitou.

Nejjednodušším přístrojem, který má tuto schopnost, je optická čočka, která zalamuje rovnoběžné paprsky blízké optické ose do jediného bodu (ohniska). Je možné celý výkon koncentrovaný v tomto bodě následně nasměrovat do libovolně tenkého paprsku? Jestliže ne, proč?

Je možné zařídit, aby bylo do ohniska lámáno víc paprsků? Navrhněte uspořádání (stačí ve 2D), při kterém je do ohniska, případně do jediného paprsku, koncentrováno co nejvíce světla z okolí. Můžete uvažovat rovnoměrné osvětlení, nebo naopak předpokládat, že světlo přichází primárně z jednoho konkrétního směru.

Nemusíte se při tom ani držet čočky, zkuste nalézt jiný předmět s podobnými vlastnostmi. Jaký tvar by musel mít povrch objektu, aby lámal do ohniska všechny rovnoběžné paprsky bez ohledu na jejich vzdálenost od optické osy? Popřípadě zkuste nalézt takový předmět, který v sobě udrží paprsek co nejdéle. Může existovat takový předmět, v němž by jednou vlétnuvší paprsek už zůstal?

K výpočtu dráhy každého paprsku využijte zákony odrazu a lomu, můžete uvažovat paraxiální aproximaci (tj. $\sin \alpha =\alpha =\mathop {\mathrm{tg}}\alpha $ pro malé $\alpha $), nebo se od ní naopak odchýlit a přemýšlet obecněji. Můžete využít i více různých materiálů s různými indexy lomu. Vítány jsou také jakékoli experimentální realizace vámi vytvořených schémat.

Evžen

Stejně


Téma 2: Mapování DNA

Využívat a ohýbat přírodu pro své záměry se lidé snaží snad už celé věky. Ale až v posledních desetiletích se nám dostaly do rukou nástroje, kterými dokážeme manipulovat s těmi nejzákladnějšími stavebními kameny života – s DNA. Díky nim dokážeme uměle vytvářet nové organismy nebo třeba velmi přesně předpovídat, jaké zdravotní problémy by toho kterého člověka mohly potkat.

Ale k tomu, abychom mohli DNA upravovat pro naše záměry, je třeba vědět, kde se v ní co nachází. Dnes asi nejjednodušší možností je DNA prostě nasekvenovat – tedy určit jak přesně jdou jednotlivé báze v dané DNA za sebou – a vše vyčíst z řetízku bází. My se ale podíváme na metodu, která nám toho sice o DNA řekne méně, ale zase je mnohem jednodušší. A to na restrikční mapování.

Restrikční mapování je založené na použití tzv. restrikčních enzymů. To jsou molekuly, které dokážou DNA „rozstřihnout“ v těch místech, která obsahují nějakou konkrétní posloupnost bází (např. enzym EcoRI rozstřihne posloupnost bází GAATTC). Nejdřív tedy DNA pomocí nějakého restrikčního enzymu rozstříháme na kratší kusy – fragmenty. Následně pomocí elektroforézy změříme délky a počty fragmentů a z těchto informací chceme sestavit restrikční mapu. To je seznam míst v DNA, ve kterých stříhá daný enzym (restrikčních míst). Pokud máme DNA dlouhou 20000 bází a získáme fragmenty délky 8000, 7000 a 5000 bází, pak restrikční mapa může např. říkat, že enzym stříhá v místě vzdáleném 7000 bází od začátku sekvence a v místě vzdáleném 15000 bází od začátku sekvence.

Z příkladu už je vidět, že jen z délek a počtu fragmentů restrikční mapu nesestavíme – není jasné, jak fragmenty uspořádat. V praxi se proto používají enzymy dva. Nejdřív DNA naštěpíme prvním, pak druhým a pak oběma současně – to nám znemožňuje uspořádat fragmenty úplně libovolně. Stačí to? Zkuste najít netriviální protipříklad dokazující, že ani v tomto případě nemusí být restrikční mapa jednoznačná. Dá se s tím nějak vypořádat? Zkuste vymyslet jiné metody, jak najít restrikční mapu DNA (pro jeden, nebo pro více restrikčních enzymů).

Jak ale vlastně z fragmentů sestavíme restrikční mapu? Inu, pořídíme si na to nějaký program! Zkuste vymyslet algoritmus, který dostane délky a počty fragmentů a sestaví z nich restrikční mapu. Můžete použít variantu se dvěma enzymy z předchozího odstavce (které se říká Double Digest Problem), nebo nějakou vlastní „stříhací“ metodu. Pokud umíte programovat, můžete svůj algoritmus i naprogramovat a podívat se, jak funguje. K tomu se vám může hodit online nástroj1, kterým si můžete nastříhat DNA nebo rovnou vyrobit restrikční mapu. Pokud byste si chtěli nastříhat nějakou reálnou DNA, můžete využít online databázi DNA2. Nenechte se zastrašit lehce komplikovaným rozhraním obou stránek, časem se na https://mam.mff.cuni.cz/zadani/temata/ objeví návod, jak je používat.

Pokud se s algoritmy a programováním moc nekamarádíte, můžete se zkusit zaměřit na experimentální část mapování. Jak vůbec takové restrikční enzymy fungují a jak poznají, kde mají stříhat? Na jakém principu funguje měření délek fragmentů? Dokážeme nějak poznat, kolik je fragmentů dané délky? A jak přesné ono měření vůbec je? Dá se s nepřesnostmi případně nějak vypořádat?

Napadla-li vás nějaká otázka, která zde nezazněla, nebojte se nad ní zamyslet a něco k ní poslat. Stejně tak se nebojte napsat, pokud potřebujete pomoci třeba se získáním nějakých zdrojů, ke kterým se nemůžete dostat, nebo máte nějaký dotaz.

O(N)dra


1) http://www.restrictionmapper.org/

2) https://www.ncbi.nlm.nih.gov/nucleotide/

Stejně


Téma 3: Mafie jako výpočetní model

Za sedmero horami a sedmero řekami v jednom odlehlém městečku byla mafie. Jak taková mafie vypadá? Skládá se z mafiánů. Žádný mafián samozřejmě z bezpečnostních důvodů nezná všechny ostatní mafiány – každý jich zná jen konstantně mnoho a s těmi si dopisuje. Každý den ráno pošle všem svým známým mafiánům dopis. (Každá dvojice známých mafiánů si tedy každý den pošle dva dopisy – v každém směru jeden.) Všechny dopisy se do večera doručí. Mohli bychom tedy říci, že celá mafie má strukturu souvislého grafu1. Vrcholy odpovídají mafiánům a hrany reprezentují to, zda si daná dvojice dopisuje.

Mafiáni by nyní chtěli zjistit něco o tom, jak ta jejich mafie vypadá – třeba kolik jich je. Jediný způsob, jak něco takového zjistit, je pomocí mafiánů, co se znají a posílají si dopisy. Nejdříve mafiánský boss na předem domluveném místě vylepí algoritmus, který bude popisovat, jak si mají mafiáni posílat dopisy, aby hledanou informaci zjistili. Každý den si pak známí mafiáni mohou vyměnit zprávu. Cílem je, aby na konci každý mafián věděl informaci, na kterou se snažili přijít.

Vymyslete grafové vlastnosti nebo problémy, které by mafiáni mohli řešit, nebo zkuste vyřešit jeden z problémů zmíněných v další části. Určete složitost vašeho algoritmu. Jde nám především o počet dnů, za který v nejhorším případě algoritmus skončí, a součet délek všech zpráv, které si mafiáni vymění. Jak se na každého správného mafiána sluší, má neomezený výpočetní výkon, takže časovou složitost v běžném slova smyslu uvažovat nemusíte. Složitosti můžete vyjadřovat v závislosti na počtu mafiánů, průměru grafu mafie (největší vzdálenost mezi dvojicí mafiánů), nebo si můžete vymyslet svůj vlastní parametr. Složitosti určujte asymptoticky2.

Inspirovat se můžete následujícími problémy:

  • Zjistěte velikost mafie, tedy počet mafiánů, kteří v ní jsou.

  • Mafiáni by chtěli co nejvíce omezit počet dopisů, které pošlou. Rozhodli se proto, že si spolu někteří mafiáni přestanou dopisovat. Najděte co nejvíce dvojic, které si spolu mohou přestat dopisovat tak, aby stále mezi libovolnou dvojicí mafiánů existovala cesta.

  • Mafiáni by chtěli zjistit, jaký je celkový majetek mafie (vyjádřeno v místní měně). Žádný z mafiánů při tom nechce, aby některý jiný mafián zjistil hodnotu jeho majetku.

  • Čas od času potřebuje nějaký mafián o něčem informovat všechny ostatní. To se dělá tak, že předá zprávu všem, se kterými si dopisuje. Každý další mafián pak zprávu přepošle ostatním mafiánům, se kterými si dopisuje (ale jen při prvním přijetí dané zprávy). Zjistěte, jak nejdéle může trvat, než se zpráva dostane ke všem mafiánům.

  • Mafiáni by chtěli vědět, kolik nejméně z nich by muselo být zatknuto, aby se mafie „rozpadla“. Tedy aby pak existovali dva mafiáni, mezi kterými nebude existovat cesta vedoucí pouze přes nezatčené mafiány. Jinými slovy chceme spočítat největší k takové, že graf mafie je k-souvislý. Toto by mohlo být zajímavé už pro k=2. (Věřím, že tento problém je poměrně těžký a možná ani nemá efektivní řešení.)

Kuba


1) Pokud nevíte, co se myslí grafem, doporučujeme přečíst si prvních pár odstavců grafové kuchařky zde: https://ksp.mff.cuni.cz/kucharky/grafy

2) Pokud nevíte, co se tím myslí, doporučujeme přečíst odstavec asymptotická složitost v programátorské kuchařce o složitosti: https://ksp.mff.cuni.cz/kucharky/slozitost/

Stejně


Téma 4: Odmocniny

Co je odmocnina? Začněme druhou odmocninou: $\sqrt {y} = x$ právě když $y=x \cdot x$. Co kdybychom ale odmocňování zobecnili a násobení zaměnili za jinou operaci? Pro začátek můžeme vyzkoušet odmocňování pro skládání permutací.

Permutace je matematické označení pro prohazování prvků. Takové prohazování můžeme zapsat více způsoby. Třeba zápis $(1, 3, 4, 2)$ vyjadřuje takové prohození čísel $(1, 2, 3, 4)$, kdy na prvním místě zůstane jednička, na druhém místě se objeví trojka, na třetím čtyřka a konečně na čtvrtém místě bude dvojka. Permutaci ale nemusíme použít pouze na řetězec $(1, 2, 3, 4)$, ale i na jiné posloupnosti čísel délky 4. Speciálně ji můžeme použít i na řetězec $(1, 3, 4, 2)$, pak vznikne posloupnost $(1, 4, 2, 3)$. Postupu, kdy permutaci aplikujeme na výstup jiné (nebo stejné) permutace, říkáme skládání permutací a budeme jej značit $\circ $. Naše permutace složená sama se sebou tedy dává permutaci $(1, 4, 2, 3)$, což pomocí našeho značení zapíšeme jako $(1, 3, 4, 2)\circ (1, 3, 4, 2) = (1, 4, 2, 3)$. Pozor, abychom dostali přímo výslednou permutaci, musíme začít s posloupností $(1, 2, 3, 4)$. Tato posloupnost je ostatně také permutací, velmi specifickou, která neprohodí žádná čísla. Říkáme jí také identita.

Pro snadnější skládání se hodí i jiný způsob reprezentace permutací, kdy si pomocí šipek nakreslíme, odkud kam se prohazují čísla. Pro naši permutaci by taková reprezentace vypadala jako na obrázku 1:

Obrázek 1: Grafické znázornění permutace

Pro začátek zkuste vyřešit následující problémy:

  • Které permutace složené samy se sebou dávají identitu? Zkuste najít všechny takové a charakterizovat je pro libovolně dlouhé posloupnosti čísel.

  • Představte si, že dostanete libovolnou permutaci $p$. Jak najít permutaci $q$, pro kterou platí $p = q \circ q$? Kdy taková permutace existuje?

Pokud tě skládání permutací nezaujalo, můžeš samozřejmě vymyslet jiné zajímavé operace a řešit podobné problémy pro ně.

Anet

Stejně


Téma 5: Dají se přeprogramovat živé organismy?

Syntetická biologie je vědní odvětví na rozmezí několika oborů. Kromě biologů a inženýrů se v ní snadno najdou i informatici nebo matematici. Je to poměrně mladý obor, který se snaží vypomoci bioinženýrským oborům obecně tím, že standardizuje „součástky“ a jejich metody spojování, které pak umožní pracovat na vyšších inženýrských úrovních. Podobná revoluce proběhla v samotném inženýrství – považte, šroubků je sice i tak mnoho druhů, ale kdyby si každý vyráběl na míru své vlastní, nestandardní, nejspíš by nikdo nikdy nepostavil třeba auto, a už vůbec ne masově. Syntetická biologie se snaží mimo jiné umožnit, aby mohli jedni vědci vyrábět z elementárních součástek základní moduly a jiní je potom bez obav mohli používat k vytváření větších celků. Ono v biologii nic není tak předvídatelné, jak by se inženýrovi nebo programátorovi mohlo zdát, především proto, že systém není vytvořen člověkem jako programovací jazyky ani založen na základním konečném množství fyzikálních zákonů jako inženýrství. Biologický systém je neuvěřitelně složitý, formovaný miliony let evoluce a málo prozkoumaný. Na druhou stranu, bioinženýrství je novou nadějí například pro uživení populace s rozumným množstvím zemědělské půdy, pro řešení problémů znečištění přírody a zajištění obnovitelné energie a dalších důležitých přírodních zdrojů, nebo pro medicínu.

Skoro všechny moduly a součástky, o kterých se bavíme, jsou ve formě DNA (deoxyribonukleová kyselina). DNA je nositelkou genetické informace a díky biologicky (téměř) universálnímu kódu je možné ji přeložit do proteinů, které v buňkách plní všemožné funkce, nejzajímavější mají asi enzymy při katalýze reakcí. Design DNA (především počítačový) a experimentální realizace plánu jsou tedy základními kameny nejen syntetické biologie a ostatních bioinženýrských oborů, ale už dávno před nimi je využíval i základní výzkum v jiných biologických odvětvích, protože cílený zásah do systému nám o něm může prozradit více než jenom jeho pozorování a měření.

V tomto témátku se postupně podíváme na všechna stádia, kterými se při takovém designu, sestavování a vpravení DNA do cílového organismu musí projít. První fáze je většinou počítačová. Když už máme nápad, jakou DNA bychom potřebovali pro náš experiment, můžeme použít různé počítačové nástroje na vizualizaci sekvencí DNA (složených z bází A,T,G,C) a jejich modifikaci, což nám pomůže s plánováním experimentu. Pokud známe cílovou DNA, je nejjednodušší si ji nechat u firmy (např. IDT) nasyntetizovat. To ale jde jen do určité velikosti a syntéza DNA na míru je oproti čtení zatím velmi drahá i pro většinu světových laboratoří. Takže se podíváme, jak se dá DNA poskládat z kousků DNA, které už máme nebo si můžeme objednat v databázích jako např. Addgene nebo iGEM distribuce Biobricks. Na poskládání naší DNA můžeme využít různé metody od starší metody založené na enzymatickém rozštípání DNA na konkrétních místech a následné ligace v cyklech přes metody založené na restrikčních enzymech typu IIS, které štípají těsně vedle sekvence, jež rozeznávají. Mimo to existují speciální metody na skládání opravdu velkých kusů DNA dohromady, které nám pomáhají sestavovat umělé genomy. Zatím se vědci v tomto odvětví pokouší především o zjednodušení stávajícího genomu v naději, že pak bude snáze manipulovatelný. A samozřejmě, nesmíme zapomenout na CRISPR/Cas9, který dovede měnit DNA přímo v organismu na konkrétním místě. V neposlední řadě svůj poskládaný nebo nasyntetizovaný kus DNA potřebuje vědec ověřit sekvenováním, vpravit do živého organismu a pak testovat, jestli dělá to, co má. U některých modelových a dobře prozkoumaných organismů je vložení DNA jednoduché, u jiných to může být (zatím) nepřekonatelný problém. Navíc v mnoha případech zasahujeme do nepříliš dobře prozkoumané a velmi složité sítě původních reakcí a procesů a efekty jsou těžko předvídatelné. A co se děje s naší novou DNA po mnoha generacích, když tak často jdeme svými požadavky proti evoluci? Co s tím můžeme dělat? Jak nám pomůže počítačové modelování? A co na to všechno etika?

Možných otázek je velmi mnoho a určitě můžete posílat příspěvky k čemukoliv, co vás zaujme. Velmi vítaný bude i podrobnější úvod do oboru, který ostatním poradí, odkud začít s průzkumem konkrétnějších témat. Pro začátek se zkusme zaměřit na první stádium – získání DNA a počítačové plánování, jak z něj sestavit finální sekvenci. K tomuto bude potřeba se trochu věnovat i technikám, které ke složení budou potřeba, zatím na teoretičtější rovině.

Zkuste se podívat, jaké existují databáze kousků DNA a jestli jsou dostačující. Jak moc se zatím daří standardizace „součástek“ a metod jejich skládání? Dají se stejně charakterizované součástky opravdu používat v jakémkoliv organismu, od bakterie po rostlinné či savčí buňky, nebo je v tom nějaký háček, a proč se tak často „optimalizují“ použité kodóny (souvisí to s genetickým kódem a „codon usage“)? Jaké může mít výhody používat zmíněné restrikční enzymy typu IIS (stříhající mimo sekvenci, kterou rozeznávají) pro vytvoření naší nové DNA a pro přiblížení se cílům syntetické biologie? Některé velmi dobré programy na vizualizaci a modifikaci DNA jako třeba Geneious jsou komerční. Existují k nim dobré open source alternativy? Pro ty z vás, které zajímá informatika, může být výzvou vytvořit nebo vylepšit nějaký nástroj, který usnadní jakékoliv stádium v designu DNA. Můžete se zamyslet i teoreticky, jakým informatickým výzvám tady takový programátor čelí a navrhnout pro ně možná řešení (bude na to asi potřeba vhled z molekulární biologie).

Praktická řešení přinášející nové myšlenky a výtvory jsou nejcennější a nebojte se pustit do větších, třeba i skupinových, projektů, ráda se o tom s vámi i poradím a pomůžu, kde začít a jak se spojit. Ze zajímavých nápadů, které budete ochotni zpracovat i anglicky, může vzniknout spolupráce se studentským klubem syntetické biologie na universitě v Cambridge. Těším se na vaše příspěvky.

Lucka

Stejně