CoChat
Sign Up
Cited by 14Algorithms and Data Compressionsemigroups and automata theoryGenomics and Phylogenetic Studies

Relative Suffix Trees

Open access
Farruggia, Andrea, Gagie, Travis, Navarro, Gonzalo, Puglisi, Simon J, Sirén, Jouni·2018·The Computer Journal
DOI 10.1093/comjnl/bxx108PMC PMC5956352
Open this paper in CoChat — free accountOpen PDF

Abstract

Suffix trees are one of the most versatile data structures in stringology, with many applications in bioinformatics. Their main drawback is their size, which can be tens of times larger than the input sequence. Much effort has been put into reducing the space usage, leading ultimately to compressed suffix trees. These compressed data structures can efficiently simulate the suffix tree, while using space proportional to a compressed representation of the sequence. In this work, we take a new approach to compressed suffix trees for repetitive sequence collections, such as collections of individual genomes. We compress the suffix trees of individual sequences relative to the suffix tree of a reference sequence. These relative data structures provide competitive time/space trade-offs, being almost as small as the smallest compressed suffix trees for repetitive collections, and competitive in time with the largest and fastest compressed suffix trees.

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.1093/comjnl/bxx108

Cites

Statistics

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?

  • A suffix tree saves the positions and values of all suffixes of a given string, allowing efficient pattern matching and substring search operations.

    “The tree saves their positions in the text as well as their values, allowing efficient pattern matching and substring search operations [15].”

    From Whole-Genome Alignment: Methods, Challenges, and Future Directions (2024) · cites this paper as [15]

Self-check

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

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

Cites

No references could be resolved yet.

