Return to Team members / External members / Alumni and former members

Blerina Sinaimeri

blerina

 Blerina Sinaimeri

Université Lyon I – INRIA
UMR CNRS 5558 – LBBE 
Bâtiment G. Mendel, Villeurbanne
Email: blerina dot sinaimeri at inria dot fr

Research

I am a Researcher at INRIA ERABLE Team (CR). My research interests include Computational Biology, Combinatorics, Graph Theory and Graph Algorithms. You can find a full updated cv here. I am currently visiting Giuseppe Italiano at LUISS University in Rome, Italy.

Current teaching

  • Autumn 2020: Advanced Algorithms, M1, Univ. Claude Bernard – Lyon 1. Page of the course here
  • Fall 2017: Discrete Mathematics, Master of Bioinformatique et Modélisation (4BIM), Institut National des Sciences Appliquées (INSA) and M1 MIV, Univ. Claude Bernard – Lyon 1. Page of the course here.
  • Fall 2016: Network Algorithms for Molecular Biology , Dep. Inf. ENS Lyon. Page of the course here

 

What’s new?

  • I am in the PC of WEPA 2020, SeqBIM 2020 and CIAC 2021.

  • Check out our new tool for Cophylogeny: Capybara

  • Check out my talk at EvolCompGen – ISMB ECCB 2019 presenting our new tool AmoCoala. Video of the talk here.

  • I participated at the Conférences ISN et enseignement 2016 organized by INRIA. Video of the talk here

  • Check out our new tool for visualizing cophylogenetic reconciliations CophyTRees

Awards

  • 2010 Winner of the 2010 Italian Chapter EATCS Award for the best Ph.D. thesis in theoretical computer science.
  • 2009 Best PhD Student paper of the year , CS Department, Sapienza University of Rome.

Publications

