Algorithmic / Bioinformatics Journal Club

We organize a weekly journal club, where we discuss interesting papers from the fields of algorithms and bioinformatics.

These events are internal to the Algorithmic Bioinformatics group and its close collaborators.

Upcoming presentations

Date and presenter: Friday 18 March 2022, 11am-12pm, Andrea Cracco,
Paper: Scalable, ultra-fast, and low-memory construction of compacted de Bruijn graphs with Cuttlefish 2. Khan, J., Kokot, M., Deorowicz, S., & Patro, R.
Date and presenter: Friday 25 March 2022, 11am-12pm, Shahbaz Khan,
Paper: A DFS Algorithm for Maximum Matchings in General Graph. Khan, J., Kokot, M., Deorowicz, S., & Patro, R.

2022:

Date and presenter: Friday 11 March 2022, 11am-12pm, Ariel, (Part II)
Paper: Co-linear Chaining with Overlaps and Gap Costs. Chirag Jain, Daniel Gibney and Sharma V. Thankachan.
Date and presenter: Friday 04 March 2022, 11am-12pm, Ariel (Part I)
Paper: Co-linear Chaining with Overlaps and Gap Costs. Chirag Jain, Daniel Gibney and Sharma V. Thankachan.
Date and presenter: Friday 25 February 2022, 11am-12pm, Nicola Rizzo.
Paper: Weighted ancestors in suffix trees revisited. Belazzougui, D., Kosolobov, D., Puglisi, S. J., & Raman, R.
Date and presenter: Friday 18 February 2022, 11am-12pm, Andreas Grigorjew
Paper: An Approximation Algorithm for Multiroute Flow Decomposition. Vorapong Suppakitpaisarn
Date and presenter: Friday 11 February 2022, 11am-12pm, Diego Diaz
Paper: Random access to grammar-compressed strings and trees. Bille, P., Landau, G. M., Raman, R., Sadakane, K., Satti, S. R., & Weimann, O.
Date and presenter: Friday 4 February 2022, 11am-12pm, Sebastian Schmidt
Paper: Finding Hamiltonian circuits in quasi-adjoint graphs. Blazewicz, J., Kasprzak, M., Leroy-Beaulieu, B., & de Werra, D. (2008).
Date and presenter: Friday 28 January 2022, 11am-12 pm, Fernando Dias,
Paper: Parsimonious clone tree reconciliation in cancer. Sashittal, Palash, Simone Zaccaria, and Mohammed El-Kebir.

2021:

