Blerina Sinaimeri
Université Lyon I – INRIA UMR CNRS 5558 – LBBE Bâtiment G. Mendel, Villeurbanne Email: blerina dot sinaimeri at inria dot frResearch
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
Current teaching
 Spring 2018: 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.
 Spring 2017: Advanced Algorithms, M1, 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?
 Check out my talk at EvolCompGen – ISMB ECCB 2019 presenting our new tool AmoCoala. Video of the talk here.
 I am a PC member of IWOCA 2019.
 I am a PC member of WABI 2019.
 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.

Peerreviewed journals
 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 , 2019, (to appear) https://doi.org/10.1007/s0045301900619z.
 T. Calamoneri, A. Monti and B.Sinaimeri; Codivergence 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), 607618, 2019.
 L.Urbini*, B.Sinaimeri*, C. Matias and M.F.Sagot, Exploring the Robustness of the Parsimonious Reconciliation Method in HostSymbiont Cophylogeny, IEEE/ACM Transactions on Computational Biology and Bioinformatics 16(3): 738748 (2019).
 A. Monti, B. Sinaimeri, On variants of Vertex Geography on undirected graphs, Discrete Applied Mathematics (DAM) Vol. 251, 268275, 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, 96101, 2018.
 L. I. Soares de Lima*, B. Sinaimeri*, G, Sacomoto, H. LopezMaestre, 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 RNAseq reads, Journal of Algorithms for Molecular Biology (AMB) 12(1), 2:12: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 MF. Sagot, Cophylogeny Reconstruction via an Approximate Bayesian Computation, Systematic Biology 64 (3), 416431, 2015. (pdf).
 B. Donati, C. Baudet, B. Sinaimeri, P. Crescenzi and MF. 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), 16161623, 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): 53155324, 2011. (pdf)
 Z. Füredi, I. Kantor, A. Monti and B. Sinaimeri, On ReverseFree 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 graphdifferent 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, 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 GraphTheoretic Concepts in Computer Science, WG 2017 , Eindhoven, The Netherlands, June 2123, 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 LatinAmerican Algorithms, Graphs and Optimization Symposium (LAGOS 2015) pdf.
 G. Sacomoto, B. Sinaimeri, C. Marchet, V. Miele, MF. Sagot, V. Lacroix, Navigating in a Sea of Repeats in RNAseq 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. JulienLaferrière, G. Sacomoto, M.F. Sagot, B. Sinaimeri and A. Trindade, De novo identification of repeats in RNAseq: 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 ReverseFree 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 colocated with ICALP 2011, Zürich, Switzerland.
 T. Calamoneri and B. Sinaimeri, Labeling of oriented planar graphs, accepted at the 10th CologneTwente 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
 COALA
Many of the most used algorithms for cophylogenetic reconstructions on hostparasite associations are based on an eventbased model, where the events include in general (a subset of) cospeciation, duplication, loss, and hostswitch. All known eventbased methods then assign a cost to each type of event in order to ﬁnd a reconstruction of minimum cost. The main problem with this approach is that the cost of the events strongly inﬂuence 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 hostswitches is bounded by some parameter in input.