Published articles are the Copyright of their respective publishers.

    • Peer-reviewed journals

      • A. Monti and B. Sinaimeri, String factorisations with maximum or minimum dimension, Theoretical Computer Science, 842: 65-73, 2020, pdf.
      • Y. Wang, A. Mary, M.-F. Sagot and B. Sinaimeri, Lazy listing of equivalence classes – A paper on dynamic programming and tropical circuits, (submitted) pdf
      • T. Calamoneri, M. Gastaledello, A. Mary, M.-F. Sagot and B. Sinaimeri, Algorithms for the quantitative Lock/Key model of cytoplasmic incompatibility, Algorithms for Molecular Biology , (to appear).

      • Y. Wang, A. Mary, M.-F. Sagot and B. Sinaimeri, Capybara: equivalence ClAss enumeration of coPhylogenY event-BAsed ReconciliAtions, Bioinformatics , 36(14): 4197-4199, 2020.
      • V. Acuña, R. Grossi, G. Italiano, L. De Lima, R. Rizzi, G. Sacomoto, M.-F. Sagot and B. Sinaimeri. On Bubble Generators in Directed Graphs, Algorithmica , 82(4): 898-914, 2020.
      • T. Calamoneri, A. Monti and B.Sinaimeri; Co-divergence and tree topology, Journal of Mathematical Biology, Volume 79, Issue 3, pp 1149–1167, 2019.
      • K. T. Huber, V. Moulton, M.-F. Sagot and B. Sinaimeri; Exploring and Visualising Spaces of Tree Reconciliations, Systematic Biology 68 (4), 607-618, 2019.
      • L.Urbini*, B.Sinaimeri*, C. Matias and M.-F.Sagot, Exploring the Robustness of the Parsimonious Reconciliation Method in Host-Symbiont Cophylogeny, IEEE/ACM Transactions on Computational Biology and Bioinformatics 16(3): 738-748 (2019).
      • A. Monti, B. Sinaimeri, On variants of Vertex Geography on undirected graphs, Discrete Applied Mathematics (DAM) Vol. 251, 268-275, 2018 pdf.
      • K. T. Huber, V. Moulton, M.-F. Sagot, B. Sinaimeri, Geometric medians in reconciliation spaces of phylogenetic trees, Information Processing Letters (IPL) , Vol. 136, 96-101, 2018.
      • L. I. Soares de Lima*, B. Sinaimeri*, G, Sacomoto, H. Lopez-Maestre, C. Marchet; V. Miele, M.-F. Sagot, V. Lacroix, Playing hide and seek with repeats in local and global de novo transcriptome assembly of short RNA-seq reads, Journal of Algorithms for Molecular Biology (AMB) 12(1), 2:1-2:19, 2017.
      • T. Calamoneri and B. Sinaimeri, Pairwise Compatibility Graphs: A Survey, SIAM Review 58(3): 445–460, 2016.
      • C. Baudet*, B. Donati*, B. Sinaimeri*, P. Crescenzi, C. Gautier, C. Matias and M-F. Sagot, Co-phylogeny Reconstruction via an Approximate Bayesian Computation, Systematic Biology 64 (3), 416-431, 2015. (pdf).
      • B. Donati, C. Baudet, B. Sinaimeri, P. Crescenzi and M-F. Sagot, EUCALYPT: Efficient tree reconciliation enumerator, Journal of Algorithms for Molecular Biology (AMB) 10(3), 2015. (pdf)
      • T. Calamoneri, A. Frangioni and B. Sinaimeri, Pairwise Compatibility Graphs of Caterpillars, Comput. J 57(11), 1616-1623, 2014.
      • T. Calamoneri, R. Petreschi and B. Sinaimeri, Pairwise compatibility property of some superclasses of threshold graphs Discrete Mathematics, Algorithms and Applications, 5(2), 2013. (pdf)
      • T. Calamoneri, E. Montefusco, R. Petreschi and B. Sinaimeri, Exploring Pairwise Compatibility graphs, Theoretical Computer Science 468: 23–36, 2013. (pdf)
      • T. Calamoneri and B. Sinaimeri, L(2,1)-labeling of oriented planar graphs, Discrete Applied Mathematics 161(12): 1719–1725, 2013. (pdf)
      • T. Calamoneri, D. Frascaria and B. Sinaimeri, All graphs with at most seven vertices are Pairwise Compatibility Graphs, Comput. J 56(7): 882–886, 2013.
      • A. Monti and B. Sinaimeri, Rainbow Graph Splitting, Theoretical Computer Science 412(39): 5315-5324, 2011. (pdf)
      • Z. Füredi, I. Kantor, A. Monti and B. Sinaimeri, On Reverse-Free Codes and Permutations, SIAM J. Discrete Math. 24(3): 964–978, 2010. (pdf)
      • J. Körner, G. Simonyi and B. Sinaimeri, On types of growth for graph-different permutations, J. Combin. Theory Ser. A 116: 713–723, 2009. (pdf)
      • J. Körner and B. Sinaimeri, On cancellative set families, Combinatorics, Probability and Computing, 16(4): 767–773, 2007. (pdf)

    • Conferences and Workshops

      • V. Acuña, G. Italiano, L. De Lima, L. Pepè Sciarria, M.-F. Sagot and B. Sinaimeri. A family of tree-based generators for bubbles in directed graphs, 31rd International Workshop on Combinatorial Algorithms, IWOCA 2020 , Bordeaux, France, June 8-10, 2020.
      • V. Acuña, R. Grossi, G. Italiano, L. De Lima, R. Rizzi, G. Sacomoto, M.-F. Sagot and B. Sinaimeri. On Bubble Generators in Directed Graphs, 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017 , Eindhoven, The Netherlands, June 21-23, 2017.
      • T. Calamoneri, M. Gastaldello, A. Mary, M.-F. Sagot and B. Sinaimeri. On Maximal Chain Subgraphs and Covers of Bipartite Graphs, 27th International Workshop on Combinatorial Algorithms IWOCA 2016 , Helsinki, Finland, August 17–19, 2016.
      • L. Urbini, B. Sinaimeri, C. Matias and M.-F. Sagot, Robustness of the Parsimonious Reconciliation Method in Cophylogeny, Algorithms for Computational Biology, Third International Conference, AlCoB 2016.
      • L. Bulteau, G. Sacomoto, B. Sinaimeri, Computing an Evolutionary Ordering is Hard, The VIII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2015) pdf.
      • G. Sacomoto, B. Sinaimeri, C. Marchet, V. Miele, M-F. Sagot, V. Lacroix, Navigating in a Sea of Repeats in RNA-seq without Drowning, 14th Workshop on Algorithms in Bioinformatics (WABI 2014) , LNCS, 82–96. (preliminary version here)
      • T. Calamoneri and B. Sinaimeri, Relating threshold tolerance graphs to other graph classes, 16th Italian Conference on Theoretical Computer Science (ICTCS 2014) , 73–79.
      • V. Lacroix, A. Julien-Laferrière, G. Sacomoto, M.-F. Sagot, B. Sinaimeri and A. Trindade, De novo identification of repeats in RNA-seq: a de Bruijn graph based approach, Poster Session , 13th Workshop on Algorithms in Bioinformatics (WABI 2013) , Sophia Antipolis, France (2013).
      • T. Calamoneri, R. Petreschi and B. Sinaimeri, On relaxing the constraints in Pairwise Compatibility graphs, In: Md. S. Rahman and S.-i. Nakano (Eds.), WALCOM 2012, LNCS vol. 7157,124–135, Springer, Berlin (2012).
      • Z. Füredi, I. Kantor, A. Monti and B. Sinaimeri, On Reverse-Free Codes and Permutations, Electronic Notes in Discrete Mathematics vol. 38, 383–387, EuroComb 2011, Budapest, (2011) (extended abstract).
      • T. Calamoneri, R. Petreschi and B. Sinaimeri, On relaxing the constraints in Pairwise Compatibility graphs, accepted at Graph and Algorithms 2011 (GA 2011) , Workshop co-located with ICALP 2011, Zürich, Switzerland.
      • T. Calamoneri and B. Sinaimeri, Labeling of oriented planar graphs, accepted at the 10-th Cologne-Twente Workshop
        on graphs and combinatorial optimization (CTW 2011) 93–96, Frascati, Italy.
      • T. Calamoneri and B. Sinaimeri, L(2,1)-labeling of oriented planar graphs, accepted at the 12th Italian Conference on Theoretical Computer Science (ICTCS 2010), Camerino, Italy (short abstract).

    • Ph.D. Thesis

      • B. Sinaimeri, Structures of Diversity, Computer Science Department, Sapienza University of Rome, February 2010. (pdf)

