{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T18:55:33Z","timestamp":1781636133716,"version":"3.54.5"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T00:00:00Z","timestamp":1771372800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T00:00:00Z","timestamp":1774396800000},"content-version":"vor","delay-in-days":35,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Max Planck Institute for Molecular Genetics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Searching large genomic data sets for local alignments poses a computational challenge. A particular obstacle is the handling of repetitive sequences that appear in various contexts and incur a high runtime cost. For practical homology search, it is important to develop a specific but sensitive filter. Good filters reduce the search space before alignment without missing significant matches.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We introduce DREAM-Stellar, a parallelized, updated version of the pairwise local aligner Stellar. The new aligner, DREAM-Stellar, is composed of four steps: preprocessing the queries and references, building a data structure for distributing the queries, computing in parallel the results and finally combining them. For distributing the queries we use the IBF data structure and a new prefilter for local alignments. We present our comparison of five local aligners on simulated and real genomic data and conclude that heuristic tools like BLAST miss a large percentage of significant local alignments or \"drown\" them in millions of less significant matches. This new version of Stellar is up to 900 times faster on 32 parallel threads than its single-threaded predecessor and can find all alignments between a pair of genomes in minutes. With that, the runtime of DREAM-Stellar is on par with tools like BLAST etc.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>\n                      DREAM-Stellar is very practical and fast on very long sequences which makes it a suitable new tool for finding local alignments between genomic sequences under the edit distance model. The software is freely available for Linux and Mac OS X at\n                      <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/github.com\/seqan\/dream-stellar\" ext-link-type=\"uri\">https:\/\/github.com\/seqan\/dream-stellar<\/jats:ext-link>\n                    <\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-026-06389-0","type":"journal-article","created":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T08:05:54Z","timestamp":1771401954000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["DREAM-Stellar: parallel and space efficient exact local alignment"],"prefix":"10.1186","volume":"27","author":[{"given":"Evelin","family":"Aasna","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon Gene","family":"Gottlieb","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcel","family":"Ehrhardt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Knut","family":"Reinert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,2,18]]},"reference":[{"key":"6389_CR1","doi-asserted-by":"publisher","DOI":"10.1126\/science.abn3943","author":"MJ Christmas","year":"2023","unstructured":"Christmas MJ, Kaplow IM, Genereux DP, Dong MX, Hughes GM, Li X, et al. Evolutionary constraint and innovation across hundreds of placental mammals. Science. 2023. https:\/\/doi.org\/10.1126\/science.abn3943.","journal-title":"Science"},{"issue":"4","key":"6389_CR2","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"PH Sellers","year":"1980","unstructured":"Sellers PH. The theory and computation of evolutionary distances: pattern recognition. J Algorithms. 1980;1(4):359\u201373. https:\/\/doi.org\/10.1016\/0196-6774(80)90016-4.","journal-title":"J Algorithms"},{"issue":"1","key":"6389_CR3","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS. Identification of common molecular subsequences. J Mol Biol. 1981;147(1):195\u20137.","journal-title":"J Mol Biol"},{"key":"6389_CR4","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btae097","author":"H Hauswedell","year":"2024","unstructured":"Hauswedell H, Hetzel S, Gottlieb SG, Kretzmer H, Meissner A, Reinert K. Lambda3: homology search for protein, nucleotide, and bisulfite-converted sequences. Bioinformatics. 2024. https:\/\/doi.org\/10.1093\/bioinformatics\/btae097.","journal-title":"Bioinformatics"},{"issue":"1","key":"6389_CR5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1038\/nmeth.3176","volume":"12","author":"B Buchfink","year":"2014","unstructured":"Buchfink B, Xie C, Huson DH. Fast and sensitive protein alignment using diamond. Nat Methods. 2014;12(1):59\u201360. https:\/\/doi.org\/10.1038\/nmeth.3176.","journal-title":"Nat Methods"},{"issue":"18","key":"6389_CR6","doi-asserted-by":"publisher","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","volume":"34","author":"H Li","year":"2018","unstructured":"Li H. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics. 2018;34(18):3094\u2013100. https:\/\/doi.org\/10.1093\/bioinformatics\/bty191.","journal-title":"Bioinformatics"},{"issue":"1","key":"6389_CR7","doi-asserted-by":"publisher","first-page":"1005944","DOI":"10.1371\/journal.pcbi.1005944","volume":"14","author":"G Mar\u00e7ais","year":"2018","unstructured":"Mar\u00e7ais G, Delcher AL, Phillippy AM, Coston R, Salzberg SL, Zimin A. Mummer4: a fast and versatile genome alignment system. PLoS Comput Biol. 2018;14(1):1005944. https:\/\/doi.org\/10.1371\/journal.pcbi.1005944.","journal-title":"PLoS Comput Biol"},{"issue":"4","key":"6389_CR8","first-page":"656","volume":"12","author":"WJ Kent","year":"2002","unstructured":"Kent WJ. BLAT-the BLAST-like alignment tool. Genome Res. 2002;12(4):656\u201364.","journal-title":"Genome Res"},{"issue":"6","key":"6389_CR9","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1093\/bioinformatics\/btn032","volume":"24","author":"TW Lam","year":"2008","unstructured":"Lam TW, Sung WK, Tam SL, Wong CK, Yiu SM. Compressed indexing and local alignment of DNA. Bioinformatics. 2008;24(6):791\u20137. https:\/\/doi.org\/10.1093\/bioinformatics\/btn032.","journal-title":"Bioinformatics"},{"issue":"3","key":"6389_CR10","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1006\/jmbi.1990.9999","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ. Basic local alignment search tool. J Mol Biol. 1990;215(3):403\u201310. https:\/\/doi.org\/10.1006\/jmbi.1990.9999.","journal-title":"J Mol Biol"},{"issue":"17","key":"6389_CR11","doi-asserted-by":"publisher","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","volume":"25","author":"SF Altschul","year":"1997","unstructured":"Altschul SF, Madden TL, Sch\u00e4ffer AA, Zhang J, Zhang Z, Miller W, et al. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res. 1997;25(17):3389\u2013402.","journal-title":"Nucleic Acids Res"},{"issue":"1\u20132","key":"6389_CR12","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1089\/10665270050081478","volume":"7","author":"Z Zhang","year":"2000","unstructured":"Zhang Z, Schwartz S, Wagner L, Miller W. A greedy algorithm for aligning DNA sequences. J Comput Biol. 2000;7(1\u20132):203\u201314. https:\/\/doi.org\/10.1089\/10665270050081478.","journal-title":"J Comput Biol"},{"key":"6389_CR13","unstructured":"Harris RS: Improved pairwise alignment of genomic dna. Phd thesis, The Pennsylvania State University (2007). Available at https:\/\/www.bx.psu.edu\/~rsharris\/rsharris_phd_thesis_2007.pdf"},{"issue":"3","key":"6389_CR14","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1101\/gr.113985.110","volume":"21","author":"SM Kie\u0142basa","year":"2011","unstructured":"Kie\u0142basa SM, Wan R, Sato K, Horton P, Frith MC. Adaptive seeds tame genomic sequence comparison. Genome Res. 2011;21(3):487\u201393. https:\/\/doi.org\/10.1101\/gr.113985.110.","journal-title":"Genome Res"},{"issue":"Suppl 9","key":"6389_CR15","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1186\/1471-2105-12-S9-S15","volume":"12","author":"B Kehr","year":"2011","unstructured":"Kehr B, Weese D, Reinert K. STELLAR: fast and exact local alignments. BMC Bioinform. 2011;12(Suppl 9):15. https:\/\/doi.org\/10.1186\/1471-2105-12-S9-S15.","journal-title":"BMC Bioinform"},{"issue":"7","key":"6389_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2021.102782","volume":"24","author":"E Seiler","year":"2021","unstructured":"Seiler E, Mehringer S, Darvish M, Turc E, Reinert K. Raptor: a fast and space-efficient pre-filter for querying very large collections of nucleotide sequences. Science. 2021;24(7):102782. https:\/\/doi.org\/10.1016\/j.isci.2021.102782.","journal-title":"Science"},{"issue":"6","key":"6389_CR17","doi-asserted-by":"publisher","first-page":"2264","DOI":"10.1073\/pnas.87.6.2264","volume":"87","author":"S Karlin","year":"1990","unstructured":"Karlin S, Altschul SF. Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proc Natl Acad Sci U S A. 1990;87(6):2264\u20138.","journal-title":"Proc Natl Acad Sci U S A"},{"issue":"4","key":"6389_CR18","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1016\/0022-2836(87)90478-5","volume":"197","author":"MS Waterman","year":"1987","unstructured":"Waterman MS, Eggert M. A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons. J Mol Biol. 1987;197(4):723\u20138.","journal-title":"J Mol Biol"},{"issue":"3","key":"6389_CR19","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","volume":"18","author":"B Ma","year":"2002","unstructured":"Ma B, Tromp J, Li M. Patternhunter: faster and more sensitive homology search. Bioinformatics. 2002;18(3):440\u20135. https:\/\/doi.org\/10.1093\/bioinformatics\/18.3.440.","journal-title":"Bioinformatics"},{"issue":"17","key":"6389_CR20","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1093\/bioinformatics\/bty567","volume":"34","author":"TH Dadi","year":"2018","unstructured":"Dadi TH, Siragusa E, Piro VC, Andrusch A, Seiler E, Renard BY, et al. Dream-yara: an exact read mapper for very large databases with short update time. Bioinformatics. 2018;34(17):766\u201372. https:\/\/doi.org\/10.1093\/bioinformatics\/bty567.","journal-title":"Bioinformatics"},{"issue":"2","key":"6389_CR21","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1089\/cmb.2006.13.296","volume":"13","author":"KR Rasmussen","year":"2006","unstructured":"Rasmussen KR, Stoye J, Myers EW. Efficient q-gram filters for finding all $$\\epsilon $$-matches over a given length. J Comput Biol. 2006;13(2):296\u2013308. https:\/\/doi.org\/10.1089\/cmb.2006.13.296.","journal-title":"J Comput Biol"},{"key":"6389_CR22","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2006-7-1-r7","author":"D Zhi","year":"2006","unstructured":"Zhi D, Raphael BJ, Price AL, Tang H, Pevzner PA. Identifying repeat domains in large genomes. Genome Biol. 2006. https:\/\/doi.org\/10.1186\/gb-2006-7-1-r7.","journal-title":"Genome Biol"},{"issue":"W1","key":"6389_CR23","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1093\/nar\/gkv416","volume":"43","author":"TL Bailey","year":"2015","unstructured":"Bailey TL, Johnson J, Grant CE, Noble WS. The meme suite. Nucleic Acids Res. 2015;43(W1):39\u201349. https:\/\/doi.org\/10.1093\/nar\/gkv416.","journal-title":"Nucleic Acids Res"},{"key":"6389_CR24","doi-asserted-by":"publisher","first-page":"6537","DOI":"10.1126\/science.abf7117","volume":"372","author":"P Ebert","year":"2021","unstructured":"Ebert P, Audano PA, Zhu EE. Haplotype-resolved diverse human genomes and integrated analysis of structural variation. Science. 2021;372:6537. https:\/\/doi.org\/10.1126\/science.abf7117.","journal-title":"Science"},{"key":"6389_CR25","doi-asserted-by":"publisher","DOI":"10.1101\/2024.09.24.614721","author":"GA Logsdon","year":"2024","unstructured":"Logsdon GA, Ebert CR, Eichler EE, Marschall T. Complex genetic variation in nearly complete human genomes. Nature. 2024. https:\/\/doi.org\/10.1101\/2024.09.24.614721.","journal-title":"Nature"},{"issue":"D1","key":"6389_CR26","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1093\/nar\/gkz836","volume":"48","author":"S Fairley","year":"2019","unstructured":"Fairley S, Lowy-Gallego E, Perry E, Flicek P. The international genome sample resource (igsr) collection of open human genomic variation resources. Nucleic Acids Res. 2019;48(D1):941\u20137. https:\/\/doi.org\/10.1093\/nar\/gkz836.","journal-title":"Nucleic Acids Res"},{"key":"6389_CR27","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-024-03297-5","author":"C Pan","year":"2024","unstructured":"Pan C, Reinert K. Leaf: an ultrafast filter for population-scale long-read sv detection. Genome Biol. 2024. https:\/\/doi.org\/10.1186\/s13059-024-03297-5.","journal-title":"Genome Biol"},{"key":"6389_CR28","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-021-02459-z","author":"I Georgakopoulos-Soares","year":"2021","unstructured":"Georgakopoulos-Soares I, Yizhar-Barnea O, Mouratidis I, Hemberg M, Ahituv N. Absent from dna and protein: genomic characterization of nullomers and nullpeptides across functional categories and evolution. Genome Biol. 2021. https:\/\/doi.org\/10.1186\/s13059-021-02459-z.","journal-title":"Genome Biol"},{"issue":"7","key":"6389_CR29","doi-asserted-by":"publisher","first-page":"41374","DOI":"10.1371\/journal.pone.0041374","volume":"7","author":"H Chen","year":"2012","unstructured":"Chen H, Tian Y, Shu W, Bo X, Wang S. Comprehensive identification and annotation of cell type-specific and ubiquitous ctcf-binding sites in the human genome. PLoS ONE. 2012;7(7):41374. https:\/\/doi.org\/10.1371\/journal.pone.0041374.","journal-title":"PLoS ONE"},{"issue":"6588","key":"6389_CR30","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1126\/science.abj6987","volume":"376","author":"S Nurk","year":"2022","unstructured":"Nurk S, Koren S, Rhie A, Rautiainen M, Bzikadze AV, Mikheenko A, et al. The complete sequence of a human genome. Science. 2022;376(6588):44\u201353. https:\/\/doi.org\/10.1126\/science.abj6987.","journal-title":"Science"},{"issue":"5\u20136","key":"6389_CR31","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1016\/s0092-8240(86)90010-8","volume":"48","author":"S Altschul","year":"1986","unstructured":"Altschul S, Erickson B. Optimal sequence alignment using affine gap costs. Bull Math Biol. 1986;48(5\u20136):603\u201316. https:\/\/doi.org\/10.1016\/s0092-8240(86)90010-8.","journal-title":"Bull Math Biol"},{"issue":"3","key":"6389_CR32","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1006\/geno.1996.0390","volume":"35","author":"L Stubbs","year":"1996","unstructured":"Stubbs L, Carver EA, Shannon ME, Kim J, Geisler J, Generoso EE, et al. Detailed comparative map of human chromosome 19q and related regions of the mouse genome. Genomics. 1996;35(3):499\u2013508. https:\/\/doi.org\/10.1006\/geno.1996.0390.","journal-title":"Genomics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-026-06389-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-026-06389-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-026-06389-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T18:24:31Z","timestamp":1781634271000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s12859-026-06389-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,18]]},"references-count":32,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["6389"],"URL":"https:\/\/doi.org\/10.1186\/s12859-026-06389-0","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,18]]},"assertion":[{"value":"8 July 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"67"}}