{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T05:13:31Z","timestamp":1782191611798,"version":"3.54.5"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2021,1,20]],"date-time":"2021-01-20T00:00:00Z","timestamp":1611100800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"European Center for Bioinformatics an Genomics project","award":["POIR.04.02.00-30-A004\/16"],"award-info":[{"award-number":["POIR.04.02.00-30-A004\/16"]}]},{"DOI":"10.13039\/501100008530","name":"European Regional Development Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008530","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,7,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>There are very few methods for de novo genome assembly based on the overlap graph approach. It is considered as giving more exact results than the so-called de Bruijn graph approach but in much greater time and of much higher memory usage. It is not uncommon that assembly methods involving the overlap graph model are not able to successfully compute greater datasets, mainly due to memory limitation of a computer. This was the reason for developing in last decades mainly de Bruijn-based assembly methods, fast and fairly accurate. However, the latter methods can fail for longer or more repetitive genomes, as they decompose reads to shorter fragments and lose a part of information. An efficient assembler for processing big datasets and using the overlap graph model is still looked out.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We propose a new genome-scale de novo assembler based on the overlap graph approach, designed for short-read sequencing data. The method, ALGA, incorporates several new ideas resulting in more exact contigs produced in short time. Among these ideas, we have creation of a sparse but quite informative graph, reduction of the graph including a procedure referring to the problem of minimum spanning tree of a local subgraph, and graph traversal connected with simultaneous analysis of contigs stored so far. What is rare in genome assembly, the algorithm is almost parameter-free, with only one optional parameter to be set by a user. ALGA was compared with nine state-of-the-art assemblers in tests on genome-scale sequencing data obtained from real experiments on six organisms, differing in size, coverage, GC content and repetition rate. ALGA produced best results in the sense of overall quality of genome reconstruction, understood as a good balance between genome coverage, accuracy and length of resulting sequences. The algorithm is one of tools involved in processing data in currently realized national project Genomic Map of Poland.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>ALGA is available at http:\/\/alga.put.poznan.pl.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btab005","type":"journal-article","created":{"date-parts":[[2021,1,6]],"date-time":"2021-01-06T20:40:29Z","timestamp":1609965629000},"page":"1644-1651","source":"Crossref","is-referenced-by-count":13,"title":["Genome-scale <i>de novo<\/i> assembly using ALGA"],"prefix":"10.1093","volume":"37","author":[{"given":"Sylwester","family":"Swat","sequence":"first","affiliation":[{"name":"Poznan University of Technology, Institute of Computing Science , 60-965 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Artur","family":"Laskowski","sequence":"additional","affiliation":[{"name":"Poznan University of Technology, Institute of Computing Science , 60-965 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Badura","sequence":"additional","affiliation":[{"name":"Poznan University of Technology, Institute of Computing Science , 60-965 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wojciech","family":"Frohmberg","sequence":"additional","affiliation":[{"name":"Poznan University of Technology, Institute of Computing Science , 60-965 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pawel","family":"Wojciechowski","sequence":"additional","affiliation":[{"name":"Poznan University of Technology, Institute of Computing Science , 60-965 Poznan, Poland"},{"name":"Institute of Bioorganic Chemistry, Polish Academy of Sciences , 61-704 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksandra","family":"Swiercz","sequence":"additional","affiliation":[{"name":"Poznan University of Technology, Institute of Computing Science , 60-965 Poznan, Poland"},{"name":"Institute of Bioorganic Chemistry, Polish Academy of Sciences , 61-704 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9863-5412","authenticated-orcid":false,"given":"Marta","family":"Kasprzak","sequence":"additional","affiliation":[{"name":"Poznan University of Technology, Institute of Computing Science , 60-965 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jacek","family":"Blazewicz","sequence":"additional","affiliation":[{"name":"Poznan University of Technology, Institute of Computing Science , 60-965 Poznan, Poland"},{"name":"Institute of Bioorganic Chemistry, Polish Academy of Sciences , 61-704 Poznan, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,1,20]]},"reference":[{"key":"2023051709552527300_btab005-B1","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1016\/j.cell.2016.05.063","article-title":"1,135 genomes reveal the global pattern of polymorphism in Arabidopsis thaliana","volume":"166","year":"2016","journal-title":"Cell"},{"key":"2023051709552527300_btab005-B2","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.tibtech.2018.07.013","article-title":"Single-molecule sequencing: towards clinical applications","volume":"37","author":"Ameur","year":"2019","journal-title":"Trends Biotechnol"},{"key":"2023051709552527300_btab005-B3","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1089\/cmb.2012.0021","article-title":"SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing","volume":"19","author":"Bankevich","year":"2012","journal-title":"J. Comput. Biol"},{"key":"2023051709552527300_btab005-B4","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/j.compbiolchem.2009.04.005","article-title":"Whole genome assembly from 454 sequencing output via modified DNA graph concept","volume":"33","author":"Blazewicz","year":"2009","journal-title":"Comput. Biol. Chem"},{"key":"2023051709552527300_btab005-B5","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1093\/bioinformatics\/18.5.652","article-title":"A heuristic managing errors for DNA sequencing","volume":"18","author":"Blazewicz","year":"2002","journal-title":"Bioinformatics"},{"key":"2023051709552527300_btab005-B6","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1016\/j.ejor.2016.06.043","article-title":"Graph algorithms for DNA sequencing - origins, current models and the future","volume":"264","author":"Blazewicz","year":"2018","journal-title":"Eur. J. Oper. Res"},{"key":"2023051709552527300_btab005-B7","doi-asserted-by":"crossref","first-page":"10.","DOI":"10.1186\/2047-217X-2-10","article-title":"Assemblathon 2: evaluating de novo methods of genome assembly in three vertebrate species","volume":"2","author":"Bradnam","year":"2013","journal-title":"GigaScience"},{"key":"2023051709552527300_btab005-B8","doi-asserted-by":"crossref","first-page":"82.","DOI":"10.1186\/1471-2105-13-82","article-title":"Readjoiner: a fast and memory efficient string graph-based sequence assembler","volume":"13","author":"Gonnella","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023051709552527300_btab005-B9","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1093\/bioinformatics\/btt086","article-title":"QUAST: quality assessment tool for genome assemblies","volume":"29","author":"Gurevich","year":"2013","journal-title":"Bioinformatics"},{"key":"2023051709552527300_btab005-B10","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1089\/cmb.1995.2.291","article-title":"A new algorithm for DNA sequence assembly","volume":"2","author":"Idury","year":"1995","journal-title":"J. Comput. Biol"},{"key":"2023051709552527300_btab005-B11","doi-asserted-by":"crossref","first-page":"302.","DOI":"10.1186\/1471-2105-15-302","article-title":"SAGE: string-overlap assembly of genomes","volume":"15","author":"Ilie","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023051709552527300_btab005-B12","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1101\/gr.170720.113","article-title":"Efficient de novo assembly of highly heterozygous genomes from whole-genome shotgun short reads","volume":"24","author":"Kajitani","year":"2014","journal-title":"Genome Res"},{"key":"2023051709552527300_btab005-B13","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/j.cell.2016.06.044","article-title":"Epigenomic diversity in a global collection of Arabidopsis thaliana accessions","volume":"166","author":"Kawakatsu","year":"2016","journal-title":"Cell"},{"key":"2023051709552527300_btab005-B14","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01188580","article-title":"Combinatorial algorithms for DNA sequence assembly","volume":"13","author":"Kececioglu","year":"1995","journal-title":"Algorithmica"},{"key":"2023051709552527300_btab005-B15","doi-asserted-by":"crossref","first-page":"1674","DOI":"10.1093\/bioinformatics\/btv033","article-title":"MEGAHIT: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph","volume":"31","author":"Li","year":"2015","journal-title":"Bioinformatics"},{"key":"2023051709552527300_btab005-B16","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1093\/bioinformatics\/bts690","article-title":"Musket: a multistage k-mer spectrum-based error corrector for Illumina sequence data","volume":"29","author":"Liu","year":"2013","journal-title":"Bioinformatics"},{"key":"2023051709552527300_btab005-B17","doi-asserted-by":"crossref","first-page":"18.","DOI":"10.1186\/2047-217X-1-18","article-title":"SOAPdenovo2: an empirically improved memory-efficient short-read de novo assembler","volume":"1","author":"Luo","year":"2012","journal-title":"GigaScience"},{"key":"2023051709552527300_btab005-B18","first-page":"1508","article-title":"Determination of the nucleotide sequence of DNA using hybridization with oligonucleotides. A new method","volume":"303","author":"Lysov","year":"1988","journal-title":"Dokl. Akad. Nauk. SSSR"},{"key":"2023051709552527300_btab005-B19","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1373\/clinchem.2016.266536","article-title":"Next-generation sequencing for biodefense: biothreat detection, forensics, and the clinic","volume":"65","author":"Minogue","year":"2019","journal-title":"Clin. Chem"},{"key":"2023051709552527300_btab005-B20","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1093\/bioinformatics\/btx648","article-title":"SAGE2: parallel human genome assembly","volume":"34","author":"Molnar","year":"2018","journal-title":"Bioinformatics"},{"key":"2023051709552527300_btab005-B21","doi-asserted-by":"crossref","first-page":"2196","DOI":"10.1126\/science.287.5461.2196","article-title":"Whole-genome assembly of Drosophila","volume":"287","author":"Myers","year":"2000","journal-title":"Science"},{"key":"2023051709552527300_btab005-B22","doi-asserted-by":"crossref","first-page":"1277.","DOI":"10.3389\/fmicb.2019.01277","article-title":"Impact of host DNA and sequencing depth on the taxonomic resolution of whole metagenome sequencing for microbiome analysis","volume":"10","author":"Pereira-Marques","year":"2019","journal-title":"Front. Microbiol"},{"key":"2023051709552527300_btab005-B23","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/07391102.1989.10507752","article-title":"l-tuple DNA sequencing: computer analysis","volume":"7","author":"Pevzner","year":"1989","journal-title":"J. Biomol. Struct. Dyn"},{"key":"2023051709552527300_btab005-B24","doi-asserted-by":"crossref","first-page":"9748","DOI":"10.1073\/pnas.171285098","article-title":"An Eulerian path approach to DNA fragment assembly","volume":"98","author":"Pevzner","year":"2001","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023051709552527300_btab005-B25","first-page":"227","volume-title":"Gene Prediction, Series Methods in Molecular Biology","author":"Seppey","year":"2019"},{"key":"2023051709552527300_btab005-B26","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1101\/gr.126953.111","article-title":"Efficient de novo assembly of large genomes using compressed data structures","volume":"22","author":"Simpson","year":"2012","journal-title":"Genome Res"},{"key":"2023051709552527300_btab005-B27","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0140-6736(14)62453-3","article-title":"UK gears up to decode 100000 genomes from NHS patients","volume":"385","author":"Siva","year":"2015","journal-title":"Lancet"},{"key":"2023051709552527300_btab005-B28","doi-asserted-by":"crossref","first-page":"e0202355.","DOI":"10.1371\/journal.pone.0202355","article-title":"GRASShopPER \u2013 an algorithm for de novo assembly based on GPU alignments","volume":"13","author":"Swiercz","year":"2018","journal-title":"PLoS One"},{"key":"2023051709552527300_btab005-B29","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1101\/gr.074492.107","article-title":"Velvet: algorithms for de novo short read assembly using de Bruijn graphs","volume":"18","author":"Zerbino","year":"2008","journal-title":"Genome Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab005\/37802044\/btab005.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/12\/1644\/50361259\/btab005.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/12\/1644\/50361259\/btab005.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T10:38:08Z","timestamp":1684319888000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/12\/1644\/6104855"}},"subtitle":[],"editor":[{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2021,1,20]]},"references-count":29,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2021,7,19]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab005","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,6,15]]},"published":{"date-parts":[[2021,1,20]]}}}