Keynote Talk Abstracts

An interval graph models the intersection between a set of intervals on the real line by representing each interval as a vertex, with an edge between each pair of vertices whose corresponding intervals overlap. Interval graphs are perhaps the most well-known class of intersection graphs, and much work has been done to design succinct data structures for interval graphs and related classes of graphs in the past several years. Unlike prior work on succinct representations of general graphs and planar graphs, which focuses on supporting local graph queries such as adjacency testing and neighbor listing, the succinct data representations of interval graphs and related graph classes often support distance and shortest path queries, broadening the scope of information that can be directly computed from these structures.

This talk thus focuses on some of our results on this topic, especially those that designed new techniques for succinct data structures or used them in unconventional ways. These include our work on designing succinct distance oracles for interval graphs, which required us to design a succinct tree representation that can perform constant-time conversion between preorder ranks and level-order ranks of tree nodes, an operation whose constant-time support had been elusive despite work on several ways of representing trees succinctly over multiple decades. I also describe the design of a distance labeling for interval graphs that matches the lower bound on label sizes within additive lower-order terms, which required careful use of different tree traversal orderings to infer information, as a centralized data structure is not allowed in the model. Finally, our recent work on beer proper interval graphs is also covered; in a beer graph, shortest paths must pass through at least one of the special vertices called beer vertices. For this, we compressed bitvectors and trees based on a parameter of interval graphs to approach the information-theoretic lower bound.

Genome sequences provide a rich record of ancestry and evolutionary history. We present computational evidence that they carry another, unexpected signal: extreme environmental conditions also leave detectable, genome-wide patterns in DNA sequences.

Our alignment-free machine-learning framework uses compact genome proxies assembled from sequence segments sampled across the genome and characterizes them through distributions of short DNA patterns (k-mers). These distributions are analyzed using supervised and unsupervised learning, revealing similarities associated with shared extreme environments across substantial evolutionary distances, including between taxonomically distant extremophiles inhabiting comparable environments.

Building on these genome-wide signatures, our latest results identify sequence patterns associated with thermal adaptation. A natural language processing approach applied to canonical 6-mer and 9-mer profiles from nearly 600 bacterial and archaeal genomes reveals highly selective families of co-occurring motifs associated with thermophilic and psychrophilic adaptation while accounting for taxonomic structure. Thermophilic bacteria exhibit distinctive C- or G-stacked and CG-periodic patterns, psychrophilic bacteria show A-, T-, and AT-run patterns, and thermophilic archaea display a distinct CTAG-centred signature. Strikingly, the signal points beyond particular genes or biological functions toward sequence-dependent physical properties of DNA itself, including stability, stacking, and flexibility.

Together, these findings show how string-based genomic representations and machine learning can expose environmental components of genome organization beyond phylogenetic relatedness. This is particularly compelling in extremophiles, which inhabit the boundaries of biological habitability: deciphering such signatures may help illuminate adaptation to severe conditions, with implications for biotechnology, astrobiology, and the search for life in extreme extraterrestrial environments.

String-processing algorithms often need to select a subset of positions in their input strings. Such selections arise for a variety of reasons, for example, to avoid running expensive subroutines at every position. Local consistency is the simple principle that such selections should be determined by local context: whenever two positions are surrounded by identical substrings, they should be treated in the same way. A hierarchical view of this principle gives rise to locally consistent parsing, where a tree is built over a string so that different occurrences of the same substring induce almost identical parse structures, differing only near their boundaries. Locally consistent parsing can be traced back to two lines of work from 1994, which applied closely related ideas to equality testing for dynamic strings (Mehlhorn, Sundar, and Uhrig; SODA'94) and parallel suffix-tree construction (Sahinalp and Vishkin; CIAC'94 & STOC'94). Over the past three decades, this principle has found a wide range of applications in string processing, extending far beyond dynamic and parallel algorithms to compressed strings, packed-string processing, and classical string algorithms.

In this talk, I will highlight a few of these applications, focusing mostly on classical, dynamic, and compressed string algorithms. I will also survey the main ways of implementing locally consistent parsing—including alphabet partitioning, deterministic coin tossing, and local minima—and discuss their respective strengths and limitations. Finally, I will mention a few refinements, including the mechanism of pausing, which has been used to construct string synchronizing sets and to produce grammars whose size can be bounded in terms of substring complexity δ. I will conclude with a few open problems and directions for further development.