Research works printed but not linked: 51

  1. [1]Weiner P. (1973) Linear Pattern Matching Algorithms. Proc. SWAT (FOCS) 1973, Iowa City, IA, October 15–17, pp. 1–11. IEEE.
  2. [2]Gusfield D. (1997) Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge, UK.
  3. [4]Mäkinen V., Belazzougui D., Cunial F. and Tomescu A.I. (2015) Genome-Scale Algorithm Design. Cambridge University Press, Cambridge, UK.
  4. [7]Ohlebusch E. and Gog S. (2009) A Compressed Enhanced Suffix Array Supporting Fast String Matching. Proc. SPIRE 2009, Saariselkä, Finland, August 25–27, pp. 51–62. Springer, Berlin, Germany.
  5. [8]Ohlebusch E., Fischer J. and Gog S. (2010) CST++. Proc. SPIRE 2010, Los Cabos, Mexico, October 11–13, pp. 322–333. Springer, Berlin, Germany.
  6. [10]Russo L.M.S., Navarro G. and Oliveira A.L. (2011) Fully compressed suffix trees. ACM Trans. Algorithms, 7, article 4.
  7. [11]Gog S. (2011) Compressed suffix trees: design, construction, and applications. PhD thesis, Ulm University, Germany.
  8. [12]Gog S. and Ohlebusch E. (2013) Compressed suffix trees: Efficient computation and storage of lcp-values. ACM J. Exp. Algorithmics, 18, article 2.1.
  9. [14]Navarro G. and Russo L.M.S. (2014) Fast fully-compressed suffix trees. Proc. DCC 2014, Snowbird, UT, March 26–28, pp. 283–291. IEEE, Los Alamitos, CA.
  10. [15]Navarro G. and Ordóñez A. (2016) Faster compressed suffix trees for repetitive text collections. ACM J. Exp. Algorithmics, 21, article 1.8.
  11. [16]Ocker C. (2015) Engineering fully-compressed suffix trees. M.Sc. thesis, Karlsruhe Institute of Technology, Germany.
  12. [17]Belazzougui D., Cunial F., Gagie T., Prezza N. and Raffinot M. (2015) Composite Repetition-aware Data Structures. Proc. CPM 2015, Ischia Island, Italy, 29 June–1 July, pp. 26–39. Springer, Berlin, Germany.
  13. [18]The 1000 Genomes Project Consortium (2015) A global reference for human genetic variation. Nature, 526, 68– 74. 26432245 PMC4750478
  14. [19]Kieffer J.C. and Yang E.-H. (2000) Grammar-based codes: a new class of universal lossless source codes. IEEE Trans. Inf. Theory, 46, 737– 754.
  15. [20]Charikar M., Lehman E., Liu D., Panigrahy R., Prabhakaran M., Sahai A. and Shelat A. (2005) The smallest grammar problem. IEEE Trans. Inf. Theory, 51, 2554– 2576.
  16. [22]Ziv J. and Lempel A. (1977) A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory, 23, 337– 343.
  17. [24]Gagie T., Gawrychowski P., Kärkkäinen J., Nekrich Y. and Puglisi S.J. (2012) A Faster Grammar-based Self-index. Proc. LATA 2012, Tarragona, Spain, March 5–9, pp. 240–251. Springer, Berlin, Germany.
  18. [25]Gagie T., Gawrychowski P., Kärkkäinen J., Nekrich Y. and Puglisi S.J. (2014) LZ77-Based Self-indexing with Faster Pattern Matching. Proc. LATIN 2014, Montevideo, Uruguay, 31 March–4 April, pp. 731–742. Springer, Berlin, Germany.
  19. [26]Gagie T. and Puglisi S.J. (2015) Searching and indexing genomic databases via kernelization. Front. Bioeng. Biotechnol., 3, 12. 25710001 PMC4321636
  20. [27]Kuruppu S., Puglisi S.J. and Zobel J. (2010) Relative Lempel–Ziv Compression of Genomes for Large-scale Storage and Retrieval. Proc. SPIRE 2010, Los Cabos, Mexico, October 11–13, pp. 201–206. Springer, Berlin, Germany.
  21. [28]Kuruppu S., Puglisi S.J. and Zobel J. (2011) Reference Sequence Construction for Relative Compression of Genomes. Proc. SPIRE 2011, Pisa, Italy, October 17–21, pp. 420–425. Springer, Berlin, Germany.
  22. [29]Kuruppu S., Beresford-Smith B., Conway T.C. and Zobel J. (2012) Iterative dictionary construction for compression of large DNA data sets. IEEE/ACM Trans. Comput. Biol. Bioinformatics, 9, 137– 149. 21576758
  23. [30]Liao K., Petri M., Moffat A. and Wirth A. (2016) Effective Construction of Relative Lempel–Ziv Dictionaries. Proc. WWW 2016, Montreal, Canada, April 11–15, pp. 807–816. IW3C2, Geneva, Switzerland.
  24. [31]Deorowicz S. and Grabowski S. (2011) Robust relative compression of genomes with random access. Bioinformatics, 27, 2979– 2986. 21896510
  25. [32]Ferrada H., Gagie T., Gog S. and Puglisi S.J. (2014) Relative Lempel–Ziv with Constant-time Random Access. Proc. SPIRE 2014, Ouro Preto, Brazil, October 20–22, pp. 13–17. Springer, Berlin, Germany.
  26. [34]Maciuca S., del Ojo Elias C., McVean G. and Iqbal Z. (2016) A Natural Encoding of Genetic Variation in a Burrows–Wheeler Transform to Enable Mapping and Genome Inference. Proc. WABI 2016, Aarhus, Denmark, 22–24 August, pp. 222–233. Springer, Berlin, Germany.
  27. [35]Paten B., Novak A.M., Eizenga J.M. and Garrison E. (2017) Genome graphs and the evolution of genome inference. Genome Res., doi: 10.1101/gr.214155.116. PMC5411762 28360232 · DOI · Paper page
  28. [36]Sirén J. (2017) Indexing Variation Graphs. Proc. ALENEX 2017, Barcelona, Spain, January 17–18, pp. 13–27. SIAM.
  29. [37]Sirén J., Välimäki N. and Mäkinen V. (2014) Indexing graphs for path queries with applications in genome research. ACM/IEEE Trans. Comput. Biol. Bioinformatics, 11, 375– 388. 26355784
  30. [39]Na J.-C., Kim H., Min S., Park H., Lecroq T., Léonard M., Mouchard L. and Park K. (2017) FM-index of alignment with gaps. Theoretical Computer Science, doi: 10.1016/j.tcs.2017.02.020. · DOI
  31. [40]Iqbal Z., Caccamo M., Turner I., Flicek P. and McVean G. (2012) De novo assembly and genotyping of variants using colored de Bruijn graphs. Nat. Genet., 44, 226– 232. 22231483 PMC3272472
  32. [41]Na J.C., Park H., Crochemore M., Holub J., Iliopoulos C.S., Mouchard L. and Park K. (2013) Suffix Tree of Alignment: An Efficient Index for Similar Data. Proc. IWOCA 2013, Rouen, France, July 10–12, pp. 337–348. Springer, Berlin, Germany.
  33. [42]Na J.C., Park H., Lee S., Hong M., Lecroq T., Mouchard L. and Park K. (2013) Suffix Array of Alignment: A Practical Index for Similar Data. Proc. SPIRE 2013, Jerusalem, Israel, October 7–9, pp. 243–254. Springer, Berlin, Germany.
  34. [44]Belazzougui D., Gagie T., Gog S., Manzini G. and Sirén J. (2014) Relative FM-Indexes. Proc. SPIRE 2014, Ouro Preto, Brazil, October 20–22, pp. 52–64. Springer, Berlin, Germany.
  35. [45]Muggli M.D., Bowe A., Noyes N.R., Morley P., Belk K., Raymond R., Gagie T., Puglisi S.J. and Boucher C. (2017) Succinct colored de Bruijn graphs. Bioinformatics, 33, 3181– 3187. 28200001 PMC5872255
  36. [46]Alipanahi B., Muggli M.D., Jundi M., Noyes N. and Boucher C. (2017) Resistome SNP calling via read colored de Bruijn graphs. Technical report. bioRxiv. PMC8016496 32049324
  37. [47]Almodaresi F., Pandey P. and Patro R. (2017) Rainbowfish: A Succinct Colored de Bruijn Graph Representation. Proc. WABI 2017, pp. 18:1–18:15.
  38. [48]Bowe A., Onodera T., Sadakane K. and Shibuya T. (2012) Succinct de Bruijn Graphs. Proc. WABI 2012, pp. 225–235.
  39. [49]Iqbal Z., Caccamo M., Turner I., Flicek P. and McVean G. (2012) De novo assembly and genotyping of variants using colored de Bruijn graphs. Nat. Genet., 44, 226– 232. 22231483 PMC3272472
  40. [52]Grossi R., Gupta A. and Vitter J.S. (2003) High-Order Entropy-compressed Text Indexes. Proc. SODA 2003, Baltimore, MD, January 12–14, pp. 841–850. SIAM.
  41. [55]Ferragina P. and Manzini G. (2005) Indexing compressed text. J. ACM, 52, 552– 581.
  42. [57]Ferragina P., González R., Navarro G. and Venturini R. (2009) Compressed text indexes: from theory to practice. ACM J. Exp. Algorithmics, 13, article 1.12.
  43. [58]Ferragina P., Manzini G., Mäkinen V. and Navarro G. (2007) Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms, 3, article20.
  44. [60]Okanohara D. and Sadakane K. (2007) Practical Entropy-Compressed Rank/Select Dictionary. Proc. ALENEX 2007, New Orleans, LA, 6 January, pp. 60–70. SIAM.
  45. [61]Cox A.J., Farruggia A., Gagie T., Puglisi S.J. and Sirén J. (2016) RLZAP: Relative Lempel–Ziv with Adaptive Pointers. Proc. SPIRE 2016, Beppu, Japan, October 18–20, pp. 1–14. Springer, Berlin, Germany.
  46. [62]Raman R., Raman V. and Satti S.R. (2007) Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms, 3, article 43.
  47. [63]Boucher C., Bowe A., Gagie T., Manzini G. and Sirén J. (2015) Relative Select. Proc. SPIRE 2015, London, UK, September 1–4, pp. 149–155. Springer, Berlin, Germany.
  48. [64]Sirén J. (2009) Compressed Suffix Arrays for Massive Data. Proc. SPIRE 2009, Saariselkä, Finland, August 25–27, pp. 63–74. Springer, Berlin, Germany.
  49. [65]Gog S., Beller T., Moffat A. and Petri M. (2014) From Theory to Practice: Plug and Play with Succinct Data Structures. Proc. SEA 2014, Copenhagen, Denmark, 29 June–1 July, pp. 326–337. Springer, Berlin, Germany.
  50. [67]Rozowsky J. et al (2011) AlleleSeq: analysis of allele-specific expression and binding in a network framework. Mol. Syst. Biol., 7, article522. PMC3208341 21811232
  51. [69]Ohlebusch E., Gog S. and Kügel A. (2010) Computing Matching Statistics and Maximal Exact Matches on Compressed Full-text Indexes. Proc. SPIRE 2010, Los Cabos, Mexico, October 11–13, pp. 347–358. Springer, Berlin, Germany.

