WABI 2022

Scope

WABI is an international Conference covering research in algorithmic work in bioinformatics, computational biology and systems biology. The emphasis is mainly on discrete algorithms and machine learning methods that address important problems in molecular biology, that are founded on sound models, that are computationally efficient, and that provide evidence of their potential usefulness in practice, preferably by testing on appropriately chosen simulated or real datasets. The goal is to present recent research results, including significant work-in-progress, and to identify and explore directions of future research. This year it is co-located with ALGO 2022.

Important Dates

  • Paper submission deadline: May 18, 2022 using EasyChair (closed)
  • Notification: June 14, 2022 (notifications went out on June 13)
  • Accepted papers final versions: June 24, 2022 (received, closed)
  • LIPIcs receives edited files: June 28, 2022
  • Proceedings published: September 5, 2022
  • Conference: September 5-9, 2022, in Potsdam, Germany
    • Mon 5, Tue 6, Wed 7 (till noon): WABI main conference (with LIPIcs proceedings)
    • Wed 7 (from noon), Thu 8, Fri 9 (till noon): Computational Pangenomics workshop (without proceedings)

Invited ALGO Keynote Speaker for WABI (Wednesday 11:30, before lunch)

Photo of Leena Salmela
Leena Salmela
University of Helsinki
Academy of Finland Research Fellow

Dr. Leena Salmela is a university lecturer in the Department of Computer Science at the University of Helsinki. Dr. Salmela received her D.Sc.(Tech) degree in computer science at Helsinki University of Technology, Finland, in 2009, where her researched focus was in string algorithms. Dr. Salmela’s current 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.

“Efficient solutions to biological problems using de Bruijn graphs“

A de Bruijn graph represents a set of sequencing reads by the k-mers, i.e. substrings of length k, occurring in the reads. In the node centric de Bruijn graph, the set of k-mers are the nodes of the de Bruijn graph and an edge is added between two nodes if they share an overlap of k-1 characters. This representation condenses the information in a large read set into compact space thus allowing efficient solutions to many problems in computational biology. Such problems include for example correction of sequencing errors and genome assembly. Because each position of a genome is sequenced several times, it is possible to correct sequencing errors in reads if we can identify data originating from the same genomic region. A de Bruijn graph can be used to represent compactly the reliable information and the individual reads can be corrected by aligning them to the graph. Genome assembly is a classic problem, which can be solved for example with de Bruijn graphs. The task is to reconstruct the underlying genome based on sequencing reads. In genome assembly the choice of k is a crucial matter. A small k can result in a tangled graph, whereas a too large k will fragment the graph. Furthermore, a different value of k may be optimal for different parts of the genome. Variable order de Bruijn graphs, which represent de Bruijn graphs of all orders k in a single data structure, have been proposed as a solution. We give the first definition of assembled sequences, i.e. contigs, on such graphs and an algorithm for enumerating them.

Schedule

NOTES:
– FFP2 or medical masks are required inside buildings on campus unless you are giving a talk.
– Last-minute schedule changes will be marked in purple.
– Please make sure to upload your PDF/PPTX to the presentation laptop BEFORE the session starts.
– Please use the cursor instead of the laser pointer, so online participants can see what you are pointing at.
– Please stand away from the speakers so we do not get an audio feedback loop.

MONDAY Sept 05 (WABI in HS3)

before 09:50: registration, badge pick-up, chat.
09:50 – 10:05: coffee break

SESSION 1: k-mer sets (Chair: Nadia Pisanti)
10:05 – 10:10: Short welcome message by PC Chairs
10:10 – 10:30: Yoshihiko Suzuki and Gene Myers. Accurate K-mer Classification Using Read Profiles (ZOOM)
10:30 – 10:50: Jens Zentgraf and Sven Rahmann. Fast gapped k-mer counting with subdivided multi-way bucketed Cuckoo hash tables (We apologize for the streaming problems. A separate video recording will be made available to online participants soon!)
10:50 – 11:10: Sebastian Schmidt and Jarno Alanko. Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time (ZOOM)

11:10 – 11:30: coffee break
11:30 – 12:30: ESA KEYNOTE (Saket Saurabh, plenary in HS1)
12:30 – 14:00 lunch

