News:
  • Nov'23: Arya and Veronika presented their projects at SeqBIM 2023: “Developing phylog.-colored dBG for bact. gene birth detection” and “Math. model of phylog. compr.”
  • Nov'23: Francesca joined our group! Welcome!
  • Nov'23: Veronika won the 2nd-place award for her BSc. thesis at the Rektorys competion for the best math theses! Congratulations!
  • Nov'23: Invited talk at Graphs & Bioinformatics 2023 at Sorbonne University in Paris: “K-mers and their graphs in computational biology”
  • Oct'23: Major update of phylogenetic compression web and MOF-Compress - everything now fully documented and configurable
  • Oct'23: Invited talk at the Alpaca/Pangaia seminar: “Efficient and Robust Search of Microbial Genomes via Phylogenetic Compression”
  • Sep'23: Arya and Veronika joined our group! Welcome!
  • Sep'23: Our “Experimental Bioinformatics” course at ENS Rennes started (taught jointly with Riccardo Vicedomini)!
  • Jun'23: Invited talk at the University Hospital of Düsseldorf: “Rapid inference of antibiotic resistance and susceptibility by genomic neighbor typing”
  • Jun'23: Talk at Heinrich Heine University Düsseldorf: “Towards comprehensive sequence data search engines”
  • Jun'23: Invited talk at CPM Summer School 2023 at ENS Paris: “Under the hood: the role of string algorithms in contemporary biological research”
  • Apr'23: Ondřej presented masked superstrings on RECOMB-Seq 2023 (see the recording on YouTube)
  • Apr'23: Phylogenetic compression preprinted on bioRxiv
Karel Břinda, Ph.D.

Karel Břinda, Ph.D.

Permanent Researcher (Inria Starting Faculty)

Inria/Irisa Rennes

Biography

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 my master’s degree in mathematical computer science from the Czech Technical University in Prague in 2013.

The research of my group focuses on the intersection of computer science and biology, with applications in epidemiology and medicine. We develop novel bioinformatics techniques for DNA data search and analysis, with the ultimate goal of enabling rapid diagnoses of antibiotic resistance at point-of-care settings, better monitoring of the spread of pathogens world-wide, and real-time searching of all publicly deposited DNA sequence data. Our research questions span 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 the 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!     --- Current open positions:  ➀ PhD student  ➁ SW engineer  ➂ M1/M2 student (intern)  

Loren Dejoies, Ph.D.

Postdoctoral Researcher

Gaëtan Benoit, Ph.D.

Software Engineer

Arya Kaul

Visiting Ph.D. student from the Baym lab at Harvard Medical School (Chateaubriand fellow)

Francesca Brunetti

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

Veronika Hendrychová

Visiting MSc. student from the Czech Technical University in Prague (Erasmus)

Ondřej Sladký

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

Alumni

  • Léo Laffeach, MSc. student, École normale supérieure de Rennes
  • Katya Milyutina, BSc. student, Charles University in Prague

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:

  • MOF-Search – BLAST-like search across all pre-2019 bacteria on standard desktops and laptop computers.
  • MOF-Compress – Phylogenetic compression of individual genome batches.

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 analyzes 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 joinly 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