SPAdes (software) - SPAdes (software)

SPAdes
VývojářiStátní univerzita v Petrohradu, Rusko
Akademická univerzita v Petrohradě, Rusko
University of California, San Diego, USA
Stabilní uvolnění
3.12.0 / 14. května 2018
Úložiště
Upravte to na Wikidata
Operační systémLinux, Mac OS
TypBioinformatika
Licencebezplatné použití
webová stránkacab.spbu.ru/software/spades/

SPAdes (Petrohrad genom assembler )[1] je shromáždění genomu algoritmus který byl navržen pro jednotlivé buňky a více buněk bakteriální datové sady. Proto nemusí být vhodný pro projekty velkých genomů.[1][2]

SPAdes pracuje s Ion Torrent, PacBio, Oxford Nanopore, a Illumina spárovaný konec, párové páry a jednotlivá čtení.[1]SPAdes byl integrován do Galaxie plynovody Guy Lionel a Philip Mabon.[3]

Pozadí

Studium genomu jednotlivých buněk pomůže sledovat změny, ke kterým dochází v DNA v průběhu času nebo s expozicí různým podmínkám. Navíc mnoho projektů jako Projekt lidského mikrobiomu a antibiotika objevu by velká výhoda přinesla Single-cell sekvenování (SCS).[4][5] SCS má výhodu oproti sekvenování DNA extrahované z velkého počtu buněk. Problém zprůměrování významných variace mezi buňkami lze překonat pomocí SCS.[6] Experimentální a výpočetní technologie jsou optimalizovány tak, aby umožňovaly vědcům sekvenovat jednotlivé buňky. Například amplifikace DNA extrahované z jedné buňky je jednou z experimentálních výzev. Pro maximalizaci přesnosti a kvality SCS je nutná jednotná amplifikace DNA. Bylo prokázáno, že použití více cyklů zesílení založených na žíhání a smyčkování (MALBAC ) pro amplifikaci DNA generuje menší zkreslení ve srovnání s polymerázovou řetězovou reakcí (PCR ) nebo zesílení vícenásobného posunutí (MDA).[7] Dále bylo uznáno, že výzvy, kterým SCS čelí, jsou spíše výpočetní než experimentální.[8] Aktuálně dostupný assembler, jako např Samet,[9] String Graph Assembler (SGA)[10] a EULER-SR,[11] nebyly navrženy tak, aby zvládly montáž SCS.[2] Sestavování dat z jedné buňky je obtížné kvůli nerovnoměrnému pokrytí čtením, změnám v délce vložky, vysokým úrovním chyb sekvenování a chimérický čte.[8][12][13] Proto byl k řešení těchto problémů navržen nový algoritmický přístup, SPAdes.

SPAdes montážní přístup

SPAdes používá k-mers pro sestavení iniciály de Bruijnův graf a v následujících fázích provádí graficko-teoretické operace, které jsou založeny na struktuře grafu, pokrytí a délkách sekvencí. Navíc iterativně upravuje chyby.[2]Fáze montáže v SPAdes jsou:[2]

  • Fáze 1: konstrukce montážního grafu. SPAdes zaměstnává multisized de Bruijn graf (viz níže), který detekuje a odstraňuje boule / bubliny a chimérické čtení.
  • Fáze 2: úprava k-bimeru (dvojice k-merů). Přesné vzdálenosti mezi k-mery v genomu (hrany v montážním grafu) se odhadují.
  • Fáze 3: konstrukce párového montážního grafu.
  • Fáze 4: kontig konstrukce. SPAdes výstupy contigů a umožňuje mapovat čtení zpět na jejich pozice v grafu sestavy po zjednodušení grafu (zpětné sledování).

Podrobnosti o sestavení SPAdes

Logaritmický graf pokrytí pro data sekvenování jedné buňky pro E-coli genom.[14]

SPAdes byl navržen tak, aby překonal problémy spojené se sestavením dat z jedné buňky takto:[2]

1. Nerovnoměrné pokrytí.SPAdes využívá vícestranný de Bruijnův graf, který umožňuje použití různých hodnot k. Bylo navrženo použít menší hodnoty k v oblastech s nízkým pokrytím, aby se minimalizovala fragmentace, a větší hodnoty k v oblastech s vysokým pokrytím, aby se snížilo opakované sbalení (fáze 1 výše).

