CoChat
Sign Up
Cited by 242Genomics and Phylogenetic StudiesAlgorithms and Data CompressionFractal and DNA sequence analysis

The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.

GraphAligner: rapid and versatile sequence-to-graph alignment

Open access
Rautiainen, Mikko, Marschall, Tobias·2020·Genome Biology
DOI 10.1186/s13059-020-02157-2PMC PMC7513500

Published version of a preprint

Open this paper in CoChat — free accountOpen PDF

Abstract

Genome graphs can represent genetic variation and sequence uncertainty. Aligning sequences to genome graphs is key to many applications, including error correction, genome assembly, and genotyping of variants in a pangenome graph. Yet, so far, this step is often prohibitively slow. We present GraphAligner, a tool for aligning long reads to genome graphs. Compared to the state-of-the-art tools, GraphAligner is 13x faster and uses 3x less memory. When employing GraphAligner for error correction, we find it to be more than twice as accurate and over 12x faster than extant tools.Availability: Package manager: https://anaconda.org/bioconda/graphaligner and source code: https://github.com/maickrau/GraphAligner

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1186/s13059-020-02157-2

Cites

6 of 6 references verified0 citation errors · 0 not checkable

Statistics

Figures

Fig. 1 Fraction of reads correctly aligned at varying read lengths for the variant graph and the linear graph. Left: reads simulated from the GRCh37 reference. Right: reads simulated from de novo assembled contigs of HG00733
Fig. 1 Fraction of reads correctly aligned at varying read lengths for the variant graph and the linear graph. Left: reads simulated from the GRCh37 reference. Right: reads simulated from de novo assembled contigs of HG00733CC BY · PubMed Central
Fig. 2 Overview of the error correction pipeline. The circles represent data and the rectangles programs
Fig. 2 Overview of the error correction pipeline. The circles represent data and the rectangles programsCC BY · PubMed Central
Fig. 3 Overview of GraphAligner. Reads are aligned independently of the other reads. Seed hits are found by matching the sequence of the read to sequences inside nodes (small blue and green bars). Seed hits are clustered in locally acyclic parts of the graph and scored. Seed hits are then extended (small dotted boxes) with a banded dynamic programming algorithm, using Viterbi’s algorithm to decide when to clip the alignment (red X). Each seed hit can result in an alignment (blue and green paths). Alignments that overlap with an another, longer alignment in the query sequence are classified as secondary. Secondary alignments are discarded by default (red X) but can be included in the output with an optional parameter. The output is then written to a file either as alignments or corrected reads
Fig. 3 Overview of GraphAligner. Reads are aligned independently of the other reads. Seed hits are found by matching the sequence of the read to sequences inside nodes (small blue and green bars). Seed hits are clustered in locally acyclic parts of the graph and scored. Seed hits are then extended (small dotted boxes) with a banded dynamic programming algorithm, using Viterbi’s algorithm to decide when to clip the alignment (red X). Each seed hit can result in an alignment (blue and green paths). Alignments that overlap with an another, longer alignment in the query sequence are classified as secondary. Secondary alignments are discarded by default (red X) but can be included in the output with an optional parameter. The output is then written to a file either as alignments or corrected readsCC BY · PubMed Central
Fig. 4 Converting a bidirected graph with variable edge overlaps to an alignment graph. Top: a bidirected graph with three nodes. The edges are labeled by their overlap. The red-colored bars represent the same sequence, which should not be duplicated during traversal. Similarly, the orange-colored bars represent the same sequence. Bottom: the alignment graph created from the top graph. The colors of the base pairs show how they match between the two graphs, with each sequence in the original graph represented by the same color in the alignment graph twice, once for the forward strand and once for the reverse complement. Similarly to the bidirected graph, the red and orange bars represent the same sequences. There are two subgraphs, one representing the forward traversal (top) and one the backward traversal (bottom) with reverse complemented node labels. Each edge introduces a breakpoint in the target node, splitting the node at the boundary of the overlap. The alignment graph then connects the ends of the overlap such that the overlapping sequence is only traversed once
Fig. 4 Converting a bidirected graph with variable edge overlaps to an alignment graph. Top: a bidirected graph with three nodes. The edges are labeled by their overlap. The red-colored bars represent the same sequence, which should not be duplicated during traversal. Similarly, the orange-colored bars represent the same sequence. Bottom: the alignment graph created from the top graph. The colors of the base pairs show how they match between the two graphs, with each sequence in the original graph represented by the same color in the alignment graph twice, once for the forward strand and once for the reverse complement. Similarly to the bidirected graph, the red and orange bars represent the same sequences. There are two subgraphs, one representing the forward traversal (top) and one the backward traversal (bottom) with reverse complemented node labels. Each edge introduces a breakpoint in the target node, splitting the node at the boundary of the overlap. The alignment graph then connects the ends of the overlap such that the overlapping sequence is only traversed onceCC BY · PubMed Central
Fig. 5 Seeding. Top: A graph with four nodes. Middle: The node sequences are extracted from the nodes. The arrows represent a mapping between the strings and nodes. Bottom: A read. Highlighted in red: Matches between the read and a string are converted into a match inside a node using the mapping
Fig. 5 Seeding. Top: A graph with four nodes. Middle: The node sequences are extracted from the nodes. The arrows represent a mapping between the strings and nodes. Bottom: A read. Highlighted in red: Matches between the read and a string are converted into a match inside a node using the mappingCC BY · PubMed Central
Fig. 6 Building a minimizer index from a graph. Only the nodes of the graph are considered when building the index, and edges are ignored. Each node has an ID and a sequence. At the start, all nodes are labeled as unprocessed. Threads pick nodes one at a time from the pool of unprocessed nodes, and find minimizers in the node sequence. Then, the threads distribute the minimizers into buckets according to the modulo of their k-mer. Once all nodes have been processed, the threads proceed to index the buckets. Each thread picks one bucket and indexes it into a bucket index. The bucket index contains an array of the minimizers in that bucket sorted by the k-mer, a bitvector representing indices where a k-mer is different from the previous one, and a minimal perfect hash function which assigns each k-mer to the rank of the bit which represents the first instance of that k-mer in the sorted array
Fig. 6 Building a minimizer index from a graph. Only the nodes of the graph are considered when building the index, and edges are ignored. Each node has an ID and a sequence. At the start, all nodes are labeled as unprocessed. Threads pick nodes one at a time from the pool of unprocessed nodes, and find minimizers in the node sequence. Then, the threads distribute the minimizers into buckets according to the modulo of their k-mer. Once all nodes have been processed, the threads proceed to index the buckets. Each thread picks one bucket and indexes it into a bucket index. The bucket index contains an array of the minimizers in that bucket sorted by the k-mer, a bitvector representing indices where a k-mer is different from the previous one, and a minimal perfect hash function which assigns each k-mer to the rank of the bit which represents the first instance of that k-mer in the sorted arrayCC BY · PubMed Central
Fig. 7 A chain of superbubbles containing three superbubbles. The solid circles are nodes connected by directed edges. The dashed circles show the three superbubbles. The three superbubbles start and end at A and B, B and C, and C and D, respectively. The three superbubbles form one chain of superbubbles since they share start and end nodes
Fig. 7 A chain of superbubbles containing three superbubbles. The solid circles are nodes connected by directed edges. The dashed circles show the three superbubbles. The three superbubbles start and end at A and B, B and C, and C and D, respectively. The three superbubbles form one chain of superbubbles since they share start and end nodesCC BY · PubMed Central
Fig. 8 Left: regular banded alignment with b=3. The reference is on top and the query on the left. The gray cells are inside the band and are calculated. The blue line shows the traceback of the optimal alignment. Right: score based banding with b=1. The reference is on top and the query on the left. The gray cells are inside the band and the blue line is the traceback. The red-circled cells are the minimum for each row, which are discovered during the calculation of the matrix and define whether a cell is inside the band or not; a cell is inside the band if its score is within b of the minimum score in the same row. The cells with a number on a white background are calculated to discover the end of the band, but they are not inside the band and are ignored when calculating the next row. The band can wander around the DP matrix and change size, automatically spreading wider in high error areas and narrower in low error areas. Note that the score-based banding parameter is 1 in comparison to 3 in the regular banding to the left. The implementation uses a coarser band of 64 x 64 blocks instead of individual cells
Fig. 8 Left: regular banded alignment with b=3. The reference is on top and the query on the left. The gray cells are inside the band and are calculated. The blue line shows the traceback of the optimal alignment. Right: score based banding with b=1. The reference is on top and the query on the left. The gray cells are inside the band and the blue line is the traceback. The red-circled cells are the minimum for each row, which are discovered during the calculation of the matrix and define whether a cell is inside the band or not; a cell is inside the band if its score is within b of the minimum score in the same row. The cells with a number on a white background are calculated to discover the end of the band, but they are not inside the band and are ignored when calculating the next row. The band can wander around the DP matrix and change size, automatically spreading wider in high error areas and narrower in low error areas. Note that the score-based banding parameter is 1 in comparison to 3 in the regular banding to the left. The implementation uses a coarser band of 64 x 64 blocks instead of individual cellsCC BY · PubMed Central
Fig. 9 Dynamic score-based banding applied on a graph. Top: an alignment graph. Bottom: The DP matrix for aligning a read to the above graph. The arrows show the correspondence between nodes in the graph and columns in the DP matrix. The dotted lines separate the nodes. The gray area represents parts of the DP matrix which are calculated, and the parts in the white area are not calculated. At each fork, the band spreads to all out-neighbors. The score-based banding implicitly limits the exploration of the alternate paths; as the scores in the alternate paths become worse than the optimal path, the explored part shrinks until finally the exploration stops completely. The blue line shows the backtrace path
Fig. 9 Dynamic score-based banding applied on a graph. Top: an alignment graph. Bottom: The DP matrix for aligning a read to the above graph. The arrows show the correspondence between nodes in the graph and columns in the DP matrix. The dotted lines separate the nodes. The gray area represents parts of the DP matrix which are calculated, and the parts in the white area are not calculated. At each fork, the band spreads to all out-neighbors. The score-based banding implicitly limits the exploration of the alternate paths; as the scores in the alternate paths become worse than the optimal path, the explored part shrinks until finally the exploration stops completely. The blue line shows the backtrace pathCC BY · PubMed Central
Fig. 10 Sparse storage of the DP matrix. Each node is stored in blocks of 64 rows and up to 64 columns. The scores of the corner cells (solid black) are stored explicitly, using 4 bytes per cell. The border cells (gray) are stored with a score difference, using 2 bits per cell. The middle cells (white) are not stored
Fig. 10 Sparse storage of the DP matrix. Each node is stored in blocks of 64 rows and up to 64 columns. The scores of the corner cells (solid black) are stored explicitly, using 4 bytes per cell. The border cells (gray) are stored with a score difference, using 2 bits per cell. The middle cells (white) are not storedCC BY · PubMed Central
Fig. 11 An example of using Viterbi’s algorithm for estimating correctness per slice. The error rates of the minimum alignment per slice (not shown in figure) are the observations. The numbers represent the probability of the alignment being in the specific state at the specific slice. The arrows represent the predecessor state for each state in each slice. Slice 2 is guaranteed correct since the predecessor for the wrong state in slice 3 is through the correct state. Similarly, slice 4 is guaranteed wrong since the predecessor for the correct state in slice 5 is through the wrong state. None of the other slices are guaranteed correct or wrong. The final backtrace will consider slices 0, 1, and 2 correctly aligned and slices 3 to 5 wrongly aligned, and only the sequence in slices 0–2 will be reported in the alignment
Fig. 11 An example of using Viterbi’s algorithm for estimating correctness per slice. The error rates of the minimum alignment per slice (not shown in figure) are the observations. The numbers represent the probability of the alignment being in the specific state at the specific slice. The arrows represent the predecessor state for each state in each slice. Slice 2 is guaranteed correct since the predecessor for the wrong state in slice 3 is through the correct state. Similarly, slice 4 is guaranteed wrong since the predecessor for the correct state in slice 5 is through the wrong state. None of the other slices are guaranteed correct or wrong. The final backtrace will consider slices 0, 1, and 2 correctly aligned and slices 3 to 5 wrongly aligned, and only the sequence in slices 0–2 will be reported in the alignmentCC BY · PubMed Central

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 60

  1. Computational Pan-Genomics Consortium. Computational pan-genomics: status, promises and challenges. Brief Bioinforma. 2016; 19(1):118–35.
  2. Paten B, Novak AM, Eizenga JM, Garrison E. Genome graphs and the evolution of genome inference. Genome Res. 2017; 27(5):665–76. · DOI · Paper page
  3. Bankevich A, Nurk S, Antipov D, Gurevich AA, Dvorkin M, Kulikov AS, Lesin VM, Nikolenko SI, Pham S, Prjibelski AD, et al. SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing. J Comput Biol. 2012; 19(5):455–77. · DOI
  4. Antipov D, Korobeynikov A, McLean JS, Pevzner PA. hybridSPAdes: an algorithm for hybrid assembly of short and long reads. Bioinformatics. 2015; 32(7):1009–15. · DOI
  5. Wick RR, Judd LM, Gorrie CL, Holt KE. Unicycler: resolving bacterial genome assemblies from short and long sequencing reads. PLoS Comput Biol. 2017; 13(6):1005595. · DOI
  6. Salmela L, Rivals E. LoRDEC: accurate and efficient long read error correction. Bioinformatics. 2014; 30(24):3506–14. · DOI
  7. Miclotte G, Heydari M, Demeester P, Rombauts S, Van de Peer Y, Audenaert P, Fostier J. Jabba: hybrid error correction for long sequencing reads. Algorithm Mol Biol. 2016; 11(1):10. · DOI
  8. Wang JR, Holt J, McMillan L, Jones CD. FMLRC: hybrid long read error correction using an FM-index. BMC Bioinformatics. 2018; 19(1):50. · DOI
  9. Dolzhenko E, Deshpande V, Schlesinger F, Krusche P, Petrovski R, Chen S, Emig-Agius D, Gross A, Narzisi G, Bowman B, et al.ExpansionHunter: a sequence-graph based tool to analyze variation in short tandem repeat regions. Bioinformatics (Oxford, England). 2019; 35:4754–6. · DOI · Paper page
  10. Hickey G, Heller D, Monlong J, Sibbesen JA, Siren J, Eizenga J, Dawson E, Garrison E, Novak A, Paten B. Genotyping structural variants in pangenome graphs using the vg toolkit. Genome Biol. 2020; 21:35. https://doi.org/10.1186/s13059-020-1941-7. · DOI · Paper page
  11. Garg S, Rautiainen M, Novak AM, Garrison E, Durbin R, Marschall T. A graph-based approach to diploid genome assembly. Bioinformatics. 2018; 34(13):105–14. · DOI
  12. Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ. Basic local alignment search tool. J Mol Biol. 1990; 215(3):403–410. · DOI · Paper page
  13. Li H. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics. 2018; 34(18):3094–100. · DOI · Paper page
  14. Li H, Durbin R. Fast and accurate short read alignment with Burrows–Wheeler Transform. bioinformatics. 2009; 25(14):1754–60. · DOI · Paper page
  15. Sović I, Šikić M, Wilm A, Fenlon SN, Chen S, Nagarajan N. Fast and sensitive mapping of nanopore sequencing reads with graphmap. Nat Commun. 2016; 7:11307. · DOI
  16. Garrison E, Sirén J, Novak AM, Hickey G, Eizenga JM, Dawson ET, Jones W, Garg S, Markello C, Lin MF, et al.Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat Biotechnol. 2018; 46:875–9. · DOI · Paper page
  17. Navarro G. Improved approximate pattern matching on hypertext. Theor Comput Sci. 2000; 237(1):455–63. · DOI
  18. Equi M, Grossi R, Tomescu AI, Mäkinen V. On the complexity of exact pattern matching in graphs: determinism and zig-zag matching. arXiv preprint arXiv:1902.03560. 2019. · arXiv
  19. Lee C, Grasso C, Sharlow MF. Multiple sequence alignment using partial order graphs. Bioinformatics. 2002; 18(3):452–64. · DOI
  20. Kavya VNS, Tayal K, Srinivasan R, Sivadasan N. Sequence alignment on directed graphs. J Comput Biol. 2019; 26(1):53–67. · DOI
  21. Limasset A, Cazaux B, Rivals E, Peterlongo P. Read mapping on de bruijn graphs. BMC Bioinformatics. 2016; 17(1):237. · DOI
  22. Jain C, Zhang H, Gao Y, Aluru S. On the complexity of sequence to graph alignment. bioRxiv. 2019. https://doi.org/10.1101/522912. · DOI
  23. Rautiainen M, Mäkinen V, Marschall T. Bit-parallel sequence-to-graph alignment. Bioinformatics. 2019. https://doi.org/10.1093/bioinformatics/btz162. · DOI
  24. Myers G. A fast bit-vector algorithm for approximate string matching based on dynamic programming. J ACM (JACM). 1999; 46(3):395–415. · DOI
  25. Liu B, Guo H, Brudno M, Wang Y. deBGA: read alignment with de bruijn graph-based seed and extension. Bioinformatics. 2016; 32(21):3224–32. · DOI
  26. Durbin R. Efficient haplotype matching and storage using the positional Burrows–Wheeler Transform (pbwt). Bioinformatics. 2014; 30(9):1266–72. · DOI
  27. Sirén J, Välimäki N, Mäkinen V. IEEE/ACM Trans Comput Biol Bioinforma (TCBB). 2014; 11(2):375–88. · DOI
  28. Sirén J. Indexing variation graphs. In: 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics: 2017. p. 13–27. https://doi.org/10.1137/1.9781611974768.2. · DOI
  29. Sirén J, Garrison E, Novak AM, Paten B, Durbin R. Haplotype-aware graph indexes. arXiv preprint arXiv:1805.03834. 2018. · DOI
  30. Mokveld T, Linthorst J, Al-Ars Z, Holstege H, Reinders M. CHOP: haplotype-aware path indexing in population graphs. bioRxiv. 2019. https://doi.org/10.1101/305268. · DOI
  31. Ghaffaari A, Marschall T. Fully-sensitive seed finding in sequence graphs using a hybrid index: 2019. p i81–9. https://doi.org/10.1093/bioinformatics/btz341. · DOI
  32. Ono Y, Asai K, Hamada M. PBSIM: PacBio reads simulator—toward accurate genome assembly. Bioinformatics. 2013; 29(1):119–21. · DOI
  33. Clarke L, Fairley S, Zheng-Bradley X, Streeter I, Perry E, Lowy E, Tassé A-M, Flicek P. The international genome sample resource (IGSR): a worldwide collection of genome variation incorporating the 1000 genomes project data. Nucleic Acids Res. 2017; 45(D1):854–9. · DOI
  34. Porubsky D, Ebert P, Audano PA, Vollger MR, Harvey WT, Munson KM, Sorensen M, Sulovari A, Haukness M, Ghareghani M, Human Genome Structural Variation Consortium, Paten B, Devine SE, Sanders AD, Lee C, Chaisson MJP, Korbel JO, Eichler EE, Marschall T. A fully phased accurate assembly of an individual human genome. bioRxiv. 2019. https://www.biorxiv.org/content/10.1101/855049v1.abstract. · DOI
  35. Krusche P, Trigg L, Boutros PC, Mason CE, Francisco M, Moore BL, Gonzalez-Porta M, Eberle MA, Tezak Z, Lababidi S, et al. Best practices for benchmarking germline small-variant calls in human genomes. Nat Biotechnol. 2019; 37(5):555–60. · DOI · Paper page
  36. Lowy-Gallego E, Fairley S, Zheng-Bradley X, Ruffier M, Clarke L, Flicek P, Consortium GP, et al.Variant calling on the grch38 assembly with the data from phase three of the 1000 genomes project. Wellcome Open Res. 2019; 4:50. https://doi.org/10.12688/wellcomeopenres.15126.2. · DOI
  37. Cleary JG, Braithwaite R, Gaastra K, Hilbush BS, Inglis S, Irvine SA, Jackson A, Littin R, Rathod M, Ware D, et al.Comparing variant call files for performance benchmarking of next-generation sequencing variant calling pipelines. BioRxiv. 2015:023754. https://www.biorxiv.org/content/10.1101/023754v2.abstract. · DOI · Paper page
  38. Zhang H, Jain C, Aluru S. A comprehensive evaluation of long read error correction methods. bioRxiv. 2019. https://doi.org/10.1101/519330. · DOI
  39. Song L, Florea L, Langmead B. Lighter: fast and memory-efficient sequencing error correction without counting. Genome Biol. 2014; 15(11):509. · DOI
  40. Chikhi R, Limasset A, Medvedev P. Compacting de bruijn graphs from sequencing data quickly and in low memory. Bioinformatics. 2016; 32(12):201–208. · DOI
  41. Holt J, McMillan L. Merging of multi-string BWTs with applications. Bioinformatics. 2014; 30(24):3524–31. · DOI
  42. Li H. Fast construction of FM-index for long sequence reads. Bioinformatics. 2014; 30(22):3274–5. · DOI
  43. Li H, Handsaker B, Wysoker A, Fennell T, Ruan J, Homer N, Marth G, Abecasis G, Durbin R. The sequence alignment/map format and samtools. Bioinformatics. 2009; 25(16):2078–9. · DOI · Paper page
  44. Weirather JL, de Cesare M, Wang Y, Piazza P, Sebastiano V, Wang X-J, Buck D, Au KF. Comprehensive comparison of pacific biosciences and oxford nanopore technologies and their applications to transcriptome analysis. F1000Research. 2017; 6:2078–2079. · DOI · Paper page
  45. Rautiainen M, Durai DA, Chen Y, Xin L, Low HM, Göke J, Marschall T, Schulz MH. AERON: transcript quantification and gene-fusion detection using long reads. 2020. https://www.biorxiv.org/content/10.1101/2020.01.27.921338v1.abstract. · DOI
  46. Li H. Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences. Bioinformatics. 2016; 32(14):2103–10. · DOI
  47. Edmonds J, Johnson EL. Matching: a well-solved class of integer linear programs. In: Combinatorial Optimization—Eureka, You Shrink!. Berlin, Heidelberg: Springer: 2003. p. 27–30. https://doi.org/10.1007/3-540-36478-1_3. · DOI
  48. Medvedev P, Brudno M. Maximum likelihood genome assembly. J Comput Biol. 2009; 16(8):1101–16. · DOI
  49. Pevzner PA, Tang H, Waterman MS. An Eulerian path approach to DNA fragment assembly. Proc Natl Acad Sci. 2001; 98(17):9748–53. · DOI · Paper page
  50. Myers EW. The fragment assembly string graph. Bioinformatics. 2005; 21(suppl_2):79–85. · DOI · Paper page
  51. Koren S, Walenz BP, Berlin K, Miller JR, Bergman NH, Phillippy AM. Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation. Genome Res. 2017; 27:215087. · DOI
  52. Limasset A, Rizk G, Chikhi R, Peterlongo P. Fast and scalable minimal perfect hashing for massive key sets. arXiv preprint arXiv:1702.03154. 2017. · arXiv
  53. Gog S, Beller T, Moffat A, Petri M. From theory to practice: plug and play with succinct data structures. In: 13th International Symposium on Experimental Algorithms, (SEA 2014): 2014. p. 326–337. · DOI
  54. Kuosmanen A, Paavilainen T, Gagie T, Chikhi R, Tomescu A, Mäkinen V. Using minimum path cover to boost dynamic programming on dags: co-linear chaining extended. In: International Conference on Research in Computational Molecular Biology. Cham: Springer: 2018. p. 105–21. https://doi.org/10.1007/978-3-319-89929-9_7. · DOI
  55. Onodera T, Sadakane K, Shibuya T. Detecting superbubbles in assembly graphs. In: International Workshop on Algorithms in Bioinformatics. Berlin, Heidelberg: Springer: 2013. p. 338–48. https://doi.org/10.1007/978-3-642-40453-5_26. · DOI
  56. Ukkonen E. Algorithms for approximate string matching. Inf Control. 1985; 64(1-3):100–18. · DOI
  57. Chao K-M, Pearson WR, Miller W. Aligning two sequences within a specified diagonal band. Bioinformatics. 1992; 8(5):481–7. · DOI
  58. Suzuki H, Kasahara M. Acceleration of nucleotide semi-global alignment with adaptive banded dynamic programming. BioRxiv. 2017:130633. https://www.biorxiv.org/content/10.1101/130633v2.abstract. · DOI
  59. Zhang Z, Berman P, Wiehe T, Miller W. Post-processing long pairwise alignments. Bioinformatics. 1999; 15(12):1012–9. · DOI
  60. Viterbi A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans Inf Theory. 1967; 13(2):260–9. · DOI

