\gdef\mujnazevCS{Rozšířená recenze knihy: Bioinformatics Algorithms --\odskoc An Active Learning Approach, Vol. I, II}
\gdef\mujnazevEN{Extended Book Review: Bioinformatics Algorithms -- An Active Learning Approach, Vol. I, II}
\gdef\mujnazevPR{\mujnazevCS}
\gdef\mujnazevDR{\mujnazevEN}
\gdef\mujauthor{Pavel Stříž}

\bonushyper

\nazev{Rozšířená recenze knihy: Bioinformatics Algorithms -- An Active Learning Approach, Vol. I, II}

\nazev{\mujnazevEN}

\author{\mujauthor}

%\Adresa{}

\Email{pavel@striz.cz}
\medskip

\def\malkapitola#1{\medskip\par\noindent\textbf{#1}}
\def\maltitul#1{\textbf{#1}\par\nopagebreak}
\def\malpodtitul#1{\noindent\textit{#1}}
\shorthandoff{-}


\noindent
Phillip Compeau, Pavel Pevzner: \textit{Bioinformatics Algorithms -- An Active Learning Approach,} 2nd Edition, Active Learning Publishers, USA, Volume~I{} (xxv+355 pp.), II~(xxiii+291 pp.), 2015. Vedle titulních stran svazků jsou ilustrace uvozující kapitolu 2 a~10.
\medskip

\fboxsep=0pt \fboxrule=1pt
%4 obrázky
\noindent
\newdimen\malvyska \malvyska=39mm
\fbox{\includegraphics[height=\malvyska, page=1]{baaala1.pdf}}\hfill%
\fbox{\includegraphics[page=91, trim=0cm 0cm 2.2cm 0cm, clip, height=\malvyska]{baaala1.pdf}}\hfill%
%
\fbox{\includegraphics[height=\malvyska, page=1]{baaala2.pdf}}\hfill%
\fbox{\includegraphics[page=201, trim=4mm 4mm 2.7cm 4mm, clip, height=\malvyska]{baaala2.pdf}}%
\medskip

\hfill Motto: \textit{Find the \{most likely, mass, minimum, maximum, length, longest, shortest, highest-scoring, reverse, pattern, optimal, position, center, frequent, circular, nearest,\,\ldots\} in a~string.}%
\smallskip

