Prefix-Free Parsing for Building Large Tunnelled Wheeler Graphs Article Swipe
Adrián Goga
,
Andrej Baláž
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.wabi.2022.18
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.wabi.2022.18
We propose a new technique for creating a space-efficient index for large repetitive text collections, such as pangenomic databases containing sequences of many individuals from the same species. We combine two recent techniques from this area: Wheeler graphs (Gagie et al., 2017) and prefix-free parsing (PFP, Boucher et al., 2019). Wheeler graphs are a general framework encompassing several indexes based on the Burrows-Wheeler transform (BWT), such as the FM-index. Wheeler graphs admit a succinct representation which can be further compacted by employing the idea of tunnelling, which exploits redundancies in the form of parallel, equally-labelled paths called blocks that can be merged into a single path. The problem of finding the optimal set of blocks for tunnelling, i.e. the one that minimizes the size of the resulting Wheeler graph, is known to be NP-complete and remains the most computationally challenging part of the tunnelling process. To find an adequate set of blocks in less time, we propose a new method based on the prefix-free parsing (PFP). The idea of PFP is to divide the input text into phrases of roughly equal sizes that overlap by a fixed number of characters. The phrases are then sorted lexicographically. The original text is represented by a sequence of phrase ranks (the parse) and a list of all used phrases (the dictionary). In repetitive texts, the PFP representation of the text is generally much shorter than the original since individual phrases are used many times in the parse, thus reducing the size of the dictionary. To speed up the block selection for tunnelling, we apply the PFP to obtain the parse and the dictionary of the original text, tunnel the Wheeler graph of the parse using existing heuristics and subsequently use this tunnelled parse to construct a compact Wheeler graph of the original text. Compared with constructing a Wheeler graph from the original text without PFP, our method is much faster and uses less memory on collections of pangenomic sequences. Therefore, our method enables the use of Wheeler graphs as a pangenomic reference for real-world pangenomic datasets.
Related Topics
Concepts
Parsing
Computer science
Prefix
Sequence (biology)
Path (computing)
Phrase
Set (abstract data type)
Block (permutation group theory)
Representation (politics)
Algorithm
Theoretical computer science
Artificial intelligence
Combinatorics
Mathematics
Programming language
Biology
Law
Linguistics
Politics
Political science
Genetics
Philosophy
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.18
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4283772682
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4283772682Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.wabi.2022.18Digital Object Identifier
- Title
-
Prefix-Free Parsing for Building Large Tunnelled Wheeler GraphsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-01-01Full publication date if available
- Authors
-
Adrián Goga, Andrej BalážList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.18Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.18Direct OA link when available
- Concepts
-
Parsing, Computer science, Prefix, Sequence (biology), Path (computing), Phrase, Set (abstract data type), Block (permutation group theory), Representation (politics), Algorithm, Theoretical computer science, Artificial intelligence, Combinatorics, Mathematics, Programming language, Biology, Law, Linguistics, Politics, Political science, Genetics, PhilosophyTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4283772682 |
|---|---|
| doi | https://doi.org/10.4230/lipics.wabi.2022.18 |
| ids.doi | https://doi.org/10.4230/lipics.wabi.2022.18 |
| ids.openalex | https://openalex.org/W4283772682 |
| fwci | 0.0 |
| type | preprint |
| title | Prefix-Free Parsing for Building Large Tunnelled Wheeler Graphs |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10181 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9993000030517578 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Natural Language Processing Techniques |
| topics[1].id | https://openalex.org/T11269 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9944999814033508 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Algorithms and Data Compression |
| topics[2].id | https://openalex.org/T10538 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9940999746322632 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1710 |
| topics[2].subfield.display_name | Information Systems |
| topics[2].display_name | Data Mining Algorithms and Applications |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C186644900 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7651890516281128 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q194152 |
| concepts[0].display_name | Parsing |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.751142144203186 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C141603448 |
| concepts[2].level | 2 |
| concepts[2].score | 0.631689727306366 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q134830 |
| concepts[2].display_name | Prefix |
| concepts[3].id | https://openalex.org/C2778112365 |
| concepts[3].level | 2 |
| concepts[3].score | 0.563178300857544 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q3511065 |
| concepts[3].display_name | Sequence (biology) |
| concepts[4].id | https://openalex.org/C2777735758 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5595121383666992 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q817765 |
| concepts[4].display_name | Path (computing) |
| concepts[5].id | https://openalex.org/C2776224158 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5582966804504395 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q187931 |
| concepts[5].display_name | Phrase |
| concepts[6].id | https://openalex.org/C177264268 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5450873374938965 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q1514741 |
| concepts[6].display_name | Set (abstract data type) |
| concepts[7].id | https://openalex.org/C2777210771 |
| concepts[7].level | 2 |
| concepts[7].score | 0.5436668992042542 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q4927124 |
| concepts[7].display_name | Block (permutation group theory) |
| concepts[8].id | https://openalex.org/C2776359362 |
| concepts[8].level | 3 |
| concepts[8].score | 0.4530356824398041 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q2145286 |
| concepts[8].display_name | Representation (politics) |
| concepts[9].id | https://openalex.org/C11413529 |
| concepts[9].level | 1 |
| concepts[9].score | 0.4308328926563263 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[9].display_name | Algorithm |
| concepts[10].id | https://openalex.org/C80444323 |
| concepts[10].level | 1 |
| concepts[10].score | 0.4291975796222687 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[10].display_name | Theoretical computer science |
| concepts[11].id | https://openalex.org/C154945302 |
| concepts[11].level | 1 |
| concepts[11].score | 0.382202684879303 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[11].display_name | Artificial intelligence |
| concepts[12].id | https://openalex.org/C114614502 |
| concepts[12].level | 1 |
| concepts[12].score | 0.26768627762794495 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[12].display_name | Combinatorics |
| concepts[13].id | https://openalex.org/C33923547 |
| concepts[13].level | 0 |
| concepts[13].score | 0.22292789816856384 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[13].display_name | Mathematics |
| concepts[14].id | https://openalex.org/C199360897 |
| concepts[14].level | 1 |
| concepts[14].score | 0.16005000472068787 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[14].display_name | Programming language |
| concepts[15].id | https://openalex.org/C86803240 |
| concepts[15].level | 0 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q420 |
| concepts[15].display_name | Biology |
| concepts[16].id | https://openalex.org/C199539241 |
| concepts[16].level | 1 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q7748 |
| concepts[16].display_name | Law |
| concepts[17].id | https://openalex.org/C41895202 |
| concepts[17].level | 1 |
| concepts[17].score | 0.0 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q8162 |
| concepts[17].display_name | Linguistics |
| concepts[18].id | https://openalex.org/C94625758 |
| concepts[18].level | 2 |
| concepts[18].score | 0.0 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q7163 |
| concepts[18].display_name | Politics |
| concepts[19].id | https://openalex.org/C17744445 |
| concepts[19].level | 0 |
| concepts[19].score | 0.0 |
| concepts[19].wikidata | https://www.wikidata.org/wiki/Q36442 |
| concepts[19].display_name | Political science |
| concepts[20].id | https://openalex.org/C54355233 |
| concepts[20].level | 1 |
| concepts[20].score | 0.0 |
| concepts[20].wikidata | https://www.wikidata.org/wiki/Q7162 |
| concepts[20].display_name | Genetics |
| concepts[21].id | https://openalex.org/C138885662 |
| concepts[21].level | 0 |
| concepts[21].score | 0.0 |
| concepts[21].wikidata | https://www.wikidata.org/wiki/Q5891 |
| concepts[21].display_name | Philosophy |
| keywords[0].id | https://openalex.org/keywords/parsing |
| keywords[0].score | 0.7651890516281128 |
| keywords[0].display_name | Parsing |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.751142144203186 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/prefix |
| keywords[2].score | 0.631689727306366 |
| keywords[2].display_name | Prefix |
| keywords[3].id | https://openalex.org/keywords/sequence |
| keywords[3].score | 0.563178300857544 |
| keywords[3].display_name | Sequence (biology) |
| keywords[4].id | https://openalex.org/keywords/path |
| keywords[4].score | 0.5595121383666992 |
| keywords[4].display_name | Path (computing) |
| keywords[5].id | https://openalex.org/keywords/phrase |
| keywords[5].score | 0.5582966804504395 |
| keywords[5].display_name | Phrase |
| keywords[6].id | https://openalex.org/keywords/set |
| keywords[6].score | 0.5450873374938965 |
| keywords[6].display_name | Set (abstract data type) |
| keywords[7].id | https://openalex.org/keywords/block |
| keywords[7].score | 0.5436668992042542 |
| keywords[7].display_name | Block (permutation group theory) |
| keywords[8].id | https://openalex.org/keywords/representation |
| keywords[8].score | 0.4530356824398041 |
| keywords[8].display_name | Representation (politics) |
| keywords[9].id | https://openalex.org/keywords/algorithm |
| keywords[9].score | 0.4308328926563263 |
| keywords[9].display_name | Algorithm |
| keywords[10].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[10].score | 0.4291975796222687 |
| keywords[10].display_name | Theoretical computer science |
| keywords[11].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[11].score | 0.382202684879303 |
| keywords[11].display_name | Artificial intelligence |
| keywords[12].id | https://openalex.org/keywords/combinatorics |
| keywords[12].score | 0.26768627762794495 |
| keywords[12].display_name | Combinatorics |
| keywords[13].id | https://openalex.org/keywords/mathematics |
| keywords[13].score | 0.22292789816856384 |
| keywords[13].display_name | Mathematics |
| keywords[14].id | https://openalex.org/keywords/programming-language |
| keywords[14].score | 0.16005000472068787 |
| keywords[14].display_name | Programming language |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:17052 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306402524 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| locations[0].source.host_organization | https://openalex.org/I2799853480 |
| locations[0].source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| locations[0].source.host_organization_lineage | https://openalex.org/I2799853480 |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | InProceedings |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.18 |
| locations[1].id | pmh:oai:arXiv.org:2206.15097 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | https://arxiv.org/pdf/2206.15097 |
| locations[1].version | submittedVersion |
| locations[1].raw_type | text |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | http://arxiv.org/abs/2206.15097 |
| locations[2].id | doi:10.48550/arxiv.2206.15097 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400194 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | True |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | arXiv (Cornell University) |
| locations[2].source.host_organization | https://openalex.org/I205783295 |
| locations[2].source.host_organization_name | Cornell University |
| locations[2].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[2].license | |
| locations[2].pdf_url | |
| locations[2].version | |
| locations[2].raw_type | article-journal |
| locations[2].license_id | |
| locations[2].is_accepted | False |
| locations[2].is_published | |
| locations[2].raw_source_name | |
| locations[2].landing_page_url | https://doi.org/10.48550/arxiv.2206.15097 |
| locations[3].id | doi:10.4230/lipics.wabi.2022.18 |
| locations[3].is_oa | True |
| locations[3].source.id | https://openalex.org/S7407052059 |
| locations[3].source.type | repository |
| locations[3].source.is_oa | False |
| locations[3].source.issn_l | |
| locations[3].source.is_core | False |
| locations[3].source.is_in_doaj | False |
| locations[3].source.display_name | Dagstuhl Research Online Publication Server |
| locations[3].source.host_organization | |
| locations[3].source.host_organization_name | |
| locations[3].license | cc-by |
| locations[3].pdf_url | |
| locations[3].version | |
| locations[3].raw_type | |
| locations[3].license_id | https://openalex.org/licenses/cc-by |
| locations[3].is_accepted | False |
| locations[3].is_published | |
| locations[3].raw_source_name | |
| locations[3].landing_page_url | https://doi.org/10.4230/lipics.wabi.2022.18 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5011426923 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Adrián Goga |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Goga, Adrián |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5059632877 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-3113-3389 |
| authorships[1].author.display_name | Andrej Baláž |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Baláž, Andrej |
| authorships[1].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.18 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2022-07-03T00:00:00 |
| display_name | Prefix-Free Parsing for Building Large Tunnelled Wheeler Graphs |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10181 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9993000030517578 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Natural Language Processing Techniques |
| related_works | https://openalex.org/W2142481367, https://openalex.org/W3196321793, https://openalex.org/W3080705045, https://openalex.org/W2385527937, https://openalex.org/W2005880840, https://openalex.org/W2507465767, https://openalex.org/W4385305499, https://openalex.org/W2047674875, https://openalex.org/W4245066656, https://openalex.org/W2373597927 |
| cited_by_count | 0 |
| locations_count | 4 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:17052 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306402524 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| best_oa_location.source.host_organization | https://openalex.org/I2799853480 |
| best_oa_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | InProceedings |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.18 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:17052 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306402524 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| primary_location.source.host_organization | https://openalex.org/I2799853480 |
| primary_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| primary_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | InProceedings |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.18 |
| publication_date | 2022-01-01 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 2, 7, 53, 72, 103, 157, 185, 202, 210, 292, 303, 336 |
| abstract_inverted_index.In | 218 |
| abstract_inverted_index.To | 145, 251 |
| abstract_inverted_index.We | 0, 28 |
| abstract_inverted_index.an | 147 |
| abstract_inverted_index.as | 16, 66, 335 |
| abstract_inverted_index.be | 77, 100, 132 |
| abstract_inverted_index.by | 80, 184, 201 |
| abstract_inverted_index.et | 39, 47 |
| abstract_inverted_index.in | 89, 152, 241 |
| abstract_inverted_index.is | 129, 170, 199, 227, 314 |
| abstract_inverted_index.of | 21, 84, 92, 108, 113, 124, 141, 150, 168, 178, 188, 204, 212, 224, 248, 270, 278, 296, 323, 332 |
| abstract_inverted_index.on | 60, 161, 321 |
| abstract_inverted_index.to | 131, 171, 263, 290 |
| abstract_inverted_index.up | 253 |
| abstract_inverted_index.we | 155, 259 |
| abstract_inverted_index.PFP | 169, 222, 262 |
| abstract_inverted_index.The | 106, 166, 190, 196 |
| abstract_inverted_index.all | 213 |
| abstract_inverted_index.and | 42, 134, 209, 267, 284, 317 |
| abstract_inverted_index.are | 52, 192, 237 |
| abstract_inverted_index.can | 76, 99 |
| abstract_inverted_index.for | 5, 10, 115, 257, 339 |
| abstract_inverted_index.new | 3, 158 |
| abstract_inverted_index.one | 119 |
| abstract_inverted_index.our | 312, 327 |
| abstract_inverted_index.set | 112, 149 |
| abstract_inverted_index.the | 25, 61, 67, 82, 90, 110, 118, 122, 125, 136, 142, 162, 173, 221, 225, 232, 242, 246, 249, 254, 261, 265, 268, 271, 275, 279, 297, 307, 330 |
| abstract_inverted_index.two | 30 |
| abstract_inverted_index.use | 286, 331 |
| abstract_inverted_index.(the | 207, 216 |
| abstract_inverted_index.PFP, | 311 |
| abstract_inverted_index.al., | 40, 48 |
| abstract_inverted_index.find | 146 |
| abstract_inverted_index.form | 91 |
| abstract_inverted_index.from | 24, 33, 306 |
| abstract_inverted_index.i.e. | 117 |
| abstract_inverted_index.idea | 83, 167 |
| abstract_inverted_index.into | 102, 176 |
| abstract_inverted_index.less | 153, 319 |
| abstract_inverted_index.list | 211 |
| abstract_inverted_index.many | 22, 239 |
| abstract_inverted_index.most | 137 |
| abstract_inverted_index.much | 229, 315 |
| abstract_inverted_index.part | 140 |
| abstract_inverted_index.same | 26 |
| abstract_inverted_index.size | 123, 247 |
| abstract_inverted_index.such | 15, 65 |
| abstract_inverted_index.text | 13, 175, 198, 226, 309 |
| abstract_inverted_index.than | 231 |
| abstract_inverted_index.that | 98, 120, 182 |
| abstract_inverted_index.then | 193 |
| abstract_inverted_index.this | 34, 287 |
| abstract_inverted_index.thus | 244 |
| abstract_inverted_index.used | 214, 238 |
| abstract_inverted_index.uses | 318 |
| abstract_inverted_index.with | 301 |
| abstract_inverted_index.(PFP, | 45 |
| abstract_inverted_index.2017) | 41 |
| abstract_inverted_index.admit | 71 |
| abstract_inverted_index.apply | 260 |
| abstract_inverted_index.area: | 35 |
| abstract_inverted_index.based | 59, 160 |
| abstract_inverted_index.block | 255 |
| abstract_inverted_index.equal | 180 |
| abstract_inverted_index.fixed | 186 |
| abstract_inverted_index.graph | 277, 295, 305 |
| abstract_inverted_index.index | 9 |
| abstract_inverted_index.input | 174 |
| abstract_inverted_index.known | 130 |
| abstract_inverted_index.large | 11 |
| abstract_inverted_index.parse | 266, 280, 289 |
| abstract_inverted_index.path. | 105 |
| abstract_inverted_index.paths | 95 |
| abstract_inverted_index.ranks | 206 |
| abstract_inverted_index.since | 234 |
| abstract_inverted_index.sizes | 181 |
| abstract_inverted_index.speed | 252 |
| abstract_inverted_index.text, | 273 |
| abstract_inverted_index.text. | 299 |
| abstract_inverted_index.time, | 154 |
| abstract_inverted_index.times | 240 |
| abstract_inverted_index.using | 281 |
| abstract_inverted_index.which | 75, 86 |
| abstract_inverted_index.(BWT), | 64 |
| abstract_inverted_index.(Gagie | 38 |
| abstract_inverted_index.(PFP). | 165 |
| abstract_inverted_index.2019). | 49 |
| abstract_inverted_index.blocks | 97, 114, 151 |
| abstract_inverted_index.called | 96 |
| abstract_inverted_index.divide | 172 |
| abstract_inverted_index.faster | 316 |
| abstract_inverted_index.graph, | 128 |
| abstract_inverted_index.graphs | 37, 51, 70, 334 |
| abstract_inverted_index.memory | 320 |
| abstract_inverted_index.merged | 101 |
| abstract_inverted_index.method | 159, 313, 328 |
| abstract_inverted_index.number | 187 |
| abstract_inverted_index.obtain | 264 |
| abstract_inverted_index.parse) | 208 |
| abstract_inverted_index.parse, | 243 |
| abstract_inverted_index.phrase | 205 |
| abstract_inverted_index.recent | 31 |
| abstract_inverted_index.single | 104 |
| abstract_inverted_index.sorted | 194 |
| abstract_inverted_index.texts, | 220 |
| abstract_inverted_index.tunnel | 274 |
| abstract_inverted_index.Boucher | 46 |
| abstract_inverted_index.Wheeler | 36, 50, 69, 127, 276, 294, 304, 333 |
| abstract_inverted_index.combine | 29 |
| abstract_inverted_index.compact | 293 |
| abstract_inverted_index.enables | 329 |
| abstract_inverted_index.finding | 109 |
| abstract_inverted_index.further | 78 |
| abstract_inverted_index.general | 54 |
| abstract_inverted_index.indexes | 58 |
| abstract_inverted_index.optimal | 111 |
| abstract_inverted_index.overlap | 183 |
| abstract_inverted_index.parsing | 44, 164 |
| abstract_inverted_index.phrases | 177, 191, 215, 236 |
| abstract_inverted_index.problem | 107 |
| abstract_inverted_index.propose | 1, 156 |
| abstract_inverted_index.remains | 135 |
| abstract_inverted_index.roughly | 179 |
| abstract_inverted_index.several | 57 |
| abstract_inverted_index.shorter | 230 |
| abstract_inverted_index.without | 310 |
| abstract_inverted_index.Compared | 300 |
| abstract_inverted_index.adequate | 148 |
| abstract_inverted_index.creating | 6 |
| abstract_inverted_index.existing | 282 |
| abstract_inverted_index.exploits | 87 |
| abstract_inverted_index.original | 197, 233, 272, 298, 308 |
| abstract_inverted_index.process. | 144 |
| abstract_inverted_index.reducing | 245 |
| abstract_inverted_index.sequence | 203 |
| abstract_inverted_index.species. | 27 |
| abstract_inverted_index.succinct | 73 |
| abstract_inverted_index.FM-index. | 68 |
| abstract_inverted_index.compacted | 79 |
| abstract_inverted_index.construct | 291 |
| abstract_inverted_index.databases | 18 |
| abstract_inverted_index.datasets. | 342 |
| abstract_inverted_index.employing | 81 |
| abstract_inverted_index.framework | 55 |
| abstract_inverted_index.generally | 228 |
| abstract_inverted_index.minimizes | 121 |
| abstract_inverted_index.parallel, | 93 |
| abstract_inverted_index.reference | 338 |
| abstract_inverted_index.resulting | 126 |
| abstract_inverted_index.selection | 256 |
| abstract_inverted_index.sequences | 20 |
| abstract_inverted_index.technique | 4 |
| abstract_inverted_index.transform | 63 |
| abstract_inverted_index.tunnelled | 288 |
| abstract_inverted_index.Therefore, | 326 |
| abstract_inverted_index.containing | 19 |
| abstract_inverted_index.dictionary | 269 |
| abstract_inverted_index.heuristics | 283 |
| abstract_inverted_index.individual | 235 |
| abstract_inverted_index.pangenomic | 17, 324, 337, 341 |
| abstract_inverted_index.real-world | 340 |
| abstract_inverted_index.repetitive | 12, 219 |
| abstract_inverted_index.sequences. | 325 |
| abstract_inverted_index.techniques | 32 |
| abstract_inverted_index.tunnelling | 143 |
| abstract_inverted_index.NP-complete | 133 |
| abstract_inverted_index.challenging | 139 |
| abstract_inverted_index.characters. | 189 |
| abstract_inverted_index.collections | 322 |
| abstract_inverted_index.dictionary. | 250 |
| abstract_inverted_index.individuals | 23 |
| abstract_inverted_index.prefix-free | 43, 163 |
| abstract_inverted_index.represented | 200 |
| abstract_inverted_index.tunnelling, | 85, 116, 258 |
| abstract_inverted_index.collections, | 14 |
| abstract_inverted_index.constructing | 302 |
| abstract_inverted_index.dictionary). | 217 |
| abstract_inverted_index.encompassing | 56 |
| abstract_inverted_index.redundancies | 88 |
| abstract_inverted_index.subsequently | 285 |
| abstract_inverted_index.representation | 74, 223 |
| abstract_inverted_index.Burrows-Wheeler | 62 |
| abstract_inverted_index.computationally | 138 |
| abstract_inverted_index.space-efficient | 8 |
| abstract_inverted_index.equally-labelled | 94 |
| abstract_inverted_index.lexicographically. | 195 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/15 |
| sustainable_development_goals[0].score | 0.6000000238418579 |
| sustainable_development_goals[0].display_name | Life in Land |
| citation_normalized_percentile.value | 0.06659895 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |