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
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 506
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-citationGraphAligner: rapid and versatile sequence-to-graph alignment
Rautiainen, M., & Marschall, T. (2020) · Genome Biology · doi:10.1186/s13059-020-02157-2 · Cited by 242
Technology dictates algorithms: recent developments in read alignment
Alser, M., Rotman, J., Deshpande, D., Taraszka, K., Shi, H., Baykal, P. I., Yang, H. T., Xue, V., Knyazev, S., Singer, B. D., et al. (2021) · Genome Biology · doi:10.1186/s13059-021-02443-7 · Cited by 144
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Indexing Graphs for Path Queries with Applications in Genome Research. https://app.cochat.ai/papers/10.1109/tcbb.2013.2297101
- The paper
- Siren, J., Valimaki, N., & Makinen, V. (2014). Indexing Graphs for Path Queries with Applications in Genome Research. IEEE/ACM Transactions on Computational Biology and Bioinformatics. https://doi.org/10.1109/tcbb.2013.2297101
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.