2. Variabilní velikosti vložky pro čtení na spárovaném konci. SPAdes využívá základní koncept spárovaných de Bruijnových grafů. Spárovaný de Bruijn však funguje dobře na čtení spárovaných konců s pevnou velikostí vložky. Proto SPAdes odhaduje „vzdálenosti“ namísto použití „velikosti vložky“. Vzdálenost (d) čtení se spárovaným koncem je definována jako pro délku čtení L, d = velikost vložky - L. Použitím přístupu k-bimer úpravy jsou vzdálenosti přesně odhadnuty. K-bimer skládající se z k-merů „α“ a „β“ spolu s odhadovanou vzdáleností mezi nimi v genomu (α | β, d). Tento přístup rozděluje párovaná čtení na dvojice k-merů, které jsou transformovány tak, aby definovaly dvojice hran (biedges) v de Bruijnových grafech. Tyto sady biedges se podílejí na odhadu vzdáleností mezi cestami hran mezi k-mers α a β. Shlukováním je optimální odhad vzdálenosti zvolen z každého klastru (fáze 2 výše). Pro konstrukci spárovaného de Bruijnova grafu se v SPAdes (fáze 3) používají obdélníkové grafy. Přístup k obdélníkovým grafům byl poprvé představen v roce 2012[15] konstruovat spárované de Bruijnovy grafy s pochybnými vzdálenostmi.

3. Boule, tipy a chiméry. K výčnělkům a tipům dochází kvůli chybám ve středu a na konci čtení. Chimérické spojení spojuje dva nesouvisející podřetězce genomu. SPAdes je identifikuje na základě topologie grafů, délky a pokrytí v nich nerozvětvených cest. SPAdes udržuje datovou strukturu, aby bylo možné zpětně sledovat všechny opravy nebo odebrání.

SPAdes upravuje dříve použitý přístup k odstranění boulí[16] a iterativní de Bruijnův grafický přístup od Peng et al (2010)[17] a vytváří nový přístup zvaný „bulge corremoval“, který znamená korekci a odstranění boule. Algoritmus bulge corremoval lze shrnout takto: jednoduchá boule je tvořena dvěma malými a podobnými cestami (P a Q) spojujícími stejnou náboje. Pokud P je cesta bez větvení (h-cesta), pak SPAdes mapuje každou hranu v P na projekci hrany v Q a odstraní P z grafu, v důsledku čehož se zvyšuje pokrytí Q. Na rozdíl od jiných assemblerů, které používají odstraněním vypouklé boule s pevným pokrytím, SPAdes krok za krokem odstraní nebo promítne dráhy h s nízkým pokrytím. Toho je dosaženo využitím postupně se zvyšujících mezních hodnot a iterací všemi dráhami h ve vzestupném pořadí pokrytí (pro odstranění boule a chimérické odstranění) nebo délky (pro odstranění špičky). Kromě toho, aby bylo zaručeno, že žádné nové zdroje / dřezy jsou zavedeny do grafu, SPAdes odstraní h-cestu (při odstraňování chimérické h-cesty) nebo projekty (v boulovém odstranění) pouze v případě, že její počáteční a koncový vrchol mají alespoň dvě odchozí a příchozí hrany. To pomáhá odstranit h-cesty s nízkým pokrytím vyskytující se z chyb sekvencování a chimérických čtení, ale ne z opakování.

SPAdes potrubí a výkon

SPAdes se skládá z následujících nástrojů:[1]

  • Přečtěte si nástroj pro opravu chyb, BayesHammer (pro data Illumina) a IonHammer (pro data IonTorrent) .[14] V tradiční korekci chyb jsou vzácné k-mery považovány za chyby. To nelze u SCS použít z důvodu nejednotného pokrytí. Proto BayesHammer využívá pravděpodobnostní subklastrování, které zkoumá více centrálních nukleotidů, které budou lépe pokryty než ostatní podobné k-mery.[14] Tvrdilo se, že pro Escherichia coli (E-coli) Jednobuněčná datová sada, BayesHammer běží přibližně za 75 minut, zabere až 10 Gb RAM k provedení opravy chyb čtení a vyžaduje 10 GB dalšího místa na disku pro dočasné soubory.
  • Iterativní assembler genomu s krátkým čtením, SPAdes. U stejné sady dat tento krok trvá ~ 75 minut. Provedení 1. fáze trvá ~ 40% tohoto času (viz SPAdes montážní přístup výše) při použití tří iterací (k = 22, 34 a 56) a ~ 45%, 14% a 1% pro dokončení fází 2, 3 a 4. Také to vyžaduje až 5 Gb RAM k provedení montáže a potřebuje 8 GB dalšího místa na disku.
  • Korektor nesouladu (který používá BWA nářadí). Tento modul vyžaduje pro dočasné soubory nejdelší dobu (~ 120 minut) a největší další místo na disku (~ 21 Gb). Dokončení neshody sestavené sestavy vyžaduje až 9 Gb RAM E-coli soubor údajů o jedné buňce.
  • Modul pro sestavování vysoce polymorfních diploidních genomů, dipSPAdes. dipSPAdes konstruuje delší kontigy využíváním výhod divergence mezi haplomy v repetitivních oblastech genomu. Poté produkuje konstrukci konsensuálních kontigů a provádí sestavení haplotypu.

