Keynote speakers

Leena Salmela

Leena Salmela is a university lecturer in the Department of Computer Science at University of Helsinki, and research fellow at the Academy of Finland. Her research interests include genome assembly algorithms, de Bruijn graphs, and other algorithms for sequencing data. Software developed by her, such as the sequencing error correction program LoRDEC, has been used in numerous biological studies.

Talk: De Bruijn graphs: solving biological problems in small space

De Bruijn graphs have become a standard data structure in analysing sequencing data due to its ability to represent the information in a sequencing read set in small space. They represent the sequencing reads by the k-mers, i.e., substrings of length k occurring in the reads. Classically, the edges of a de Bruijn graph are defined to be the k-mers and the nodes are the k-1-length prefixes and suffixes of the k-mers. The construction of a de Bruijn graph starts by counting the k-mers occurring in the reads. Many good methods exist for extracting exact k-mers from read data and counting the number of their occurrences. However, sequencing read sets can contain a significant number of sequencing errors, which limits the usefulness of counting exact k-mers to short k-mers. Recently, we have developed methods for extracting longer k-mers from noisy data by using spaced seeds and strobemers.

De Bruijn graphs were originally introduced for solving the genome assembly problem, where the goal is to reconstruct the genome based on sequencing reads. In practice, genome assembly is solved with de Bruijn graphs by reporting unitigs, which are non-branching paths in the de Bruijn graphs. The choice of k is a crucial matter in de-Bruijn-graph-based genome assembly. A too small k will make the graph tangled, resulting in short unitigs, while a too large k will fragment the graph, again resulting in short unitigs. A variable-order de Bruijn graph, which represents de Bruijn graphs of all orders k in a single data structure, has been presented as a solution to the choice of k. However, it is not clear how the definition of unitigs can be extended to variable-order de Bruijn graphs.

In this talk, we present a robust definition of assembled sequences in variable-order de Bruijn graphs and an algorithm for enumerating them. Apart from genome assembly, de Bruijn graphs are used in many other problems such as sequencing error correction, reference free variant calling, indexing read sets, and so on. At the end of this talk, we will review some of these applications and their de-Bruijn-graph-based solutions.

---

Dominik Kempa

Dominik Kempa is an assistant professor in the Department of Computer Science at Stony Brook University. His research interests include parallel and external-memory algorithms, data compression, string algorithms, combinatorics on words, compressed data structures and bioinformatics.

Talk: LZ-End Parsing: Upper Bounds and Algorithmic Techniques

Lempel-Ziv (LZ77) compression is the most commonly used lossless compression algorithm. The basic idea is to greedily break the input string into blocks (called phrases), every time forming as a phrase the longest prefix of the unprocessed part that has an earlier occurrence. In 2010, Kreft and Navarro introduced a variant of LZ77 called LZ-End, that additionally requires the previous occurrence of each phrase to end at the boundary of an already existing phrase. Due to its excellent practical performance as a compression algorithm and a compressed index, they conjectured that it achieves a compression that can be provably upper-bounded in terms of the LZ77 size. Despite the recent progress in understanding such relation for other compression algorithms (e.g., the run-length encoded Burrows-Wheeler transform), no such result is known for LZ-End. In this talk, we give an overview of the recent progress on the above problem. More precisely, we prove that for any string of length n, the number z_e of phrases in the LZ-End parsing satisfies z_e = O(z log²n), where z is the number of phrases in the LZ77 parsing. This is the first non-trivial upper bound on the size of LZ-End parsing in terms of LZ77, and it puts LZ-End among the strongest dictionary compressors. Using our techniques, we also derive bounds for other variants of LZ-End and with respect to other compression measures. Our second contribution is a data structure that implements random access queries to the text in O(z_e) space and O(polylog n) time. This is the first linear-size structure on LZ-End that efficiently implements such queries. All previous data structures either incur a logarithmic penalty in the space or have slow queries. We also show how to extend these techniques to support longest-common-extension (LCE) queries. This work was carried out in collaboration with Barna Saha and was presented at the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).

Registration

At least one author per accepted paper must register at the appropriate conference rate by September 9, 2022. Registration fees are:

Category	Early bird (Until Oct. 5)	Regular
Onsite author	USD 320	USD 400
Online author	USD 240	USD 300
Onsite general	USD 240	USD 300
Onsite student	USD 160	USD 200
Online no-author	USD 0	USD 0

Note: In coordination with our workshop WCTA, we are providing free-registration scholarships for students. If you want to apply for them, fill the following scholarships form.

Online registration fee includes:

• Attendance to SPIRE 2022 sessions, invited talks and tutorial
• LNCS Proceedings (electronic version)

Additionally, onsite registration fee includes:

• Conference material
• Coffee breaks
• Lunches
• Social dinner and tourist event

---

Registration process

The registration process consists of four steps

1. Registration form (mandatory for all)

Complete the following form

2. Payment

We provide two payment options: online platform and bank transfer.

• Online platform: The prices in the online platform are the equivalent prices in chilean pesos

• Onsite author: Link
• Online author: Link
• Onsite general: Link
• Onsite student: Link



• Bank transfer: Please make a bank transfer, for the amount of your corresponding fee, to

• Bank name: Banco Itaú
• Swift code: ITAUCLRM
• Address: O’higgins 612, Concepción, Chile
• Account number: 0210344586
• Bank account holder: Universidad de Concepción - UdeC
• RUT (ID): 81.494.400-K
• Address: Edmundo Larenas 270 interior, Concepción, Chile
• Contact e-mail: iit-capa@udec.cl
• Reason of the payment: Registration SPIRE2022: Name of the participant -- affiliation (country)
• Amount: your corresponding fee



If necessary, consider:

• Beneficiary Banco Itaú (Chile)
• Swift code: ITAUCLRM
• Intermediary Bank: Bank of America N.A., 100 West 33 Street, 4 Floor. New York, NY 10001
• Swift code: BOFAUS3N
• ABA code: 026009593



Note 1: Please make sure that the bank transfer is free of charge for the beneficiary.

Note 2: For bank transfers inside Chile, contact us at spire2022@inf.udec.cl.

3. Send email and attach the payment confirmation receipt

To complete the registration process, please send us an email to spire2022@inf.udec.cl, attaching your payment-confirmation/receipt (e.g. PDF). In the email, include the recipient name (person/institution) for who/which the invoice must be issued and the full address for the invoice (otherwise, the address provided in the registration form will be used)

Note 1: All registrations will generate a legal invoice.

Note 2: If you need to issue the invoice to the name of your institution, please contact us at spire2022@inf.udec.cl. More details are needed to generate the invoice.

4. Confirmation email

Once received your email, and as soon as we receive the payment in our bank account, we will send you an email to confirm that the registration completed successfully. Please note that this could take more than one week, so please be patient.