De novo sekvenátory - De novo sequence assemblers

De novo sekvenátory jsou typem programu, který se sestavuje krátce nukleotid sekvence na delší bez použití odkazu genom. Ty se nejčastěji používají v bioinformatických studiích k sestavení genomů nebo přepisy. Jsou dva běžné typy de novo assemblerů chamtivý algoritmus montéři a De Bruijnův graf montéři.

Typy montérů de novo

Existují dva typy algoritmů, které tito assemblery běžně využívají: chamtivý, jehož cílem je místní optima a algoritmy grafových metod, jejichž cílem je globální optima. Různá asembleri jsou šitá na míru konkrétním potřebám, jako je shromažďování (malých) bakteriálních genomů, (velkých) eukaryotických genomů nebo transkriptomů.

Chamtiví sestavovatelé algoritmů jsou assemblery, které nacházejí místní optima v zarovnání menších čte. Chamtiví sestavovatelé algoritmů obvykle obsahují několik kroků: 1) výpočet vzdálenosti párů čtení, 2) shlukování čtení s největším překrytím, 3) sestavení překrývajících se čtení do větších kontigy a 4) opakujte. Tyto algoritmy obvykle nefungují dobře pro větší sady čtení, protože snadno nedosahují globálního optima v sestavě a fungují dobře na sady čtení, které obsahují oblasti opakování.[1] Rané de novo sekvenční assemblery, jako je SEQAID[2] (1984) a CAP[3] (1992), použili chamtivé algoritmy, jako jsou algoritmy překrývání rozložení a konsensu (OLC). Tyto algoritmy naleznou překrytí všech čtení, pomocí překrytí určují rozložení (nebo obklady) čtení a poté vytvářejí konsenzuální sekvenci. Některé programy, které používaly algoritmy OLC, obsahovaly filtraci (k odstranění párů čtení, které se nepřekrývají) a heuristické metody ke zvýšení rychlosti analýz.

Assemblerové metody[4] přicházejí ve dvou variantách: string a De Bruijn. Řetězcový graf a De Bruijnův graf metody assemblerů byly představeny na a DIMACY[5] workshop v roce 1994 Waterman[6] a Gene Myers.[7] Tyto metody představovaly důležitý krok vpřed v sestavení sekvence, protože oba používají algoritmy k dosažení globálního optima namísto lokálního optima. Zatímco obě tyto metody pokročily směrem k lepším sestavám, metoda grafu De Bruijn se stala nejpopulárnější ve věku sekvenování nové generace. Během sestavování grafu De Bruijn jsou čtení rozděleny na menší fragmenty určené velikosti, k. The k-mers se poté použijí jako uzly v sestavě grafu. Uzly, které se do určité míry překrývají (obvykle k-1), jsou pak spojeny hranou. Assembler poté vytvoří sekvence na základě De Bruijnova grafu. Sestavovače grafů De Bruijn obvykle fungují lépe na větších sadách čtení než chamtivé sestavovače algoritmů (zvláště když obsahují oblasti opakování).

Běžně používané programy

Seznam de-novo assemblerů
názevPopis /

Metodologie

TechnologieAutorPředstavil /

Naposledy aktualizováno