SESSION 2 Succinct Data Structures (Chair: Travis Gagie)
14:00 – 14:20: Zsuzsanna Liptak, Francesco Masillo and Simon J. Puglisi. Suffix sorting via matching statistics
14:20 – 14:40: Giulio Ermanno Pibiri. On Weighted K-Mer Dictionaries
14:40 – 15:00: Adrián Goga and Andrej Baláž. Prefix-free parsing for building large tunnelled Wheeler graphs (moved here from Tuesday BWT session)

15:00 – 15:20: coffee break

SESSION 3 Genome distance and rearrangement (Chair: Daniel Doerr)
15:20 – 15:40: Pijus Simonaitis and Benjamin J. Raphael. A maximum parsimony principle for multichromosomal complex genome rearrangements
15:40 – 16:00: Marilia Braga, Leonie Brockmann, Katharina Klerx and Jens Stoye. A linear time algorithm for an extended version of the breakpoint double distance
16:00 – 16:20: Diego P. Rubert and Marilia Braga. Gene orthology inference via large-scale rearrangements for partially assembled genomes

16:20 – 16:40: coffee break
16:40 – 17:40: WABI Business meeting: Information about WABI 2022; changes in the Steering Committee; future plans for WABI
17:40 – later: ALGO RECEPTION

TUESDAY Sept 06 (WABI in HS 3)

SESSION 4: BWT-like data structures (Chair: Jarno Alanko)
08:50 – 09:10: Veronica Guerrini, Alessio Conte, Roberto Grossi, Gianni Liti, Giovanna Rosone and Lorenzo Tattini. phyBWT: Alignment-free phylogeny via eBWT positional clustering
09:10 – 09:30: Taher Mun, Naga Sai Kavya Vaddadi and Ben Langmead. Pangenomic genotyping with the marker array (moved here from Monday’s Succinct Data Structures session)
09:30 – 09:50: Ahsan Sanaullah, Degui Zhi and Shaojie Zhang. Haplotype Threading Using the Positional Burrows-Wheeler Transform

09:50 – 10:10: coffee break

SESSION 5 (Chair: Thomas Vinar)
10:10 – 10:30: Alitzel López Sánchez and Manuel Lafond. Predicting Horizontal Gene Transfers with Perfect Transfer Networks
10:30 – 10:50: Konstantinn Bonnet, Tobias Marschall and Daniel Doerr. Constructing founder sets under allelic and non-allelic homologous recombination
10:50 – 11:10: Wei Wei and David Koslicki. WGSUniFrac: Applying UniFrac metric to Whole Genome Shotgun data (ZOOM)

11:10 – 11:30: coffee break
11:30 – 12:30: ESA KEYNOTE (Simon Puglisi, plenary in HS1)
12:30 – 14:00: lunch (and lunch meeting for Steering Committee only)

SESSION 6: Phylogenetics++ (Chair: Christina Boucher)
14:00 – 14:20: Mathieu Gascon and Nadia El-Mabrouk. Non-binary Tree Reconciliation with Endosymbiotic Gene Transfer
14:20 – 14:40: Baqiao Liu and Tandy Warnow. Fast and Accurate Species Trees from Weighted Internode Distances (ZOOM)
14:40 – 15:00: Giulia Bernardini, Leo van Iersel, Esther Julien and Leen Stougie. Reconstructing Phylogenetic Networks via Cherry Picking and Machine Learning

15:00 – 15:20: coffee break

SESSION 7 (Chair: Erin Molloy)
15:20 – 15:40: Eden Ozery, Meirav Zehavi and Michal Ziv-Ukelson. Algorithms for Structure Informed Genome Rearrangement
15:40 – 16:00: Daniel Gibney, Sharma V. Thankachan and Srinivas Aluru. Feasibility of Flow Decomposition with Subpath Constraints in Linear Time (ZOOM)

16:00-16:40: coffee break

16:40 – 17:25: ALGO Memorial lecture about Rolf Niedermeier, Gerhard Woeginger, Camil Demetrescu
17:25 – late: ALGO conference dinner (with short walk; ticket required)

