News:
  • Nov'24: New paper: “FroM Superstring to Indexing: a space-efficient index for unconstrained k-mer sets using the Masked Burrows-Wheeler Transform (MBWT)
  • Nov'24: Tam joined us as a PhD student to work on novel computational methods for phylogenetic compression
  • Oct'24: Amory joined us as an MSc. student to work on the interplay between phylogenetic compression and the Burrows-Wheeler Transform
  • Sep'24: New edition of the BOX Experimental Bioinformatics course at École normale supérieure de Rennes (with Riccardo Vicedomini)
  • Sep'24: Obtained an AIS Rennes Métropole grant: “Développement d’algorithmes efficaces pour la recherche sublinéaire dans de grandes bases de données génomiques”
  • Aug'24: Presentation at Stringmasters 2024: “Developing the phylogenetic transform”
  • Jun'24: Obtained an ANR grant: “ReAll: Real-time read alignment to all bacterial genomes on laptops
  • Jun'24: Ondřej defended his BSc thesis, started an internship at Eligo Bioscience, and will continue at ETH Zürich
  • Jun'24: Léo joined us as a PhD student to work on sublinear algorithms for large genome collections
  • May'24: Ondřej won the SVOČ competition for the best 2024 thesis in Theoretical Computer Science / Machine Learning in Czechia and Slovakia
  • May'24: Invited talk at the EMBL-EBI Kmer/sequence indexing workshop 2024: “Efficient search of microbial genomes by phylogenetic compression”
Karel Břinda, Ph.D.

Karel Břinda, Ph.D.

Permanent Researcher (Inria Starting Faculty)

Inria/Irisa Rennes

About

I hold a permanent PI position at Inria, the French National Institute for Research in Digital Science and Technology. I’m based at the Inria Center at Rennes University, where I’m part of the GenScale project team. I’m also associated with the IRISA Research Institute of Computer Science and Random Systems. Prior to joining Inria in 2022, I was a postdoctoral fellow and a research associate in biomedical informatics and epidemiology at Harvard Medical School and the Harvard T.H. Chan School of Public Health. I received my Ph.D. in computer science from the University of Paris-Est in 2016 and a master’s degree in mathematical computer science from the Czech Technical University in Prague in 2013.

Our research focuses on the intersection of computer science and biology, with applications in epidemiology and medicine. We develop new bioinformatics methods to analyze big genomic datasets, with the ultimate goals of enabling the rapid diagnosis of antibiotic resistance, monitoring of the spread of pathogens worldwide, and enabling instant searches across all publicly deposited DNA sequence data. Our research questions range from the theoretical aspects of computer science to the practical end-to-end protocols used in laboratories. In this context, we are particularly excited about the potential of emerging rapid and portable genomic technologies, such as nanopore sequencing or CRISPR tests.

Download my CV.

People

We're recruiting! Do you want to push the limits of computer science to achieve new breakthroughs in genomics? Seeking opportunities as a postdoc, PhD student, intern, or software engineer? Then we want to hear from you!    

Loren Dejoies, Ph.D.

Postdoctoral Researcher

Léo Ackermann

PhD student, Inria, co-supervised with Pierre Peterlongo

Tam Truong

PhD student, IRISA, co-supervised with Pierre Peterlongo

Francesca Brunetti

Visiting Ph.D. student from the Sapienza University of Rome

Amory Antao

MSc. student at École normale supérieure de Rennes, , co-supervised with Riccardo Vicedomini

Veronika Hendrychová

MSc. student at the Czech Technical University in Prague

Ondřej Sladký

BSc. student at Charles University in Prague, co-supervised with Pavel Veselý

Alumni

  • Arya Kaul, visiting Ph.D. student from Harvard Medical School, Chateaubriand fellow, 2023-2024
  • Léo Laffeach, MSc. student (École normale supérieure de Rennes), 2022–2023
  • Katya Milyutina, BSc. student (Charles University in Prague), 2022–2023