Cited by

Sorted by citations

See all 242

Metadata

Authors
Rautiainen, M., & Marschall, T.
Affiliations
Max Planck Institute for Informatics (DE)
Corresponding author
Marschall, Tobias
ORCID
Venue
Genome Biology
Publisher
Springer Science and Business Media LLC
Published
2020-09-24
Volume
21
Issue
1
Pages
253-253
ISSN
  • 1465-6906 (ISSN-L)
  • 1474-760X
DOI
10.1186/s13059-020-02157-2
PMC
PMC7513500
OpenAlex
W3088400220
Cited by
242
References
6
Citations by year
2026: 39 · 2025: 50 · 2024: 53 · 2023: 48 · 2022: 23 · 2021: 19 · 2020: 10
FWCI
8.73
Type
journal article
Language
en
Open access
Licence
Locations
  • Genome biology (publishedVersion, cc-by)
  • bioRxiv (Cold Spring Harbor Laboratory) (acceptedVersion, cc-by-nd)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • MPG.PuRe (Max Planck Society) (submittedVersion, other-oa)
Funders
  • International Max Planck Research School for Environmental, Cellular and Molecular Microbiology
  • International Max Planck Research School for Advanced Methods in Process and Systems Engineering
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
Keywords
genome graphs, long-read alignment, pangenome graphs, error correction, genome assembly, variant genotyping, genetic variation
MeSH terms
Algorithms, Animals, Humans, Software, Sequence Alignment, Genomics

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review