WEDNESDAY Sept 07 (WABI in L-E.03 — note the different building/room!)

SESSION 8 (Chair: Christina Boucher)
08:50 – 09:10: Clément Agret, Bastien Cazaux and Antoine Limasset. Toward optimal fingerprint indexing for large scale genomics
09:10 – 09:30: Yoshihiro Shibuya, Djamal Belazzougui and Gregory Kucherov. Efficient reconciliation of genomic datasets of high similarity
09:30 – 09:50: Ke Chen and Mingfu Shao. Locality-sensitive bucketing functions

09:50 – 10:10: coffee break (note that the Wednesday morning session is on a different part of the campus. Access to the catering/coffee will take a longer walk. It may not be possible to spend much time at the coffee if you want to walk and be back on time. The OC will see if we can get some coffee at L-E.03 as well.)

SESSION 9 and AWARD (Chair: Sven Rahmann)
10:10 – 10:30: Bertrand Marchand, Sebastian Will, Sarah Berkemer, Laurent Bulteau and Yann Ponty. Fully-automated design of dynamic programming schemes for RNA folding with pseudoknots
10:30 – 11:10: WABI Best paper award

11:10 – 11:30: coffee break
11:30 – 12:30: WABI KEYNOTE by Leena Salmela: Efficient solutions to biological problems using de Bruijn graphs (plenary in HS1; chairs: Christina Boucher and Sven Rahmann)
12:30 – 14:00 lunch

14:00 – Friday noon:
WABI Pangenomics workshops by EU Projects PANGAIA and ALPACA (in H-2.57 — again different!)

Zoom link for the public lectures: https://uni-bielefeld.zoom.us/j/61746700409?pwd=RnI3ZGdad2FqR2pLNWx5RS9kSjBxdz09

14:00 – 15:00: Knut Reinert: Hierarchical Interleaved Bloom Filter: Enabling ultrafast, approximate sequence queries, and ALPACA business meeting (Alexander Schönhuth)
15:00 – 15:20: coffee break
15:20 – 16:20: PANGAIA network meeting, part I (Paola Bonizzoni)
16:20 – 16:30: coffee break
16:30 – 21:30: Social event: Boat tour including dinner and drinks (register by email with Jens Stoye)

THURSDAY Sept 08 (Pangenomics workshop in H-2.57)

08:50 – 09:50: PANGAIA network meeting, part II (Paola Bonizzoni)
09:50 – 10:10: coffee break
10:10 – 11:10: Camille Marchet: Round table discussion: how to improve communication with your advisors,
and a few other items about wellness at work, and Mathias Weller: Peer Community in bioinformatics: a new approach to reviewing and publishing
11:10 – 11:30: coffee break
11:30 – 12:30: Christina Boucher: Computational Problems in Metagenomic Amplification
12:30 – 14:00: lunch
14:00 – 15:00: Erin K. Molloy: Recent advances and open challenges in estimating evolutionary
histories from low-homoplasy markers, and Rayan Chikhi: Metagenome assembly and analysis
15:00 – 15:20: coffee break
15:20 – 16:20: Paul Medvedev: The theoretical analysis of sequencing bioinformatic algorithms
16:20 – 16:40: coffee break
16:40 – 18:00: Open problems session (Travis Gagie)

FRIDAY Sept 09 (Pangenomics workshop in H-2.57)

08:50 – 09:50: Hackathon, part I (Rayan Chikhi)
09:50 – 10:10: coffee break
10:10 – 11:10: Hackathon, part II (Rayan Chikhi)
11:10 – 11:30: coffee break
11:30 – 12:30: Gene Myers: High Fidelity Genome Sequencing: What have we been missing?
12:30 – 14:00: Closing remarks and lunch
14:00: end

Call for Papers (closed)

Papers presenting original research in all areas of algorithms applied to biology, ecology, medicine, and life sciences are sought. Please have a look at past issues of the conference for good examples.

Paper submission and proceedings (closed)

Papers should be submitted electronically via the EasyChair submission system. The WABI 2022 proceedings will be published in the Leibniz International Proceedings in Informatics (LIPIcs) series. Substantially extended versions of selected papers will be invited to a WABI 2022 special issue of Algorithms for Molecular Biology (see an example: 2020 issue).