Licence*Domovská stránka
Propastparalelní asembler sekvencí spárovaných konců určený pro velké genomové sestavení krátkých čtení (genomová a transkriptomická), využívají Bloomův filtr k grafu De BruijnIllumina[8][9]2009 / 2017OSodkaz
AFEAP klonování Lasergene Genomics Suitepřesná a účinná metoda pro sestavování velkých sekvencí DNAdvě kola PCR, následovaná ligací lepivých konců fragmentů DNA[10]2017 / 2018Codkaz
OBJEVTEpárovaná koncová čtení bez PCR (nástupce ALLPATHS-LG)Illumina (MiSeq nebo HiSeq 2500)[11]2014OSodkaz
Assembler DNA Baser SequenceSestavení sekvence DNA s automatickým oříznutím konce a korekcí nejednoznačnosti. Zahrnuje volajícího základny.Sanger, IlluminaHeracle BioSoft SRL2018.09C (69 $)NA
DNASTAR Lasergene Genomics Suite(velké) genomy, exomy, transkriptomy, metagenomy, ESTIllumina, ABI SOLiD, Roche 454, Ion Torrent, Solexa, SangerDNASTAR2007 / 2016Codkaz
Newblergenomy, EST454, Sanger454 biologických věd2004/2012Codkaz
PhrapgenomySanger, 454, SolexaZelená, P.1994 / 2008C / NC-Aodkaz
PlassAssembler na úrovni proteinu: sestavuje sekvenční čtení přeložené do šesti rámců do proteinových sekvencíIllumina[12]2018 / 2019OSodkaz
Paprseksada assemblerů včetně de novo, metagenomických, ontologických a taxonomických profilů; používá graf De Bruijn[13]2010OSodkaz
SPAdes(malé) genomy, jednobuněčnéIllumina, Solexa, Sanger, 454, Ion Torrent, PacBio, Oxford Nanopore[14]2012 / 2019OSodkaz
Samet(malé) genomySanger, 454, Solexa, SOLiD[15]2007 / 2011OSodkaz
HGAPGenomy do 130 MBPacBio čte[16]2011 / 2015OSodkaz
SokolDiploidní genomyPacBio čte[17]2014 / 2017OSodkaz
MůžešMalé a velké, haploidní / diploidní genomyPacBio / Oxford Nanopore čte[18]2001 / 2018OSodkaz
MaSuRCAHaploidní / diploidní genomy jakékoli velikostiData Illumina a PacBio / Oxford Nanopore, starší údaje 454 a Sanger[19]2011 / 2018OSodkaz
ZávěsMalé mikrobiální genomyPacBio / Oxford Nanopore čte[20]2016 / 2018OSodkaz
Trojicetranskriptomové sestavy podle de Bruijnova grafuIllumina RNA-seq[21]2011odkaz
*Licence: OS = Open Source; C = komerční; C / NC-A = Komerční, ale zdarma pro nekomerční a akademické pracovníky

Různé assemblery jsou navrženy pro různé typy technologií čtení. Čtení z technologií druhé generace (nazývané technologie krátkého čtení), jako je Illumina, jsou obvykle krátké (s délkami řádově 50-200 základních párů) a mají chybovost kolem 0,5-2%, přičemž chyby jsou hlavně chyby substituce. Čtení z technologií třetí generace, jako je PacBio, a technologií čtvrté generace, jako je Oxford Nanopore (nazývané technologie dlouhého čtení), jsou delší s délkami čtení obvykle v řádu tisíců nebo desítek tisíc a mají mnohem vyšší chybovost kolem 10–20%, přičemž chyby jsou hlavně vkládání a mazání. To vyžaduje různé algoritmy pro sestavení od technologií pro krátké a dlouhé čtení.

Assemblathon

Existuje mnoho programů pro sestavení sekvencí de novo a mnoho z nich bylo porovnáno v Assemblathonu. Assemblathon je pravidelné společné úsilí k testování a vylepšování četných dostupných assemblerů. Doposud byla dokončena dvě shromáždění (2011 a 2013) a třetí probíhá (k dubnu 2017). Týmy vědců z celého světa volí program a sestavují simulované genomy (Assemblathon 1) a genomy modelových organismů, jejichž dříve byly sestaveny a anotovány (Assemblathon 2). Sestavy jsou poté porovnány a vyhodnoceny pomocí mnoha metrik.

Assemblathon 1