Selected Publications

  1. K. Břinda, L. Lima, S. Pignotti, N. Quinones-Olvera, K. Salikhov, R. Chikhi, G. Kucherov, Z. Iqbal, and M. Baym.

    Efficient and robust search of microbial genomes via phylogenetic compression,

    bioRxiv 2023.04.15.536996, 2023. [preprint] [software] [supplement]

  2. O. Sladký, P. Veselý, and K. Břinda.

    Masked superstrings as a unified framework for textual k-mer set representations,

    RECOMB-Seq, 2023. [preprint] [software] [supplement]

  3. K. Břinda, M. Baym, and G. Kucherov.

    Simplitigs as an efficient and scalable representation of de Bruijn graphs,

    Genome Biology 22(96), 2021. [preprint] [journal] [software] [supplement]

  4. K. Břinda, A. Callendrello, K. C. Ma, D. R. MacFadden, T. Charalampous, R. S. Lee, L. Cowley, C. B. Wadsworth, Y. H. Grad, G. Kucherov, J. O’Grady, M. Baym, and W. P. Hanage.

    Rapid inference of antibiotic resistance and susceptibility by genomic neighbour typing,

    Nature Microbiology 5, pp. 455–464, 2020. [preprint] [journal] [software] [supplement]

  5. K. Břinda, M. Sykulski, and G. Kucherov.

    Spaced seeds improve k-mer-based metagenomic classification,

    Bioinformatics 31(22), pp. 3584–3592, 2015. [preprint] [journal] [supplement]

For a full publication list, see Google Scholar.

Methods

A. Phylogenetic compression

Framework implementing phylogenetic compression, a technique using evolutionary history to guide compression and efficiently search large collections of microbial genomes using existing algorithms and data structures. This improves the compression ratios of assemblies, de Bruijn graphs, and k-mer indexes by one to two orders of magnitude.

Associated tools:

  • Phylign – BLAST-like search across all pre-2019 bacteria on standard desktops and laptop computers.
  • MiniPhy – Phylogenetic compression of extremely large genome collections

B. Metagenomic classification

  • ProPhyle - Accurate, resource-frugal, and deterministic metagenomic classification, based on k-mer propagation, simplitigs, and k-mer indexing using the Burrows-Wheeler Transform.

  • ProphAsm - rapid and memory-efficient computation of simplitigs (spectrum-preserving string sets) and set operations with k-mer sets.

  • ProPhex An efficient k-mer index based on the Burrows-Wheeler Transform.


C. Genomic Neighbor Typing

A proof-of-concept framework for Genomic Neighbor Typing for within-minutes predictions of antibiotic resistance during nanopore sequencing. Pipeline, library, two species databases (S. pneumoniae and N. gonorrhoeae), and demonstrations of within-minutes diagnostic from isolates and metagenomes.


D. Read mapping and variant calling

  • Ococo – Online variant and consensus caller, based on streaming and maintaining variant statistics in small counters per individual genomic positions, which enables real-time analyses of unsorted SAM/BAM data.

  • RNFtools – A generic format for naming simulated sequencing reads using arbitrary tools and the associated toolkit and pipeline for read simulation and read mapper evaluation.


E. Auxiliary tools

  • SAMsift – Advanced filtering and tagging of SAM/BAM alignments using Python expressions.

  • Disty McMatrixFace – Tool for computing a distance matrix from a core genome alignment.

  • NanoSim-H – An easy-to-use simulator of nanopore reads, a fork of NanoSim.

For a full software list, see the Github page.

Teaching

École normale supérieure de Rennes

  • Experimental Bioinformatics; BOX (Fall 2023, Lecturer)

    Masters' level course (M1), focused on computational methods for genomics. Taught jointly with Riccardo Vicedomini.

Harvard Medical School

  • Concepts in Genome Analysis; BMIF 201 (Fall 2019; TA)

    PhD level course, focused on quantitative aspects of genetics and genomics, including computational and statistical methods of genomic analysis. Close collaboration with Profs. Shamil R. Sunyaev, Michael Baym, Cheng-Zhong Zhang, and Heng Li.

Czech Technical University in Prague

  • Assistive Technology; 01ASTE (Falls 2010–2012; Instructor)

    Masters' level course.

  • Software Project; 01SWP1, 01SWP2 (Falls and springs 2010–2012; Supervisor)

    Masters' level course.

Selected media coverage

Interviews

  • BBC World Service – Science in Action – 13 Feb 2020

    Our paper about rapid diagnostics of antibiotic resistance was covered by BBC World Service in the show Science in Action (13 Feb 2020; starts at 8.10 minutes). 2020-BBC-ScienceInAction-GNT.mp3

  • The Bioinformatics Chat – Spectrum-preserving string sets and simplitigs – 28 Feb 2020

    Our paper about simplitigs for an efficient and scalable representation of de Bruijn graph was covered by the The Bioinformatics Chat podcast series (#42, 28 Feb 2020). 2020-TheBioinformaticsChat-Simplitigs.mp3

Other media coverage

Contact