Submission Guidelines: Manuscripts should be prepared according to the LIPIcs instructions using their most recent template (v2021.1.2). They should be 10-15 pages in length, excluding bibliography and title matter (header, abstract). Each paper must contain a succinct statement of the issues and of their motivation, a summary of the main results, and a brief explanation of their significance, all accessible to non-specialist readers. Additional material (beyond 15 pages) may be provided in a clearly marked appendix, which may or may not be read at the discretion of individual reviewers. In any case, the work must self-contained without the appendix. Only the typeset PDF file should be submitted to EasyChair for review. By submitting a paper, the authors acknowledge that in case of acceptance at least one of the authors must register at ALGO 2022, attend the conference in person or virtually, depending on circumstances, and present the paper.

WABI Program Committee

PC Chairs

  • Christina Boucher, University of Florida, USA
  • Sven Rahmann, Saarland University, Germany

PC members

  • Tatsuya Akutsu, Kyoto University
  • Marco Antoniotti, DISCo, Università degli Studi di Milano-Bicocca
  • Jasmijn Baaijens, TU Delft
  • Anne Bergeron, Universite du Quebec à Montréal
  • Paola Bonizzoni, Università di Milano-Bicocca
  • Lenore Cowen, Tufts University
  • Gianluca Della Vedova, Univ. degli Studi Milano-Bicocca
  • Daniel Doerr, Heinrich Heine University Düsseldorf
  • Mohammed El-Kebir, University of Illinois at Urbana-Champaign
  • Nadia El-Mabrouk, University of Montreal
  • Travis Gagie, Diego Portales University
  • Anna Gambin, Institute of Informatics, Warsaw University
  • Shilpa Garg, University of Copenhagen
  • Bjarni Halldorsson, deCODE genetics and Reykjavik University
  • Katharina Huber, University of East Anglila
  • Carl Kingsford, Carnegie Mellon University
  • Gregory Kucherov, CNRS/LIGM
  • Manuel Lafond, Université de Sherbrooke
  • Elodie Laine, Sorbonne Université
  • Yu Lin, The Australian National University
  • Stefano Lonardi, UC Riverside
  • Guillaume Marçais, Carnegie Mellon University
  • Camille Marchet, CNRS
  • Erin Molloy, University of Maryland, College Park
  • Francesca Nadalin, EMBL
  • William Stafford Noble, University of Washington
  • Aida Ouangraoua, Université de Sherbrooke
  • Ion Petre, Department of Mathematics and Statistics, University of Turku, Finland
  • Nadia Pisanti, University of Pisa
  • Solon Pissis, CWI Amsterdam
  • Alberto Policriti, University of Udine
  • Mihai Pop, University of Maryland
  • Teresa Przytycka, National Center of Biotechnology Information, NLM, NIH
  • Knut Reinert, FU Berlin
  • Eric Rivals, LIRMM/CNRS
  • Sebastien Roch, UW Madison
  • Giovanna Rosone, Dipartimento di Informatica – Università di Pisa
  • Alexander Schoenhuth, Bielefeld University
  • Mingfu Shao, Computational Biology Department, Carnegie Mellon University
  • Krister Swenson, CNRS, Université de Montpellier
  • Ewa Szczurek, University of Warsaw
  • Sharma V. Thankachan, University of Central Florida
  • Hélène Touzet, CNRS, CRIStAL, Lille
  • Tomas Vinar, Comenius University in Bratislava
  • Prudence Wong, University of Liverpool
  • Simone Zaccaria, UCL Cancer Institute
  • Louxin Zhang, National University of Singapore
  • Michal Ziv-Ukelson, Ben Gurion University of the Negev

Steering Committee

  • Bernard Moret, EPFL, Switzerland (till 09/2022)
  • Vincent Moulton, University of East Anglia, UK
  • Nadia Pisanti, University of Pisa (since 09/2022)
  • Mona Singh, Princeton University (since 09/2022)
  • Jens Stoye, Bielefeld University, Germany
  • Tandy Warnow, University of Illinois at Urbana-Champaign (till 09/2022)