Assemblathon 1[22] proběhlo v roce 2011 a představovalo 59 shromáždění od 17 různých skupin a organizátorů. Cílem tohoto Assembalthonu bylo co nejpřesněji a úplně sestavit genom, který se skládal ze dvou haplotypů (každý se třemi chromozomy 76,3, 18,5 a 17,7 Mb), které byly generovány pomocí Evolveru. K posouzení sestav byla použita řada metrik, včetně: NG50 (bod, ve kterém je dosaženo 50% celkové velikosti genomu, když jsou délky lešení sečteny od nejdelší po nejkratší), LG50 (počet lešení, která jsou větší než nebo stejná délka N50), pokrytí genomu a míra substituční chyby.

  • Porovnávaný software: ABySS, Phusion2, phrap, Velvet, SOAPdenovo, PRICE, ALLPATHS-LG
  • Analýza N50: shromáždění Plant Genome Assembly Group (s využitím assembleru Meraculous) a ALLPATHS, Broad Institute, USA (s použitím ALLPATHS-LG) si vedly nejlépe v této kategorii, řádově nad ostatními skupinami. Tyto sestavy dosáhly N50> 8 000 000 základen.
  • Pokrytí genomu shromážděním: pro tuto metriku nejlépe fungovalo shromáždění BGI přes SOAPdenovo, přičemž bylo pokryto 98,8% celkového genomu. Všichni montéři si v této kategorii vedli relativně dobře, přičemž všechny skupiny kromě tří měly pokrytí 90% a vyšší a nejnižší celkové pokrytí bylo 78,5% (odbor Comp. Sci., University of Chicago, USA prostřednictvím Kiki).
  • Substituční chyby: sestavu s nejnižší mírou substituční chyby předložil tým Wellcome Trust Sanger Institute ve Velké Británii pomocí softwaru SGA.
  • Celkově: Nikdo z montérů si ve všech kategoriích nevedl výrazně lépe v ostatních. Zatímco někteří asembleri vynikali v jedné kategorii, v jiných ne, což naznačuje, že v kvalitě softwaru asemblerů stále existuje velký prostor pro zlepšení.

Assemblathon 2

Assemblathon 2[23] vylepšeno na Assemblathon 1 začleněním genomů vícečetných obratlovců (pták (Mumesittacus undulatus), ryba (Zebra Maylandia) a had (Boa constrictor constrictor)) s genomy odhadovanými na 1,2, 1,0 a 1,6 Gbp na délku) a hodnocení více než 100 metrik. Každý tým dostal čtyři měsíce na to, aby shromáždil svůj genom z dat další generace (NGS), včetně Illumina a Roche 454 data sekvence.

  • Porovnávaný software: ABySS, ALLPATHS-LG, PRICE, Ray a SOAPdenovo
  • Analýza N50: pro shromáždění ptačího genomu měly týmy Baylor College of Medicine Human Genome Sequencing Center a ALLPATHS nejvyšší NG50, a to více než 16 000 000, respektive 14 000 000 bp.
  • Přítomnost jádrových genů: Většina sestavení si v této kategorii vedla dobře (~ 80% nebo vyšší), přičemž pouze jedna klesla na něco přes 50% v sestavě jejich genomu ptáků (Wayne State University prostřednictvím HyDA).
  • Celkově: Centrum pro sekvenování lidského genomu Baylor College of Medicine s využitím různých metod montáže (SeqPrep, KmerFreq, Quake, BWA, Newbler, ALLPATHS-LG, Atlas-Link, Atlas-GapFill, Phrap, CrossMatch, Velvet, BLAST, a BLASR) předváděly to nejlepší pro sestavy ptáků a ryb. U sestavy hadího genomu si nejlépe vedl Wellcome Trust Sanger Institute využívající SGA. U všech sestav předložily SGA, BCM, Meraculous a Ray konkurenční sestavy a hodnocení. Výsledky mnoha zde popsaných sestavení a hodnocení naznačují, že zatímco jeden assembler může fungovat dobře u jednoho druhu, u jiného nemusí. Autoři předkládají několik návrhů na sestavení: 1) použít více než jeden assembler, 2) použít více než jednu metriku pro hodnocení, 3) vybrat assembler, který vyniká v metrikách většího zájmu (např. N50, pokrytí), 4) nízké N50 nebo velikosti sestav se nemusí týkat, v závislosti na potřebách uživatele, a 5) vyhodnotit úrovně heterozygotnosti v sledovaném genomu.

Viz také