Date and presenter: Friday 10 December 2021, 11am-12pm, Lucy Williams,
Paper: A practical algorithm for Flow Decomposition and transcript assembly. ALENEX 2018, Kyle Kloster, Philipp Kuinke, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, Blair D. Sullivan, Andrew van der Poel.
Date and presenter: Friday 03 December 2021, 11am-12pm, Borja Freire Castro
Paper: Haploflow: Strain-resolved de novo assembly of viral genomes.. Fritz, A., Bremges, A., Deng, Z. L., Lesker, T. R., Goetting, J., Ganzenmueller, T., ... & McHardy, A. C. (2021)
Date and presenter: Friday 19 November 2021, 11am-12pm, Andreas Grigorjew
Paper: On Near-Optimal Alignments of Biological Sequences. Journal of Computational Biology, Dalit Naor, Douglas L. Brutlag.
Date and presenter: Friday 19 November 2021, 11am-12pm, Sebastian Schmidt
Paper: PREMIER: PRobabilistic Error-correction using Markov Inference in Errored Reads, IEEE International Symposium on Information Theory (2013), Xin Yin, Zhao Song, Karin Dorman, Aditya Ramamoorthy.
Date and presenter: Friday 12 November 2021, 11am-12pm, Fernando Dias
Paper: Integer programming formulations for the elementary shortest path problem, European Journal of Operational Research (2016), LeonardoTaccari.
Date and presenter: Wednesday 13 October 2021, 11am-12pm, Diego Diaz,
Paper: Optimal-Time Dictionary-Compressed Indexes , ACM Transactions on Algorithms, Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro, Nicola Prezza.
Date and presenter: Wednesday 6 October 2021, 11am-12pm, Nicola Rizzo,
Paper: The tractability frontier for NFA minimization, Journal of Computer and System Sciences 2012, Henrik Björklunda, Wim Martens.
Date and presenter: Wednesday 22 September 2021, 11am-12pm, Lucy Williams,
Paper: A practical algorithm for Flow Decomposition and transcript assembly. ALENEX 2018, Kyle Kloster, Philipp Kuinke, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, Blair D. Sullivan, Andrew van der Poel.
Date and presenter: Wednesday 15 September 2021, 11am-12pm, Manuel Ariel Cáceres Reyes,
Paper: Efficient algorithms for measuring the funnel-likeness of DAGs. J Comb Optim 2020 (continued), Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
Date and presenter: Wednesday 8 September 2021, 11am-12pm, Manuel Ariel Cáceres Reyes,
Paper: Efficient algorithms for measuring the funnel-likeness of DAGs. J Comb Optim 2020, Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
Date and presenter: Friday 3 September 2021, 11am-12pm, Shahbaz Khan,
Paper: Superbubbles, Ultrabubbles and Cacti, RECOMB 2017, Benedict Paten, Adam M. Novak, Erik Garrison, Glenn Hickey
Date and presenter: Friday 27 August 2021, 11am-12pm, Tuukka Norri,
Paper: Algorithms and Complexity on Indexing Founder Graphs. RECOMB-Seq 2021, Massimo Equi, Tuukka Norri, Jarno Alanko, Bastien Cazaux, Alexandru I. Tomescu, and Veli Mäkinen
Date and presenter: Friday 6 August 2021, 11am-12pm, Miika Leinonen,
Paper: Multiple sequence alignment using partial order graphs, Bioinformatics, 2002, Christopher Lee, Catherine Grasso, Mark F. Sharlow.
Date and presenter: Friday 9 July 2021, 11am-12pm, Sebastian Schmidt,
Paper: Backtracking (the) Algorithms on the Hamiltonian Cycle Problem, Joeri Sleegers, Daan van den Berg
Date and presenter: Friday 11 June 2021, 11am-12pm, Fernando Dias,
Paper: How to split a flow?, INFOCOM 2012, Hartman, T., Hassidim, A., Kaplan, H., Raz, D., & Segalov, M.
Date and presenter: Friday 4 June 2021, 11am-12pm, Andreas Grigorjew,
Paper: Locating well-conserved regions within a pairwise alignment, K.-M. Chao, R. C. Hardison, and W. Miller.
Date and presenter: Friday 28 May 2021, 11am-12pm, Massimo Equi,
Topic: Short introduction to quantum computing.
Date and presenter: Friday 21 May 2021, 11am-12pm, Tuukka Norri,
Topic: Short introduction to SeqAn 3.
Date and presenter: Friday 7 May 2021, 11am-12pm, Saska Dönges,
Paper: Engineering Predecessor Data Structures for Dynamic Integer Sets, SEA 2021 , Patrick Dinklage, Johannes Fischer and Alexander Herlez.
Date and presenter: Friday 16 April 2021, 11am-12pm, Group Discussion,
Problem: Brain storming session on some open problems (continued)
Date and presenter: Friday 9 April 2021, 11am-12pm, Group Discussion.
Problem: Brain storming session on some open problems
Date and presenter: Friday 30 March 2021, 11am-12pm, Sebastian Schmidt,
Paper: Assembly of long, error-prone reads using repeat graphs (The Flye assembler), Nature Biotechnology, Mikhail Kolmogorov, Jeffrey Yuan, Yu Lin and Pavel A. Pevzner.
Date and presenter: Friday 23 March 2021, 11am-12pm, Alexandru Tomescu,
Paper: Simplitigs as an efficient and scalable representation of de Bruijn graphs, Genome Biology, Karel Břinda, Michael Baym and Gregory Kucherov
Date and presenter: Thursday 26 March 2021, 2pm-3pm, Manuel Ariel Cáceres Reyes,
Paper: Distance indexing and seed clustering in sequence graphs, ISMB 2020 (continued), Xian Chang, Jordan Eizenga, Adam M Novak, Jouni Sirén, Benedict Paten,
Date and presenter: Thursday 18 March 2021, 2pm-3pm, Manuel Ariel Cáceres Reyes,
Paper: Distance indexing and seed clustering in sequence graphs, ISMB 2020 , Xian Chang, Jordan Eizenga, Adam M Novak, Jouni Sirén, Benedict Paten,
Date and presenter: Thursday 11 March 2021, 2pm-3pm, Shahbaz Khan,
Paper: Shortest DNA cyclic cover in compressed space DCC 2016, Bastien Cazaux, Rodrigo Canovas and Eric Rivals.
Date and presenter: Thursday 4 March 2021, 2pm-3pm, Sebastian Schmidt,
Paper: Minimap2: pairwise alignment for nucleotide sequences, Bioinformatics 2018, by Heng Li
Date and presenter: Thursday 18 February 2021, 2pm-3pm, Nicola Rizzo,
Paper: The Longest Repeated String Problem on Graphs, by Nicola Rizzo, Alexandru I. Tomescu, Massimo Equi, Veli Mäkinen and Alberto Policriti.
Date and presenter: Thursday 4 February 2021, 2pm-3pm, Shahbaz Khan,
Paper: Simple dynamic algorithms for Maximal Independent set, Maximum Flow and Maximum Matching, SOSA 2021, by Manoj Gupta and Shahbaz Khan
Date and presenter: Friday 29 January 2021, 12pm-1pm, Alexandru I. Tomescu,
Paper: Subtree Isomorphism Revisited., SODA 2016, by Amir Abboud, Artūrs Bačkurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
Date and presenter: Friday 22 January 2021, 11am-12pm, Massimo Equi,
Paper: Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, SOFSEM 2021, by Massimo Equi, Veli Mäkinen, Alexandru I. Tomescu
Date and presenter: Friday 15 January 2021, 11am-12pm, Sebastian Schmidt,
Paper: SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing, 2012, by Anton Bankevich, Sergey Nurk, Dmitry Antipov, Alexey A. Gurevich, Mikhail Dvorkin, Alexander S. Kulikov, Valery M. Lesin, Sergey I. Nikolenko, Son Pham, Andrey D. Prjibelski, Alexey V. Pyshkin, Alexander V. Sirotkin, Nikolay Vyahhi, Glenn Tesler, Max A. Alekseyev, and Pavel A. Pevzner
Date and presenter: Friday 8 January 2021, 11am-12pm, Manuel Ariel Cáceres Reyes,
Paper: On the Complexity of Sequence to Graph Alignment (continued), Journal of Computational Biology, by Chirag Jain, Haowen Zhang, Yu Gao, Srinivas Aluru.