Software

    • Capybara
      Phylogenetic tree reconciliation is the method of choice in analysing host-symbiont systems. Despite the many reconciliation tools that have been proposed in the literature, two main issues remain unresolved: (i) listing suboptimal solutions (i.e. whose score is “close” to the optimal ones) and (ii) listing only solutions that are biologically different “enough”. The first issue arises because the optimal solutions are not always the ones biologically most significant; providing many suboptimal solutions as alternatives for the optimal ones is thus very useful. The second one is related to the difficulty to analyse an often huge number of optimal solutions. In this paper, we propose Capybara that addresses both of these problems in an efficient way. Furthermore, it includes a tool for visualising the solutions that significantly helps the user in the process of analysing the results..
    • COALA
      Many of the most used algorithms for co-phylogenetic reconstructions on host-parasite associations are based on an event-based model, where the events include in general (a subset of) co-speciation, duplication, loss, and host-switch. All known event-based methods then assign a cost to each type of event in order to find a reconstruction of minimum cost. The main problem with this approach is that the cost of the events strongly influence the reconciliation obtained. COALA was designed for estimating the frequency of the events based on an approximate Bayesian computation approach.
    • EUCALYPT
      EUCALYPT was designed for reconciling phylogenetic trees of host and parasite systems. It can also be applied to gene/species trees in the context of the DTL model. EUCALYPT has many features. It can find one optimal reconciliation of a pair of trees, can compute the number of all optimal solutions, and most important can list them all. The first two problems are handled in polynomial time, while the enumeration has a polynomial delay complexity. Eucalypt could also compute some statistics on the solutions obtained and allows for arbitrary cost values. It can also consider a variation of the problem where the length of host-switches is bounded by some parameter in input.

Permanent link to this article: https://team.inria.fr/erable/en/team-members/blerina-sinaimeri/