The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Indexing Graphs for Path Queries with Applications in Genome Research
Abstract
We propose a generic approach to replace the canonical sequence representation of genomes with graph representations, and study several applications of such extensions. We extend the Burrows-Wheeler transform (BWT) of strings to acyclic directed labeled graphs, to support path queries as an extension to substring searching. We develop, apply, and tailor this technique to a) read alignment on an extended BWT index of a graph representing pan-genome, i.e., reference genome and known variants of it; and b) split-read alignment on an extended BWT index of a splicing graph. Other possible applications include probe/primer design, alignments to assembly graphs, and alignments to phylogenetic tree of partial-order graphs. We report several experiments on the feasibility and applicability of the approach. Especially on highly-polymorphic genome regions our pan-genome index is making a significant improvement in alignment accuracy.
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.
Integrity signals
Registry
Cites
Statistics
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.
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
Fast and accurate short read alignment with Burrows-Wheeler transform
Li, H., & Durbin, R. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp324 · Cited by 58,607
An integrated map of genetic variation from 1,092 human genomes
The 1000 Genomes Project Consortium (2012) · Nature · doi:10.1038/nature11632 · Cited by 7,711
Sequencing technologies – the next generation
Metzker, M. L. (2010) · Nature Reviews Genetics · doi:10.1038/nrg2626 · Cited by 7,066
A Block-sorting Lossless Data Compression Algorithm
Burrows, M. T., & Wheeler, D. J. (1994) · Cited by 2,333
Suffix Arrays: A New Method for On-Line String Searches
Manber, U., & Myers, G. (1993) · SIAM Journal on Computing · doi:10.1137/0222058 · Cited by 1,915
A Fine-Scale Map of Recombination Rates and Hotspots Across the Human Genome
Myers, S., Bottolo, L., Freeman, C., McVean, G., & Donnelly, P. (2005) · Science · doi:10.1126/science.1117196 · Cited by 1,134
Navarro, G., & Mäkinen, V. (2007) · ACM Computing Surveys · doi:10.1145/1216370.1216372 · Cited by 735
Self-citationFerragina, P., & Manzini, G. (2005) · Journal of the ACM · doi:10.1145/1082036.1082039 · Cited by 686
Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
Grossi, R., & Vitter, J. S. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539702402354 · Cited by 431
Dindel: Accurate indel calls from short-read data
Albers, C. A., Lunter, G., MacArthur, D. G., McVean, G., Ouwehand, W. H., & Durbin, R. (2011) · Genome Research · doi:10.1101/gr.112326.110 · Cited by 410
Integrative Annotation of Variants from 1092 Humans: Application to Cancer Genomics
Khurana, E., Fu, Y., Colonna, V., Mu, X. J., Kang, H. M., Lappalainen, T., Sboner, A., Lochovsky, L., Chen, J., Harmanci, A., et al. (2013) · Science · doi:10.1126/science.1235587 · Cited by 365
Sense from sequence reads: methods for alignment and assembly
Flicek, P., & Birney, E. (2009) · Nature Methods · doi:10.1038/nmeth.1376 · Cited by 358
Variation analysis and gene annotation of eight MHC haplotypes: The MHC Haplotype Project
Horton, R., Gibson, R., Coggill, P., Miretti, M., Allcock, R. J., Almeida, J., Forbes, S., Gilbert, J. G. R., Halls, K., Harrow, J. L., et al. (2008) · Immunogenetics · doi:10.1007/s00251-007-0262-2 · Cited by 315
A taxonomy of suffix array construction algorithms
Puglisi, S. J., Smyth, W. F., & Turpin, A. H. (2007) · ACM Computing Surveys · doi:10.1145/1242471.1242472 · Cited by 312
Building the sequence map of the human pan-genome
Li, R., Li, Y., Zheng, H., Luo, R., Zhu, H., Li, Q., Qian, W., Ren, Y., Tian, G., Li, J., et al. (2010) · Nature Biotechnology · doi:10.1038/nbt.1596 · Cited by 259
Simultaneous alignment of short reads against multiple genomes
Schneeberger, K., Hagmann, J., Ossowski, S., Warthmann, N., Gesing, S., Kohlbacher, O., & Weigel, D. (2009) · Genome Biology · doi:10.1186/gb-2009-10-9-r98 · Cited by 237
Storage and Retrieval of Highly Repetitive Sequence Collections
Mäkinen, V., Navarro, G., Sirén, J., & Välimäki, N. (2010) · Journal of Computational Biology · doi:10.1089/cmb.2009.0169 · Cited by 206
Splicing graphs and EST assembly problem
Heber, S., Alekseyev, M., Sze, S.-H., Tang, H., & Pevzner, P. A. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.suppl_1.s181 · Cited by 201
Bowe, A., Onodera, T., Sadakane, K., & Shibuya, T. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33122-0_18 · Cited by 167
Compressing and indexing labeled trees, with applications
Ferragina, P., Luccio, F., Manzini, G., & Muthukrishnan, S. (2009) · Journal of the ACM · doi:10.1145/1613676.1613680 · Cited by 164
Accurate extension of multiple sequence alignments using a phylogeny-aware graph algorithm
Löytynoja, A., Vilella, A. J., & Goldman, N. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts198 · Cited by 129
Short read alignment with populations of genomes
Huang, L., Popic, V., & Batzoglou, S. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt215 · Cited by 112
Indexing Finite Language Representation of Population Genotypes
Sirén, J., Välimäki, N., & Mäkinen, V. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23038-7_23 · Cited by 20
Compressed Full-Text Indexes for Highly Repetitive Collections
Sirén, J. (2012) · Työväentutkimus Vuosikirja · Cited by 17
Cited by
Graph-based genome alignment and genotyping with HISAT2 and HISAT-genotype
Kim, D., Paggi, J. M., Park, C., Bennett, C., & Salzberg, S. L. (2019) · Nature Biotechnology · doi:10.1038/s41587-019-0201-4 · Cited by 15,022
Souporcell: robust clustering of single-cell RNA-seq data by genotype without reference genotypes
Heaton, H., Talman, A. M., Knights, A., Imaz, M., Gaffney, D. J., Durbin, R., Hemberg, M., & Lawniczak, M. K. N. (2020) · Nature Methods · doi:10.1038/s41592-020-0820-1 · Cited by 533
Eizenga, J. M., Novak, A. M., Sibbesen, J. A., Heumos, S., Ghaffaari, A., Hickey, G., Chang, X., Seaman, J. D., Rounthwaite, R., Ebler, J., et al. (2020) · Annual Review of Genomics and Human Genetics · doi:10.1146/annurev-genom-120219-080406 · Cited by 320
Self-citationComputational pan-genomics: status, promises and challenges
(2016) · Briefings in Bioinformatics · doi:10.1093/bib/bbw089 · Cited by 287
Graphtyper enables population-scale genotyping using pangenome graphs
Eggertsson, H. P., Jonsson, H., Kristmundsdottir, S., Hjartarson, E., Kehr, B., Masson, G., Zink, F., Hjorleifsson, K. E., Jonasdottir, A., Jonasdottir, A., et al. (2017) · Nature Genetics · doi:10.1038/ng.3964 · Cited by 276
Metadata
- Authors
- Siren, J., Valimaki, N., & Makinen, V.
- Venue
- IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Published
- 2014-03
- Volume
- 11
- Issue
- 2
- Pages
- 375-388
- ISSN
- 1545-5963 (ISSN-L)
- OpenAlex
- W2011210839
- Cited by
- 324
- References
- 24
- Type
- paratext
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.