2020:

Date and presenter: Friday 11 December 2020, 11am-12pm, Manuel Ariel Cáceres Reyes,
Paper: On the Complexity of Sequence to Graph Alignment , Journal of Computational Biology, by Chirag Jain, Haowen Zhang, Yu Gao, Srinivas Aluru.
Date and presenter: Friday 27 November 2020, 11am-12pm, Alexandru Tomescu and Sebastian Schmidt,
Paper: Fast and accurate long-read assembly with wtdbg2, Nature Methods, (code) by Jue Ruan and Heng Li.
Date and presenter: Friday 20 November 2020, 11am-12pm, Shahbaz Khan,
Paper: Efficient Construction of Hierarchical Overlap Graphs (SPIRE 2020), by Sung Gwan Park, Bastien Cazaux, Kunsoo Park, Eric Rivals
Date and presenter: Friday 13 November 2020, 11am-12pm, Manuel Ariel Cáceres Reyes,
Paper: On the Hardness and Inapproximability of Recognizing Wheeler Graphs (ESA 2019), by Daniel Gibney and Sharma V. Thankachan.
Date and presenter: Friday 6 November 2020, 11am-12pm, Sebastian Schmidt,
Paper: Lower Bounds for External Memory Integer Sorting via Network Coding (STOC 2019), by Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi.
Date and presenter: Friday 23 October 2020, 11am-12pm, Jarno N. Alanko,
Paper: Bifrost – Highly parallel construction and indexing of colored and compacted de Bruijn graphs, by Guillaume Holley, Páll Melsted.
Date and presenter: Friday 16 October 2020, 11am-12pm, Shahbaz Khan
Paper: Direct Superbubble Detection, Algorithms 12(4): 81 (201) (conitnued), by Fabian Gärtner, Peter F. Stadler.
Date and presenter: Friday 9 October 2020, 11am-12pm, Shahbaz Khan
Paper: Direct Superbubble Detection, Algorithms 12(4): 81 (201) (first half), by Fabian Gärtner, Peter F. Stadler.
Date and presenter: Friday 2 October 2020, 11am-12pm, Alexandru Tomescu
Paper: Strain-aware assembly of genomes from mixed samples using variation graphs, RECOMB 2020, by Jasmijn A. Baaijens, Leen Stougie, Alexander Schönhuth.
Date and presenter: Friday 25 September 2020, 11am-12pm, Massimo Equi
Paper: Simple Reductions from Formula-SAT to Pattern Matching on Labeled Graphs and Subtree Isomorphism (arxiv), by Daniel Gibney, Gary Hoppenworth, Sharma V. Thankachan.
Date and presenter: Friday 18 September 2020, 11am-12pm, Jun Ma
Paper: Haplotype-resolved de novo assembly with phased assembly graphs (Arxiv), by Haoyu Cheng, Gregory T Concepcion, Xiaowen Feng, Haowen Zhang, Heng Li.
Date and presenter: Wednesday 9 September 2020, 2-3pm, Sebastian Schmidt
Paper: A New Approach to Fragment Assembly in DNA Sequencing (RECOMB 01), by Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman
Date and presenter: Wednesday 2 September 2020, 2-3pm, Manuel Ariel Cáceres Reyes
Paper: TransBorrow: genome-guided transcriptome assembly by borrowing assemblies from different assemblers (Genome Research), by Ting Yu, Zengchao Mu, Zhaoyuan Fang, Xiaoping Liu, Xin Gao, and Juntao Liu.
Date and presenter: Wednesday 26 August 2020, 2-3pm, Alexandru Tomescu
Paper: AStarix: Fast andOptimal Sequence-to-Graph Alignment (RECOMB 2020), by Pesho Ivanov, Benjamin Bichsel, Harun Mustafa, André Kahles, Gunnar Rätsch, Martin T. Vechev
Date and presenter: Wednesday 12 August 2020, 2-3pm, Shahbaz Khan
Paper: Linear-time superbubble identification algorithm for genome assembly (TCS 2016), by Ljiljana Brankovica, Costas S. Iliopoulos, Ritu Kundu, Manal Mohamed, Solon P. Pissis, Fatima Vayani