Reference

  1. ^ J. Bang-Jensen; G. Gutin; A. Yeo (2004). "Když chamtivý algoritmus selže". Diskrétní optimalizace. 1 (2): 121–127. doi:10.1016 / j.disopt.2004.03.007.
  2. ^ Peltola, Hannu; Söderlund, Hans; Ukkonen, Esko (11.01.1984). „SEQAID: program sestavování sekvence DNA založený na matematickém modelu“. Výzkum nukleových kyselin. 12 (1 část 1): 307–321. doi:10.1093 / nar / 12.1 Část 1.307. ISSN  0305-1048. PMC  321006. PMID  6320092.
  3. ^ Huang, Xiaoqiu (01.09.1992). Msgstr "Program sestavy contig založený na citlivé detekci překrytí fragmentů". Genomika. 14 (1): 18–25. doi:10.1016 / S0888-7543 (05) 80277-0. PMID  1427824.
  4. ^ Compeau, Phillip EC, Pavel A. Pevzner a Glenn Tesler (2011). „Jak aplikovat de Bruijnovy grafy na genomové seskupení“. Přírodní biotechnologie. 29 (11): 987–991. doi:10.1038 / nbt.2023. PMC  5531759. PMID  22068540.CS1 maint: používá parametr autoři (odkaz)
  5. ^ „Workshop DIMACS o kombinatorických metodách pro mapování a sekvenování DNA“. Říjen 1994.
  6. ^ Idury, R. M .; Waterman, M. S. (01.01.1995). Msgstr "Nový algoritmus pro sestavení sekvence DNA". Journal of Computational Biology. 2 (2): 291–306. CiteSeerX  10.1.1.79.6459. doi:10.1089 / cmb.1995.2.291. ISSN  1066-5277. PMID  7497130.
  7. ^ Myers, E. W. (01.01.1995). "Směrem ke zjednodušení a přesné formulaci fragmentů". Journal of Computational Biology. 2 (2): 275–290. doi:10.1089 / cmb.1995.2.275. ISSN  1066-5277. PMID  7497129.
  8. ^ Simpson, Jared T .; et al. (2009). "ABySS: paralelní assembler pro data krátkých sekvencí čtení". Výzkum genomu. 19 (6): 1117–1123. doi:10.1101 / gr.089532.108. PMC  2694472. PMID  19251739.
  9. ^ Birol, Inanç; et al. (2009). „Sestava transkriptomu de novo s ABySS“. Bioinformatika. 25 (21): 2872–2877. doi:10.1093 / bioinformatika / btp367. PMID  19528083.
  10. ^ Zeng, Fanli; Zang, Jinping; Zhang, Suhua; Hao, Zhimin; Dong, Jingao; Lin, Yibin (2017-11-14). „AFEAP klonování: přesná a účinná metoda pro velké sestavení sekvence DNA“. BMC biotechnologie. 17 (1): 81. doi:10.1186 / s12896-017-0394-x. ISSN  1472-6750. PMC  5686892. PMID  29137618.
  11. ^ Láska, R. Rebecca; Weisenfeld, Neil I .; Jaffe, David B .; Besansky, Nora J .; Neafsey, Daniel E. (prosinec 2016). „Vyhodnocení DISCOVAR de novo pomocí vzorku komárů pro cenově výhodné sestavení genomu s krátkým čtením“. BMC Genomics. 17 (1): 187. doi:10.1186 / s12864-016-2531-7. ISSN  1471-2164. PMC  4779211. PMID  26944054.
  12. ^ Steinegger, Martin; Mirdita, pilot; Söding, Johannes (2019-06-24). „Sestavení na úrovni proteinů mnohonásobně zvyšuje regeneraci proteinové sekvence z metagenomických vzorků“. Přírodní metody. 16 (7): 603–606. doi:10.1038 / s41592-019-0437-4. hdl:21.11116 / 0000-0003-E0DD-7. PMID  31235882.
  13. ^ Boisvert, Sébastien, François Laviolette a Jacques Corbeil (2010). „Ray: simultánní shromažďování čtení ze směsi vysoce výkonných sekvenčních technologií“. Journal of Computational Biology. 17 (11): 1519–1533. doi:10.1089 / cmb.2009.0238. PMC  3119603. PMID  20958248.CS1 maint: používá parametr autoři (odkaz)
  14. ^ Bankevich, Anton; Nurk, Sergey; Antipov, Dmitrij; Gurevich, Alexey A .; Dvorkin, Michail; Kulikov, Alexander S .; Lesin, Valery M .; Nikolenko, Sergey I .; Pham, Son; Prjibelski, Andrey D .; Pyshkin, Alexey V. (květen 2012). „SPAdes: Nový algoritmus shromáždění genomu a jeho aplikace při sekvenování jednotlivých buněk“. Journal of Computational Biology. 19 (5): 455–477. doi:10.1089 / cmb.2012.0021. ISSN  1066-5277. PMC  3342519. PMID  22506599.
  15. ^ Zerbino, D.R .; Birney, E. (2008-02-21). „Velvet: Algorithms for de novo short read assembly using de Bruijn graphs“. Výzkum genomu. 18 (5): 821–829. doi:10.1101 / gr.074492.107. ISSN  1088-9051. PMC  2336801. PMID  18349386.
  16. ^ Chin, Chen-Shan, David H. Alexander, Patrick Marks, Aaron A. Klammer, James Drake, Cheryl Heiner, Alicia Clum a kol. „Nehybridní, hotové sestavy mikrobiálního genomu z dlouho čtených dat sekvenování SMRT.“ Přírodní metody 10, č. 6 (2013): 563-569. Dostupný online
  17. ^ Chin, Chen-Shan, Paul Peluso, Fritz J. Sedlazeck, Maria Nattestad, Gregory T. Concepcion, Alicia Clum, Christopher Dunn a kol. „Fázovaná sestava diploidního genomu s jednokomolekulárním sekvenováním v reálném čase.“ Přírodní metody 13, č. 12 (2016): 1050-1054. K dispozici zde
  18. ^ Koren, Sergey, Brian P. Walenz, Konstantin Berlin, Jason R. Miller, Nicholas H. Bergman a Adam M. Phillippy. „Canu: škálovatelné a přesné sestavení s dlouhým čtením pomocí adaptivního vážení k-mer a opakované separace.“ Výzkum genomu 27, č. 5 (2017): 722-736. K dispozici zde
  19. ^ Zimin, Aleksey V .; Marçais, Guillaume; Puiu, Daniela; Roberts, Michael; Salzberg, Steven L .; Yorke, James A. (listopad 2013). „Sestavovač genomu MaSuRCA“. Bioinformatika. 29 (21): 2669–2677. doi:10.1093 / bioinformatika / btt476. ISSN  1367-4803. PMC  3799473. PMID  23990416.
  20. ^ Kamath, Govinda M., Ilan Shomorony, Fei Xia, Thomas A. Courtade a N. Tse David. „ZÁVĚS: sestavení s dlouhým čtením dosahuje optimálního rozlišení opakování.“ Výzkum genomu 27, č. 5 (2017): 747-756. K dispozici zde
  21. ^ Grabherr, Manfred G .; et al. (2011). „Kompletní transkriptomová sestava z dat RNA-Seq bez referenčního genomu“. Přírodní biotechnologie. 29 (7): 644–652. doi:10.1038 / nbt.1883. PMC  3571712. PMID  21572440.
  22. ^ Earl, Dent; et al. (2011). „Assemblathon 1: konkurenceschopné vyhodnocení metod sestavování krátkého čtení de novo“. Výzkum genomu. 21 (12): 2224–2241. doi:10.1186 / 2047-217X-2-10. PMC  3844414. PMID  23870653.
  23. ^ Bradnam, Keith R .; et al. (2013). „Assemblathon 2: hodnocení de novo metod montáže genomu u tří druhů obratlovců“. GigaScience. 2 (1): 10. arXiv:1301.5406. doi:10.1186 / 2047-217X-2-10. PMC  3844414. PMID  23870653.