A De Brujin gráfok tulajdonságai
A DNS szekvenálásból keletkező adatok összeillesztésére számos algoritmus használatos, többek között ilyen a De Bruijn gráf, melynek három alakját ismertetjük.
A B(n,k) De Bruijn irányított gráf jellemzője, hogy n darab k hosszúságú elemből áll. Az eredeti elmélet alapján k hosszúságú ábécé betűkből áll, viszont a DNS szekvenálás esetén k hosszúságú fraglentekről beszélhetünk. Az általános alakban két csúcs között akkor szerepel él, ha az első csúcs utolsó k-1 betűje meggyegyezik a második csúcs első k-1 betűjével.
Tulajdonságok:
A B(n,k) gráfnak nk csúcsa és nk+1 éle van.
Minden csúcsból k él fut ki, és minden csúcsba k él fut be.
Minden De Bruijn-gráf tartalmaz Hamilton-kört és zárt Euler-vonalat, ami nagyon fontos hátrány lehet a DNS assembly során. Ezek korrigálását láthatjuk a továbbiakban.
Egy Hamilton-kör törlésével a gráf összefüggő marad (azaz, ha eltekintünk az irányítástól, a gráf bármely két csúcsa között van út)
A B(n,k) De Bruijn-gráfban (n!)n k-1/nk Hamilton-kör van.
A fent megemlített tulajdonságok előnyösek a DNS assembly során, azonban azzal a kitétellel, hogy az assembly során sosem törekszünk olyan gráf megalkotására, amely zártnak mondható, sokkal inkább a DNS fragmensek egymásutániságának felállítása a cél (1. ábra).
1. ábra: A standard De Bruijn gráf alkalmazására a DNS assembly során (Bankevich et. al.)
A Standars De Bruijn algoritmus alkalmazásával a túl kis k-mer méret a gráf fragmentáltságához vezet, míg a túl nagy szakaszok összeillesztése összeesést eredményezhet olyan repetitív egységek összekapcsolódásával, amely csak matematikailag helyes, viszont biológiai értelmét tekintve nem (1. táblázat).
1.táblázat: A különböző lefedettségek esetén alkalmazott k-mer méretek hatása a gráfra
Ezen problémák kiküszöbölésére alkalmazhatunk úgynevezett Multisized De Bruijn gráfot (2. ábra), melynek alakja:
2.ábra: A, Standard De Bruijn DB(Reads, 3) a piros szaggatott vonal jelzi a Hamilton köröket, amely gyengíti az összeillesztés minőségét. B, Összeesett Standard De Bruijn DB(Reads, 3), C, Framentált De Bruijn gráf DB(Reads, 4), D, Multisized De Bruijn DB(Reads, 3, 4) eredményezi a jelen példán a legjobb összeillesztést.
A munkánk során a fent ismertetett a DNS assembly eljárásokhoz szükséges algoritmusok tesztelését végeztük bakteriális genomon, hogy eldönthessük, mely algoritmusok, milyen speciális mintákhoz a legmegfelelőbbek. Továbbá célunk ezzel kapcsolatban új algoritmusok fejlesztése. Miután pedig átfogó képet kaptunk a módszerek működési elvéről és hasznosságáról szeretnénk a már meglévő algoritmusok közül a legmegfelelőbbeket, és az általalunk fejlesztett új algoritmust saját szoftverfejlesztésünk során is alkalmazni.
Az informatikai infrastruktúra kiépítésével párhuzamosan elindult a kísérleti fejlesztés folyamata is. A de novo algoritmusok jellemzően a de Brujin módszeren alapulnak, amely segítségével sok millió/milliárd rövid szekvenciából összeépíthető egy hipotetikus genom. Első lépésben a módszert teszteltük publikusan elérhető Escherichia coli (E. coli) genomszekvencia összeépítésével. Az E. coli a laborokban széleskörűen alkalmazott törzs. Ennek köszönhetően igen jól kutatott és sok szekvencia adat áll rendelkezésünkre. Jelenleg az egyik legjobb de novo algoritmus/szoftver ami használatban van, az úgynevezett Spades, ezért a tesztelést ezzel a programmal kezdtük el. A de Brujin de novo algoritmus egyik legfőbb paramétere a k-mer hossz, ezért ennek a paraméternek a változtatására fókuszáltunk, azaz arra, hogy vajon ennek változtatása hogyan hat ki az assembly különböző tulajdonságaira. Az assembly néhány kiválasztott főbb tulajdonságának változása a k-mer méret függvényében az alábbi ábrákon látható. A node-ok a de Brujin gráfban az összeillesztett szekvenciákat jelentik. Jól megfigyelhető, hogy a k-merek méretének változása hogyan hat a node-okra. A k-merek méretének növekedésével, egyre csökken a node-ok száma, ami azt jelenti, hogy egyre kevéssé fragmentált a végeredményben kapott genom. Azonban, egy adott méret fölött már nincs jelentős változás (3. ábra).
3.ábra: A horizontális tengelyen a k-merek mérete van feltüntetve, míg a vertikális tengelyen a node-ok száma.
Érdekes megfigyelni a k-merek hogyan befolyásolják a leghosszabb összerakott node/kontig méretét (4. ábra). Inkább lépcsőzetesen növekeő hatás figyelhető meg, mint folyamatos változás. Hiába növeljük a k-merek méretét a leghosszabb kontig méretén nem lehet jelentősen változtatni ezen a mérettartományon belül (Illumina szekvenálás).
4. ábra: A horizontális tengelyen a k-merek mérete van feltüntetve, míg a vertikális tengelyen a leghosszabb node mérete.
A k-merek hosszának növelésével legjobban a node-ok medián szerinti mérete növekszik. Ez azt jelenti, hogy kevéssé fragmentált lesz a végeredményben kapott genom. A rövid kontigok mérete lesz egyre hosszabb, a leghosszabb kontigok mérete jelentősen nem változik (5. és 6. ábra).
5. ábra: A horizontális tengelyen a k-merek mérete van feltüntetve, míg a vertikális tengelyen a node-ok medián szerinti mérete.
Az N50 a de novo összeszerelés során használt általános statisztikai szám. Értékét úgy kapjuk meg, hogy az összeillesztett kontigokat sorba rendezzük méret szerint és azt vesszük N50-nek, ami a kontigok összhosszának 50%-ánál éppen kisebb. Az N50 méret a genom szekvencia folyamatosságára utal.
6.ábra: A horizontális tengelyen a k-merek mérete van feltüntetve, míg a vertikális tengelyen az összerakott genom N50 értéke.
Az assembly bizonyos statisztikáiból (k-mer eloszlás), megjósolható a minta várható genom mérete. Ahogy a 7. ábrán látható, egy mérethatáron túl ennek értéke sem közelít jelentősen a valódi genom mérethez.
7.ábra: A horizontális tengelyen a k-merek mérete van feltüntetve, míg a vertikális tengelyen az összerakott genom becsült mérete. Pirossal kiemelve a vizsgált E. coli törzs referencia szekvenciájának mérete.
A k-merek mérete jelentősen befolyásolja a számítási és memória igényét is a módszernek, ezért ezek vizsgálata abban is segít, hogy a rendelkezésünkre álló erőforrások segítségével, minél több tesztelést végrehajthassunk.
A továbbiakban tervezzük, nem csak E. coli, hanem más baktérium fajokon és törzseken is a de Brujin módszeren alapulú genom összerakási módszert. Elsősorban a Bacillus subtilis baktérium fajon ami az E. coli-tól eltérően egy Gram pozitív baktérium. Továbbá más de novo alkalmazást is tervezünk tesztelni és azokat összehasonlítani.
A következőkben a k-merek alkalmazását vizsgáltuk egy metagenomikai feladatban. A bakteriofágok a baktériumokat fertőzni képes vírusok. Jellemző, hogy bizonyos oligomer szekvenciamintázatok előfordulási gyakorisága hasonló a bakteriofágok genomjában, mint a gazdabaktérium genomjában, mely jelenség alapján előrejelezhető a bakteriofág gazdabaktériuma (species, genus vagy ezeknél magasabb taxonómiai szinten). Az alábbi kísérletben baktériumgenomokból saját magunk által összeállított adatbázison teszteltük, hogy a különböző bakteriális taxonokat fertőzni képes fágok gazda baktériumát milyen pontossággal tudjuk előre jelezni. A kísérlet során 7 különböző taxont fertőzni képes 9 különböző bakteriofág genomját térképeztük fel 5 különböző k-mer mérettel (3, 6, 9, 12, 15).
Az eredményeket a 2. táblázat tartalmazza. Az adatokból látható, hogy bizonyos fágok esetében a k-merek segítségével a különböző mintázatok előfordulási gyakorisága alapján végzett gazdabaktérium előrejelzés teljesen sikertelen, hiszen minden ilyen esetben a domain volt az a legalacsonyabb taxonómiai kategória, ahol sikerült előrejeleznünk a megfelelő gazdabaktériumot. Ez ugyanakkor nem függ a baktériumtól, sokkal inkább a fággenom sajátossága, hiszen, míg az azonos gazdabaktérium fajt fertőző PhiEaH1 esetében az előrejelzés sikertelen volt, a PhiEaH2 esetében család szintjén működött. Hasonlóképpen az Xaj24 esetében az előrejelzés sikertelen volt, míg az Xaj2-nél osztály szintjén működött. Ugyanakkor 2 fág (PhiC2, A006) esetében faj szintű azonosításra voltunk képesek.
Látható, hogy azokban az esetekben, ahol az előrejelzés valamilyen sikerrel működött, többnyire eltérés volt a különböző k-mer hosszokkal végzett előrejelzés pontossága között. Az, hogy melyik k-mer volt a legsikeresebb az előrejelzésben, függött a fággenomtól. Összefoglalásként megállapítható, hogy a metagenomikában alkalmazandó vírus-gazda előrejelzési algoritmus nem állhat kizárólag a különböző k-mer hosszok segítségével végzett mintázatkeresésből, hanem több algoritmust kell majd ötvöznünk.
2. táblázat: Bakteriofágok gazda előrejelzése különböző k-mer méretekkel. Az egyes k-mer hosszokhoz tartozó oszlopokban feltüntettük, hogy az adott k-mer mérettel az adott sorban szereplő bakteriofág gazdája mely taxonomiai kategóriában jelzett előre sikerrel, illetve zárójelben azt is, hogy milyen biztonsággal.
A továbbiakban a de novo összeszerelés (illetve ehhez hasonlóan a readek térképezésének) stratégiája az lesz, hogy elsőként feltérképezzük a genom becsült lefedettségét, majd a readek végein k-mereket (k=3-8, függ a genom lefedettségének mértékétől, vö. 1. táblázat) hasonlítunk össze véletlenszerűen, melyekből csoportokat generálunk. A csoportokban újabb 2-3 lépcsőben alcsoportokat generálunk oly módon, hogy a readek közepének irányában újabb k-merekkel való egyezést vizsgálunk. Ezt követően egy lassabb illesztő algoritmussal generáljuk a kontigokat elsőként alcsoportokon belül, majd a fel nem használt readeket ismételten illesztjük a kész kontigokra, de most alcsoportok között. Ezután a kontigok egymásra illeszthetőségét vizsgáljuk meg, ismételten a végükön a k-mer egyezések alapján, majd a kész kontigokra térképezzük a fel nem használt readeket. Ezután illesztjük össze a kontigokat.
A metagenomika esetében a k-merekkel történő mintázatvizsgálatot ki fogjuk egészíteni a G+C % mintázaton alapuló vizsgálatokkal, illetve a teljes metagenom esetében a de novo szekvenálás (és a térképezés) során használatos algoritmusokkal.
Infrastruktúra létrehozása
A projekt első munkafázisában kiépítettük az analízisekhez szükséges infrastruktúrát, amit a továbbiakban is folyamatosan fejlesztünk. Ennek alapja, egy már az Enviroinvest Zrt tulajdonában lévő nagy kapacitású szerver, amely húsz processzor maggal, negyvennyolc gigabájt memóriával és öt terabájt háttértárral rendelkezik. Ez a teljesítmény és háttértár megfelelő ahhoz, hogy a potenciális bioinformatikai szoftvereket tesztelhessük, és a teszteléshez alapvető adatokat tároljuk.
A hardver eszközökön túl, kiemelt fontosságú a számítógép operációs rendszerének megválasztása és a szoftveres környezet kialakítása is. A bioinformatikai szoftverek jelentős része a kutatói szférából eredeztethető, ahol a kutatások átláthatósága és megismételhetősége miatt fontos szempont, hogy az alkalmazások nagy része nyílt forráskódú és szabadon terjeszthető legyen. Ezért a bioinformatikai szoftverek túlnyomó része linux operációs rendszer alatt érhető el. A linux szemléletből fakadóan, további előny, hogy sok esetben egyes programok szabadon kombinálhatóak, úgynevezett pipeline-ok hozhatóak létre, és ezek a pipeline-ok egyszerre akár több adatsor feldolgozására is képesek párhuzamosan. A választásunk az Environmental Omics Bio-Linux linux disztrúbúciójára esett. Ez egy speciális Ubuntu linux disztribúció, amely bizonyos, alapvető bioinformatikai szoftvereket már előtelepítve tartalmaz. Továbbá, fontos szempont volt, hogy az Ubuntu linux a könnyen menedzselhető és a jól támogatott csomagkezelője révén, a számunkra fontos egyéb alkalmazások (pl: különféle de novo alkalmazások) is egyszerűen telepíthetőek. Ezek a tulajdonságok nagy mértékben megkönnyítik a hatékony munkavégzést.
A rendszerben meglévő alap bioinformatikai programok mellé ötvennégy további alkalmazás került telepítésre. Ezeknek a szoftvereknek egyelőre még csak a legújabb aktuális verziói érhetők el parancssoros felületen, de lehetőség van arra, hogy a későbbiekben folyamatosan megjelenő újabb verziók mellett ezeket is megtartsuk és tovább használhassuk, így biztosítva a régi eredmények újabb megismételhetőségét és azt is, hogy a verziók közötti eltérések összehasonlíthatók legyenek egy későbbi elemzés során.
Bakteriális genomok analíziséhez kidolgoztunk egy pipeline-t (8.ábra), amely során ellenőrizhetők a nyers adatfájlok minőségi és mennyiségi paraméterei. Ezután a nem megfelelő szekvenciák eltávolíthatók, így biztosítva az analízis megbízhatóságát. A jó minőségű, szűrt szekvenciákat többféle úgynevezett assembler program segítségével összeszereljük nagyobb egységekbe, majd ezeket az adatokat felhasználva meghatározzuk a végleges genomot. Ha ez a lépés is sikeres, akkor legutolsó lépésben a genomban megkeressük a funkcióval rendelkező szakaszokat (pl: géneket), azaz annotáljuk.
8.ábra: Bakteriális de novo adatfeldolgozás vázlatos felépítése
A genomösszeszerelés minőségét úgy is ellenőrizhetjük, hogy a megszűrt jó minőségű szekvenciákat visszaillesztjük az általunk meghatározott genomra. Illetve több mintát egymással is összevethetünk, és eltéréseket kereshetünk a különféle izolátumok között (9. ábra).
9.ábra: A jó minőségű szekvenciák visszaillesztése az összeszerelt genomra, illetve többféle izolátum összehasonlítása.
Jelenleg a pipeline-ban az adatok feldolgozásához a Bash parancssori értelmezőt használjuk, amely távoli hozzáférés segítségével érhető el a cég belső hálózatában található gépekről. Így a munkatársak egységesen a szerveren futó környezetben ugyanazokkal a szoftverekkel és adatokkal tudnak dolgozni. Ebben a szoftverkörnyezetben a kutatásban résztvevő munkatársak könnyen létre tudnak hozni akár egyedi pipeline-okat is, amit utána közösen tudnak tesztelni.
A különféle de novo algoritmusok statisztika elemzéséhez létrehoztunk egy webes felületet (screenshotja a 10. ábrán látható), amelyben az R programcsomag segítségével tudjuk kiértékelni a genomanalízis eredményeit.
10.ábra: Az R programcsomag webes felülete (screenshot)
A szerveren folyamatosan építjük ki a feladatoknak megfelelő adatbázisokat. Az NCBI oldaláról teljes Blast adatbázisokat töltöttünk le (nukleotid, fehérje és referencia genom), amelyekből származó információkat be tudunk építeni a parancssori pipeline-okba is. A de novo összerakások eredményeiként kapott szekvenciákat ezen adatbázisok segítségével tudjuk értelmezni. Laborunk által eddig meghatározott DNS szekvenciákból kiépített saját adatbázison is teszteltük a fentebb említett de novo genomösszerakási módszereket, és sikeresen határoztunk meg baktériumokból és fágokból származó szekvenciákat. Adatbázisunkat folyamatosan bővítjük nemzetközi adatbázisokból származó szekvenciákkal is. Első lépésben a piacvezető Illumina szekvenátorokból származó adatokkal. A gyártó gépeinek segítségével a világon rendelkezésre álló szekvenciaadatok több mint 90%-át hozták létre. Egy piacképes szoftvertermék létrehozásánál ezért kulcsfontosságú, hogy ezen adatokkal megfelelően működjön. Ennek érdekében az Illumina saját felhőszolgálatása (BaseSpace) által szabadon hozzáférhető adatok begyűjtését is elkezdtük (screenshot: 11. ábra).
11.ábra: Az Illumina cég által közzétett adatokat elérhetővé tettük a szerverünkön is. (Screenshot)
Fontos megemlíteni, hogy mind bakteriális, mind humán sejtvonalakból származó adatok is rendelkezésre állnak. Így nem csak bakteriális, hanem komplexebb élőlények genomjából származó DNS adatokkal is tudjuk majd tesztelni az általunk létrehozott pipeline-okat. Ezeken túl az NCBI/ENA/DDBJ által üzemeltettet SRA adatbázisból is elkezdtünk adatokat letölteni. Az Illumina adatok mellett célunk, hogy további, elsősorban hosszú leolvasásokra képes újabb szekvenáló platformokból származó adatokat is integráljunk az adatabázisba, elsősorban az Oxford nanopore és a Pacific Biosciences gyártókra fókuszálva.
A projekt során kidolgozásra kerül a mikrobiális markergének segítségével történő azonosításhoz szükséges pipeline. Ennek fontos előkészítő lépése, hogy letöltésre került a három legfontosabb szükséges adatszett. A bakteriális 16S rRNS Greengras adatbazis, a mikrobiális ITS szekvenciákat tartlamazó UNITE adatbázis és a 16S és 18S rRNS szekvenciákat tartalmazó SILVA adatbázis.
A szolgáltatóközponthoz szükséges szoftver fejlesztése
A feladat során állítjuk elő az elemzőszoftvert és végezzük el a bioinformatkai szolgáltató központ programozási jellegű feladatait. Elsőként megtervezzük a menürendszert, majd beépítjük a nyilvánosan elérhető (a megfelelő menük esetében hatékonyan működő) illetve (a de novo összeépítés, páros illesztés és referenciagenomra térképezés esetében) az általunk kifejlesztett algoritmusokat. A bioinformatikai központ felületének grafikus kialakítása, a próbaverzió létrehozása és az előfizetési kulcs generálása is e feladat részét képezi. A programozási feladatok alvállalkozó bevonásával történnek. E feladat két munkaszakaszt ölel fel, az első munkaszakaszban vállaltuk, hogy kiválasztjuk a feladatot végző alvállalkozót, kidolgozzuk a szoftverfejlesztés stratégiáját, illetve megkezdjük a szoftverfejlesztést.
Igényeink alapján megtervezték a szoftver architektúráját, ami Linux szerveren futó .NET Core 2 technológián alapuló WEB API komponenseket, illetve webes kliens alkalmazást jelent. Meghatározták, illetve kialakították a fejlesztéshez használt környezetet és infrastruktúrát (Visual Studio 2017 fejlesztői környezet, illetve legfrissebb Ubuntu linux virtuális szerver telepítést, valamint MySql adatbázis telepítést végeztek). A kliens alkalmazás fejlesztésére a Aurelia keretrendszert, Single Page Application technológiát választották.
A fejlesztési és tesztelési feladatok nyilvántartását egy erre a célra kialakított Redmine projektben végzi a szolgáltató. A szoftverfejlesztés során eddig megvalósult a CQS integráció, kialakult a domain architektúra, elkészült az alapvető megjelenítési terv (alap design), oldal elrendezések, logó, képek stb. Funkcionális tekintetben megvalósult a login oldal, az authentikáció és felhasználók létrehozása. Folyamatban van az adminisztrációs felületek kialakítása.