Cited by

Sorted by citations

Authors
Farruggia, A., Gagie, T., Navarro, G., Puglisi, S. J., & Sirén, J.
Affiliations
  • University of Pisa (IT)
  • Centre for Biotechnology and Bioengineering (CL)
  • University of Helsinki (FI)
  • Wellcome Sanger Institute (GB)
Corresponding author
Navarro, Gonzalo
ORCID
Venue
The Computer Journal
Publisher
Oxford University Press (OUP)
Published
2017-11-21
Volume
61
Issue
5
Pages
773-788
ISSN
  • 0010-4620 (ISSN-L)
  • 1460-2067
DOI
10.1093/comjnl/bxx108
PMC
PMC5956352
OpenAlex
W2617428261
Cited by
14
References
0
Citations by year
2024: 3 · 2022: 1 · 2021: 3 · 2020: 3 · 2019: 2 · 2018: 1 · 2017: 1
FWCI
1.10
Type
journal article
Language
en
Open access
Licence
Locations
  • The Computer Journal (publishedVersion, cc-by)
  • Europe PMC (PubMed Central) (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Työväentutkimus Vuosikirja (submittedVersion)
  • Universidad de Chile (submittedVersion, cc-by-nc-nd)
  • arXiv (Cornell University)
Funders
Wellcome Trust (098051)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
Keywords
compressed suffix trees, suffix trees, space-efficient data structures, repetitive DNA, reference sequences, space-time tradeoff, string data structures

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