%\noindent
Před lety jsem hledal server, který by nabízel sérii úloh na procvičování programování, ale aby to byl nějaký rozumný počet a~uzavřené. Plus abych mohl vydat něco typu \textit{Sbírka řešených úloh} s~odkazy na zdroj. Dlouhodobě se zabývám zpracováním textu a~na konferenci OSSConf v~Žilině jsem zaslechl: \uv{\ldots\ my na to v~texte na webe používame matíciu vzdáleností a~funguje to naozaj dobre\ldots} Říkal jsem si, že to už jsem někde viděl či četl, že se na to musím doma podívat. Edit distance od Levenshteina z~1966 \uv{bylo naozaj to, o~čem bratia hovorili}. Hledal jsem nějaké příklady a~ukázky a~za chvíli jsem byl na webu \url{http://rosalinde.info} a~viděl i~různé modifikace tohoto problému, viz sekce \textit{Bioinformatics Textbook Track}. Úlohy mají na webu a~není omezení na programovací jazyk ani čas (jak dost často bývá zvykem u~soutěžního programování) a~mají tam úvod do Pythonu i~algoritmizace.

Začal jsem úlohy postupně řešit, pak jsem se zasekl. Tak jsem dohledal jejich knihy a~znovu řešení úloh obnovil. V~době psaní recenze mi ještě pár tuctů úloh chybí, ale ty už jsou obtížností z~jiného světa, ale je vidět světlo na konci tunelu. A~hlavně jsem na druhý pokus (první asi zapadl mezi emailové spamy) dostal souhlas autorů na takový knižní počin.

O~co tedy v~knihách jde? Jedná se de facto o~skripta na bioinformatiku podpořené serverem na úlohy z~knihy plus celý blok úloh nezmíněné v~knize, ale též z~bioinformatiky. Obrovskou výhodou je, že po uznání úlohy jako vyřešené je k~dispozici diskuzní fórum k~dané úloze, dá se častokrát narazit na zajímavé myšlenky a~postupy plus řešení v~nejrůznějších %programovacích 
jazycích.

Dvousvazková kniha mi za ty roky přirostla k~srdci. Věděl jsem, že závěrečné problémy budou těžké, dokonce Pavel Pevzner o~tom někde psal, že to tak dělá u~svých studentů, že přes těžké (i~některé nevyřešené) problémy se z~nich snaží dostat to nejlepší, říkejme jim \textit{Code Challenges}. Snad se v~budoucnu se všemi vyřešenými úlohami pochlubím. %, zatím je to stále práce v~běhu.

Za zmínku stojí i~jejich YouTube kanál, kde řeší vybrané úlohy. Odkazy a~prezentace, viz \url{http://bioinformaticsalgorithms.org}. V~knize vás potěší \textit{Detours}, tedy čtení rozšiřující a~odpočinkové. Nápovědy k~úlohám lze hledat pod \textit{Charging Stations}. Kniha vyzývá i~k~řešení reálných problémů, viz \textit{Final Challenges}.

Pokud se zabýváte alespoň trochu typografií a~sazbou, kniha pro vás nebude zklamáním ani z~tohoto pohledu. V~metadatech PDF souborů lze vyčíst, že je sázen \TeX em. Obrázky (grafy, stromy, diagramy ap.) jsou vysázené ve většině případů v~barvě a~v~prvotřídní kvalitě. Ve vzorcích zahlédnete barevné výrazy, to byla jednu dobu má příjemná úloha automatizace pro Lua\TeX. U~jednotlivých kapitol přikládám vzorek 
%pro potěšení oka 
s~otázkou, jak to vysázet?

Kniha je rozdělena do 6+5 kapitol. Zkusím je stručně představit, jaké oblasti řeší a~vždy několik problémů, které se v~kapitole objeví.

%\enlargethispage{\baselineskip}
\malkapitola{Kapitola 1:}
\maltitul{Where in the Genome Does DNA Replication Begin?}
\malpodtitul{Algorithmic Warmup.}
Úvod do četností, měření odlišností, hledání vzorů a~práce s~textovými řetězci skládající se ze znaků \{A,C,G,T\}. Musíme brát na paměti, že je to příjemná konvence pro čtenáře užívat znaky (8 bitů), efektivnější samozřejmě je pracovat se dvěma bity, které nám čtyři znaky dokáží zakódovat. 
Na ukázku sazby jsem vybral horní obrázek ze str.\,21.%
\fboxrule=0pt\fboxsep=0pt% dočasné

\noindent\hfil
\fbox{\includegraphics[page=36, trim=38mm 55mm 44mm 12.5cm, clip, height=30mm]{baaala1.pdf}}%
\kern3mm %\hfill
\fbox{\includegraphics[page=46, trim=5.0cm 15.1cm 5.65cm 2.5cm, clip, height=30mm]{baaala1.pdf}}%

\newpage%
\malkapitola{Kapitola 2:}
\maltitul{Which DNA Patterns Play the Role of Molecular Clocks?}
\malpodtitul{Randomized Algorithms.}
Hledání vzorů a~jejich ohodnocení, Hamming Distan\-ce, Gibbs Sampling. 
Za sazbu jsem vybral obrázek ze str.\,74 a~pravý obrázek ze str.\,109.

\noindent
\fbox{\includegraphics[page=99, trim=6.3cm 7cm 2.4cm 13.2cm, clip, height=2.65cm]{baaala1.pdf}}\hfill%
\fbox{\includegraphics[page=134, trim=9.5cm 8.5cm 3.4cm 8.8cm, clip, height=2.65cm]{baaala1.pdf}}%


\malkapitola{Kapitola 3:}
\maltitul{How Do We Assemble Genomes?}
\malpodtitul{Graph Algorithms.}
Úvod do teorie grafů, rekonstrukce řetězce, Hamiltonian Path, De Bruijn Graph. S~úsměvem lze říci, že se jedná o~slavné FBI případy, tedy seskládání důležitých dokumentů prohnaných skartovačkou. Zkušení hackeři ví, že dokumenty je potřeba pálit, nikoliv skartovat. U~této kapitoly si člověk připadal jako správný detektiv.
Za sazbu jsem vybral obrázky ze str.\,134, 161 a~175.

\noindent
\fbox{\includegraphics[page=159, trim=6.2cm 4.3cm 5.5cm 12.4cm, clip, height=3.25cm]{baaala1.pdf}}\hfill%
%\fbox{\includegraphics[page=181, trim=4cm 10cm 7cm 10cm, clip, height=3cm]{baaala1.pdf}}%
\fbox{\includegraphics[page=186, trim=5.1cm 4.9cm 5.8cm 13.1cm, clip, height=3.25cm]{baaala1.pdf}}\hfill%
\fbox{\includegraphics[page=200, trim=9.4cm 4.8cm 3.4cm 13.4cm, clip, height=3.25cm]{baaala1.pdf}}%


\malkapitola{Kapitola 4:}
\maltitul{How Do We Sequence Antibiotics?}
\malpodtitul{Brute Force Algorithms.}
Kapitola uvádí sekvencování peptidů, konvoluci.
Za sazbu jsem vybral vysázení proteinů ze str.\,189 a~zdrojového kódu ze str.\,196.%

\noindent\hfil
\fbox{\includegraphics[page=214, trim=3.2cm 4.7cm 3.8cm 12cm, clip, height=3.4cm]{baaala1.pdf}}%
\hfill
\fbox{\includegraphics[page=221, trim=2.8cm 5.7cm 6.2cm 11.75cm, clip, height=3.4cm]{baaala1.pdf}}%


\malkapitola{Kapitola 5: }
\maltitul{How Do We Compare Biological Sequences?}
\malpodtitul{Dynamic Programming.}
Mé oblíbené úlohy, jak s~minimem změn z~jednoho řetězce dostat druhý. Tato úloha mě dovedla k~této knize. Uvede dále i~do variant lokální a~globální a~úlohy s~více než dvěma řetězci. 
Obrázky z~teorie grafů jsou čtenáři jistě dobře známé, za sazbu jsem vybral obrázek ze str.\,260, 276 a~za sazbu textu výsledek zarovnání tří řetězců a~jejich barevné odlišení ze str.\,290. Na vysvětlenou. Červená značí shodu ve třech případech, zelená, modrá a~hnědá v~příslušných dvou případech, u~černé není shoda a~divis je vložení prázdného znaku do původního řetězce.

\noindent
\fbox{\includegraphics[page=285, trim=4cm 5cm 3.4cm 7.1cm, clip, height=3.7cm]{baaala1.pdf}}%
\hfill
\fbox{\includegraphics[page=301, trim=3.4cm 5.9cm 2.7cm 11.5cm, clip, height=3.7cm]{baaala1.pdf}}%

\noindent\hfil
\fbox{\includegraphics[page=315, trim=3.6cm 7.1cm 2.85cm 13.25cm, clip, width=0.8\textwidth]{baaala1.pdf}}%


\enlargethispage{\baselineskip}
\malkapitola{Kapitola 6:}
\maltitul{Are There Fragile Regions in the Human Genome?}
\malpodtitul{Combinatorial Algorithms.}
Úvod do kombinatoriky, přesněji permutací, jak získat chromozom z~jiného. %Zde končí první svazek. 
Za svět sazby jsem vybral znázornění, jak z~myši udělat člověk ze str.\,302 a~transformaci genomu ze str.\,338.

\noindent
\fbox{\includegraphics[page=321, trim=3.8cm 11.6cm 3.3cm 2.6cm, clip, height=5cm]{baaala1.pdf}}\hfill%
\fbox{\includegraphics[page=363, trim=5.3cm 3.8cm 4.6cm 11.3cm, clip, height=5cm]{baaala1.pdf}}%


\malkapitola{Kapitola 7:}
\maltitul{Which Animal Gave Us SARS?}
\malpodtitul{Evolutionary tree reconstruction.}
Kapitola začíná druhý svazek a~uvádí do evolučních stromů a~jejich konstrukci. Podobnou konstrukci známe z~rodokmenů, jen je to ve větším měřítku a~vztahy se teprve hledají. 
Za sazbu jsem vybral evoluční strom ze str.\,64, jen otočený skrz úsporu místa.%

\noindent\hfil
\fbox{\rotatebox{-90}{\includegraphics[page=87, trim=5.9cm 8.5cm 5.3cm 3.2cm, clip, angle=0, height=9.5cm]{baaala2.pdf}}}%
\medskip



\malkapitola{Kapitola 8:}
\maltitul{How Did Yeast Become a~Wine Maker?}
\malpodtitul{Clustering Algorithims.}
Shlukování je náplní této kapitoly. Mezi algoritmy najdeme starý dobrý známý Lloydův pro $k$-means a~CAST. Poté se kapitola zabývá hierarchických shlukováním. 
Za sazbu jsem vybral strom ze str.\,105 s~3D reprezentací. Na str.\,104 a~107 upoutají tabulky se symetrickými hodnotami. Někdy se hodnoty vynechávají, zde se autoři rozhodli pro odlišnou (šedou) barvu.

\noindent\hfil
\fbox{\includegraphics[page=128, trim=3.4cm 6cm 4cm 11.5cm, clip, height=5cm]{baaala2.pdf}}%


\malkapitola{Kapitola 9:}
\maltitul{How Do We Locate Disease-Causing Mutations?}
\malpodtitul{Combinatorial Pattern Matching.}
Kapitola uvádí do datových struktur a~jejich rychlé prohledávání: trie, suffix trie, suffix tree, suffix array. Velká část kapitoly je věnována transformaci Burrows-Wheeler a~její inverzi. Pokud si to již někdo zkoušel naprogramovat, tuší, že už jde v~knize do tuhého. Na ukázku hezké sazby jsem vybral SuffixTree ze str.\,168.

\noindent\hfil
\fbox{\includegraphics[page=191, trim=4.15cm 14.4cm 3.6cm 3.4cm, clip, width=0.6\textwidth]{baaala2.pdf}}%


\malkapitola{Kapitola 10:}
\maltitul{Why Have Biologists Still Not Developed an HIV Vaccine?}
\malpodtitul{Hidden Markov Models.}
Skryté Markovovské řetězce v~plné síle plus Baum-Welch Learning. Za sazbu jsem nevěděl, co vybrat dřív, jestli barevné vzorce či reprezentaci HMM. Vybral jsem jednu textovou ukázku (změny v~čase u~proteinu gp120 u~pacienta s~HIV) ze str.\,180 a~jednu grafickou HMM ze str.\,207 s~volenou nejpravděpodobnější cestou k~danému problému.

\noindent
\fbox{\includegraphics[page=203, trim=4cm 18.4cm 3.4cm 3.1cm, clip, width=\textwidth]{baaala2.pdf}}%

\noindent\hfil
\fbox{\includegraphics[page=230, trim=3.4cm 8.25cm 5.1cm 10cm, clip, width=0.6\textwidth]{baaala2.pdf}}%



\malkapitola{Kapitola 11:}
\maltitul{Was \textit{T.\,rex} Just a~Big Chicken?}
\malpodtitul{Computational Proteomics.}
Kapitola uvozuje práci s~identifikací a~výpočty kolem spekter peptidů. Přečíst kapitolu není těžké, ale naprogramovat výzvy a~neztratit se v~nich, to už těžké je. Na závěr ze světa sazby jsem si pro vás opět vybral jednu textovou ze str.\,237, jedná se opět o~jistý výsledek (seskládání peptidů u~inzulínu, výsledkem je sekvence aminokyseliny, viz práce Fredericka Sangera) a~dvě grafické ze 
str.\,270 (dvě modifikace jednoho peptidu)
a~243 (DAG; orientovaný acyklický graf).

\noindent
\fbox{\includegraphics[page=260, trim=3.45cm 13.2cm 4.2cm 3.05cm, clip, height=35mm]{baaala2.pdf}}%
\hfill
\fbox{\includegraphics[page=293, trim=5.5cm 6cm 4.9cm 13.4cm, clip, height=35mm]{baaala2.pdf}}%

\noindent
\fbox{\includegraphics[page=266, trim=3.5cm 15cm 4.2cm 6cm, clip, width=\textwidth]{baaala2.pdf}}%




Závěr každé kapitoly je jisté slovní shrnutí zdrojů a~vývoj v~dané oblasti.


Pokud jste víc matematici a~statistici než \uv{bio}, kniha nabízí nespočet úloh, zvlášť u~kapitol 10 a~11 se protáčí panenky. Pokud jste víc programátoři, tak vězte, že biologické úlohy jsou převedeny na zadání zpracování textu, a~to už bude vaše doména. Pokud nejste (ještě) ani jedno ze zmíněných, zkuste si pár úloh jen tak, pro zábavu z~řešení stylu \uv{Heuréka, ono mně to vyšlo!} či si knihami prolistujte, pro inspiraci z~hezky vysázené knihy.


Kniha tiše nabízí možnost si úlohy vyzkoušet v~\emph{libovolném} programovacím jazyce. To ale nevylučuje užití \emph{hotových} programů či knihoven, např. v~R, resp. s pomocí BioConductoru. Věřím tomu a~ověřil jsem si to, že na mnoha místech to jde, ale jádro knihy k~tomu nesměřuje. Myslím si však, že člověk nemusí být zrovna druhý Donald E. Knuth (TAOCP), John Carmack (Doom, Wolfstein 3D), Linus Torvald (Linux, Git), 
Dennis Ritchie (C), Steven Halim (kniha Competitive Programming), či Gennady Korotkevich (v současnosti nejlepší soutěžní programátor),
% (kniha soutěžní programování, vítěz IOCP z~let ) či  Sen? William Lin (YouTuber, vítěz IOCP z~let ), 
aby si užil hezkou knihu a~\uv{trochu} toho programování.


Kniha obsahuje hezké ilustrace, rozšiřující seznam zdrojů a~našince potěší, že mezi zdroji na obrázky v~druhém svazku, úplně poslední strana, zahlédne jméno Katka Nemčoková, její fotka je na str.\,34 vpravo. Byla to při čtení podobná radost, jako zaslechnout češtinu v~seriálu Stargate Atlantis (spinoff slavného seriálu Stargate CG). Nesmím opomenout zmínku na Toma Stopparda, str.\,92, rodáka ze Zlína, byť rodina emigrovala do Anglie v~jeho útlém věku. Ještě jsem si poznačil jedno jméno, moment, ano, samozřejmě, Mendelovy zákony na str.\,215 prvního svazku. Snad jsem nikoho dalšího neopomenul.

% Bezdek? soft k-means
% Dančík? pevzner, tang 2000
% Sokal?

Poznámka závěrem. U~této knihy, ale i~obecně, jsem si říkal, že číslo strany by bylo lepší mít v~záhlaví než v~zápatí. Když totiž rychle procházíte PDF a~máte náhled na stranu v~zobrazení větším než je obrazovka, tak vidíte záhlaví, zápatí nikoliv. Možná tip pro bulletin, kde to máme stejně? Byť to je jistý standard (ještě \emph{z~historických dob}) tištěných knih, ale tam je de facto jedno, jestli se díváte při rychlém listování na horní či spodní roh stránky.

Hezké bádání a~sny v~\{A,C,G,T\}! Poslední sazební ukázka je ze str.\,185 prvního svazku.

\noindent\hfil
\fbox{\includegraphics[page=210, trim=3.9cm 5.5cm 4.6cm 8.1cm, clip, width=0.4\textwidth]{baaala1.pdf}}%


