{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,13]],"date-time":"2025-09-13T15:48:06Z","timestamp":1757778486251},"reference-count":16,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Explosive growth of short-read sequencing technologies in the recent years resulted in rapid development of many new alignment algorithms and programs. But most of them are not efficient or not applicable for reads \u2273200 bp because these algorithms specifically designed to process short queries with relatively low sequencing error rates. However, the current trend to increase reliability of detection of structural variations in assembled genomes as well as to facilitate de novo sequencing demand complimenting high-throughput short-read platforms with long-read mapping. Thus, algorithms and programs for efficient mapping of longer reads are becoming crucial. However, the choice of long-read aligners effective in terms of both performance and memory are limited and includes only handful of hash table (BLAT, SSAHA2) or trie (Burrows-Wheeler Transform - Smith-Waterman (BWT-SW), Burrows-Wheeler Alignerr - Smith-Waterman (BWA-SW)) based algorithms.<\/jats:p>\n               <jats:p>Results: New O(n) algorithm that combines the advantages of both hash and trie-based methods has been designed to effectively align long biological sequences (\u2273200 bp) against a large sequence database with small memory footprint (e.g. ~2 GB for the human genome). The algorithm is accurate and significantly more fast than BLAT or BWT-SW, but similar to BWT-SW it can find all local alignments. It is as accurate as SSAHA2 or BWA-SW, but uses 3+ times less memory and 10+ times faster than SSAHA2, several times faster than BWA-SW with low error rates and almost two times less memory.<\/jats:p>\n               <jats:p>Availability and implementation: The prototype implementation of the algorithm will be available upon request for non-commercial use in academia (local hit table binary and indices are at ftp:\/\/styx.ucsd.edu).<\/jats:p>\n               <jats:p>Contact: \u00a0vit@ucsd.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts102","type":"journal-article","created":{"date-parts":[[2012,3,9]],"date-time":"2012-03-09T01:41:10Z","timestamp":1331257270000},"page":"1070-1077","source":"Crossref","is-referenced-by-count":11,"title":["YOABS: yet other aligner of biological sequences\u2014an efficient linearly scaling nucleotide aligner"],"prefix":"10.1093","volume":"28","author":[{"given":"V. L.","family":"Galinsky","sequence":"first","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2012,3,7]]},"reference":[{"key":"2023012711533239100_B1","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023012711533239100_B2","volume-title":"A block-sorting lossless data compression algorithm","author":"Burrows","year":"1994"},{"key":"2023012711533239100_B3","first-page":"656","article-title":"BLAT\u2013the BLAST-like alignment tool","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res."},{"key":"2023012711533239100_B4","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1093\/bioinformatics\/btn032","article-title":"Compressed indexing and local alignment of DNA","volume":"24","author":"Lam","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012711533239100_B5","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol."},{"key":"2023012711533239100_B6","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012711533239100_B7","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","article-title":"Fast and accurate long-read alignment with Burrows-Wheeler transform","volume":"26","author":"Li","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012711533239100_B8","doi-asserted-by":"crossref","first-page":"1851","DOI":"10.1101\/gr.078212.108","article-title":"Mapping short DNA sequencing reads and calling variants using mapping quality scores","volume":"18","author":"Li","year":"2008","journal-title":"Genome Res."},{"key":"2023012711533239100_B9","doi-asserted-by":"crossref","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","article-title":"The sequence alignment\/map format and SAMtools","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012711533239100_B10","doi-asserted-by":"crossref","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","article-title":"SOAP2: an improved ultrafast tool for short read alignment","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012711533239100_B11","doi-asserted-by":"crossref","first-page":"936","DOI":"10.1101\/gr.111120.110","article-title":"Stampy: a statistical algorithm for sensitive and fast mapping of Illumina sequence reads","volume":"21","author":"Lunter","year":"2011","journal-title":"Genome Res."},{"key":"2023012711533239100_B12","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","article-title":"PatternHunter: faster and more sensitive homology search","volume":"18","author":"Ma","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012711533239100_B13","doi-asserted-by":"crossref","first-page":"1757","DOI":"10.1093\/bioinformatics\/btn322","article-title":"Database indexing for production MegaBLAST searches","volume":"24","author":"Morgulis","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012711533239100_B14","doi-asserted-by":"crossref","first-page":"1725","DOI":"10.1101\/gr.194201","article-title":"SSAHA: a fast search method for large DNA databases","volume":"11","author":"Ning","year":"2001","journal-title":"Genome Res."},{"key":"2023012711533239100_B15","doi-asserted-by":"crossref","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","article-title":"Improved tools for biological sequence comparison","volume":"85","author":"Pearson","year":"1988","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711533239100_B16","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1089\/10665270050081478","article-title":"A greedy algorithm for aligning DNA sequences","volume":"7","author":"Zhang","year":"2000","journal-title":"J. Comput. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/8\/1070\/48930487\/bioinformatics_28_8_1070.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/8\/1070\/48930487\/bioinformatics_28_8_1070.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T12:20:29Z","timestamp":1674822029000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/8\/1070\/196143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,7]]},"references-count":16,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2012,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts102","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2012,4]]},"published":{"date-parts":[[2012,3,7]]}}}