Porovnávání assemblerů

Nedávná studie[18] porovnal několik genomových asemblerů na jedné buňce E-coli Vzorky. Tito montéři jsou EULER-SR,[11] Samet,[9] SOAPdenovo,[19] Velvet-SC, EULER + Velvet-SC (E + V-SC),[16] IDBA-UD[20] a SPAdes. Bylo prokázáno, že IDBA-UD a SPAdes fungovaly nejlépe.[18] SPAdes měl největší NG50 (99 913, statistika NG50 je stejná jako N50 kromě toho, že je použita velikost genomu místo velikosti sestavy).[21] Navíc pomocí E-coli referenční genom,[22] SPAdes shromáždil nejvyšší procento genomu (97%) a nejvyšší počet úplných genů (4 071 ze 4 324).[18] Výkony montérů byly následující:[18]

  • Počet kontigů:

IDBA-UD SPAdes

  • NG50

SPAdes > IDBA-UD >>> E + V-SC> EULER-SR> Velvet> Velvet-SC> SOAPdenovo

  • Největší kontig:

IDBA-UD> SPAdes >> EULER-SR> Velvet = E + V-SC> Velvet-SC> SOAPdenovo

  • Mapovaný genom (%):

SPAdes > IDBA-UD> E + V-SC> Velvet-SC> EULER-SR> SOAPdenovo> Velvet

  • Počet nesprávných sestav:

E + V-SC = Velvet = Velvet-SC SPADes

Viz také

Reference

  1. ^ A b C d http://spades.bioinf.spbau.ru/release3.0.0/manual.html
  2. ^ A b C d E Bankevich A; Nurk S; Antipov D; Gurevič AA; Dvorkin M; Kulikov AS; Lesin VM; Nikolenko SI; Pham S; Prjibelski AD; Pyshkin AV; Sirotkin AV; Vyahhi N; Tesler G; Alekseyev MA; Pevzner PA. (2012). „SPAdes: nový algoritmus sestavování genomu a jeho aplikace na sekvenování jednotlivých buněk“. Journal of Computational Biology. 19 (5): 455–477. doi:10.1089 / cmb.2012.0021. PMC  3342519. PMID  22506599.
  3. ^ Přístřešek na Galaxy
  4. ^ Gill S; Pop M; Deboy R; Eckburg P; Turnbaugh P; Samuel B; Gordon J; Relman D; Fraser-Liggett C; Nelson K (2006). „Metagenomická analýza lidského mikrobiomu distálního střeva“. Věda. 312 (5778): 1355–1359. Bibcode:2006Sci ... 312.1355G. doi:10.1126 / science.1124234. PMC  3027896. PMID  16741115.
  5. ^ Li J; Vederas J (2009). „Objevování drog a přírodní produkty: konec doby nebo nekonečné hranice?“ (PDF). Věda. 325 (5937): 161–165. Bibcode:2009Sci ... 325..161L. doi:10.1126 / science.1168243. PMID  19589993. S2CID  206517350.
  6. ^ Lu S; Zong C; Ventilátor W; Yang M; Li J; Chapman A; Zhu P; Hu X; Xu L; Yan L; F B; Qiao J; Tang F; Li R; Xie X (2012). „Sondování meiotické rekombinace a aneuploidie jednotlivých spermií sekvenováním celého genomu“. Věda. 338 (6114): 1627–1630. Bibcode:2012Sci ... 338.1627L. doi:10.1126 / science.1229112. PMC  3590491. PMID  23258895.
  7. ^ http://news.harvard.edu/gazette/story/2013/01/one-cell-is-all-you-need/
  8. ^ A b Rodrigue S; Malmstrom RR; Berlin AM; Birren BW; Henn MR; Chisholm SW (2009). „Amplifikace celého genomu a de novo shromáždění jednotlivých bakteriálních buněk“. PLOS ONE. 4 (9): e6864. Bibcode:2009PLoSO ... 4.6864R. doi:10,1371 / journal.pone.0006864. PMC  2731171. PMID  19724646.
  9. ^ A b Zerbino D; Birney E (2008). "Velvet: algoritmy pro de novo sestavení krátkého čtení pomocí de Bruijnových grafů". Výzkum genomu. 18 (5): 821–829. doi:10.1101 / gr.074492.107. PMC  2336801. PMID  18349386.
  10. ^ Simpson JT; Durbin R (2012). „Efektivní de novo shromažďování velkých genomů pomocí komprimovaných datových struktur“. Výzkum genomu. 22 (3): 549–556. doi:10,1101 / gr.126953.111. PMC  3290790. PMID  22156294.
  11. ^ A b Pevzner PA; Tang H; Waterman MS (2001). „Euleriánský přístup k sestavě fragmentů DNA. Sborník Národní akademie věd Spojených států amerických. 98 (17): 9748–9753. Bibcode:2001PNAS ... 98.9748P. doi:10.1073 / pnas.171285098. PMC  55524. PMID  11504945.
  12. ^ Medvedev P; Scott E; Kakaradov B; Pevzner P (2011). „Oprava chyby vysoce výkonných sekvenčních datových sad s nejednotným pokrytím“ (PDF). Bioinformatika. 27 (13): i137–141. doi:10.1093 / bioinformatika / btr208. PMC  3117386. PMID  21685062.
  13. ^ Ishoey T; Woyke T; Stepanauskas R; Novotný M; Lasken RS (2008). „Genomické sekvenování jednotlivých mikrobiálních buněk ze vzorků prostředí“. Současný názor v mikrobiologii. 11 (3): 198–204. doi:10.1016 / j.mib.2008.05.006. PMC  3635501. PMID  18550420.
  14. ^ A b C Nikolenko SI; Korobeynikov AI; Alekseyev MA. (2012). „BayesHammer: Bayesovské shlukování pro korekci chyb v sekvenování jednotlivých buněk“ (PDF). BMC Genomics. 14 (Suppl 1): S7. arXiv:1211.2756. doi:10.1186 / 1471-2164-14-S1-S7. PMC  3549815. PMID  23368723.
  15. ^ Vyahhi N; Pham SK; Pevzner P (2012). Od de Bruijnových grafů po obdélníkové grafy pro shromáždění genomu. Přednášky z bioinformatiky. Přednášky z informatiky. 7534. 249–261. doi:10.1007/978-3-642-33122-0_20. ISBN  978-3-642-33121-3.
  16. ^ A b Chitsaz H; Yee-Greenbaum JL; Tesler G; Lombardo MJ; Dupont CL; Badger JH; Novotný M; Rusch DB; Fraser LJ; Gormley NA; Schulz-Trieglaff O; Smith GP; Evers DJ; Pevzner PA; Lasken RS (2011). „Efektivní de novo sestavení jednobuněčných bakteriálních genomů ze souborů dat s krátkým přečtením“. Nat Biotechnol. 29 (10): 915–921. doi:10.1038 / nbt.1966. PMC  3558281. PMID  21926975.
  17. ^ Peng Y .; Leung H.C.M .; Yiu S.-M; Chin FYL (2010). IDBA - praktický iterativní de Bruijnův graf de novo assembler. Přednáška Notes Comput. Sci. Přednášky z informatiky. 6044. str.426–440. Bibcode:2010LNCS.6044..426P. CiteSeerX  10.1.1.157.195. doi:10.1007/978-3-642-12683-3_28. hdl:10722/129571. ISBN  978-3-642-12682-6.
  18. ^ A b C d Gurevič A; Saveliev V; Vyahhi N; Tesler G (2013). „QUAST: nástroj pro hodnocení kvality pro genomové sestavy“ (PDF). Bioinformatika. 29 (8): 1072–1075. doi:10.1093 / bioinformatika / btt086. PMC  3624806. PMID  23422339.
  19. ^ Li R; Zhu H; Ruan J; Qian W; Fang X; Shi Z; Li Y; Li S; Shan G; Kristiansen K; Li S; Yang H; Wang J; Wang J (2010). „Sestavení lidských genomů de novo s masivně paralelním sekvenováním krátkého čtení“ (PDF). Výzkum genomu. 20 (2): 265–272. doi:10.1101 / gr.097261.109. PMC  2813482. PMID  20019144.
  20. ^ Peng Y; Leung HCM; Yiu SM; Chin FYL (2012). „IDBA-UD: de novo assembler pro jednobuněčná a metagenomická sekvenční data s velmi nerovnoměrnou hloubkou“ (PDF). Bioinformatika. 28 (11): 1–8. doi:10.1093 / bioinformatika / bts174. PMID  22495754.
  21. ^ http://bioinf.spbau.ru/spades/
  22. ^ Blattner FR; Plunkett G; Bloch C; Perna N; Burland V; Riley M; Collado-Vides J; Glasner J; Rode C; Mayhew G; Gregor J; Davis N; Kirkpatrick H; Goeden M; Rose D; Mau B; Shao Y (1997). „Kompletní genomová sekvence Escherichia coli K-12“. Věda. 277 (5331): 1453–1462. doi:10.1126 / science.277.5331.1453. PMID  9278503.