Research



I am interested in the algorithmic side (NP-hardness, FPT, W[1]-hardness, approximation,...) of some biological problems (Biological Networks, RNA...). During my thesis, I particularly worked on the Graph Motif problem, for which a (tentative) resume of definitions and result can be found here.

I try to maintain a list of acceptance ratio of some conferences, here.

Publications :

Here is my publication list
JabRef references
Matching entries: 0
settings...
Article
Blin, Guillaume and Rizzi, Romeo and Sikora, Florian and Vialette, Stéphane:
Minimum Mosaic Inference of a Set of Recombinants.
International Journal of Foundations of Computer Science (IJFCS) Vol. 24 (1) , pp. 51-66. 2013.

[BibTeX] [DOI] [URL]
BibTeX: 
@article{Blin2013,
  author = {Blin, Guillaume and Rizzi, Romeo and Sikora, Florian and Vialette, Stéphane},
  title = {Minimum Mosaic Inference of a Set of Recombinants},
  journal = {International Journal of Foundations of Computer Science (IJFCS)},
  year = {2013},
  volume = {24},
  number = {1},
  pages = {51-66},
  url = {http://hal-upec-upem.archives-ouvertes.fr/hal-00679269},
  doi = {10.1142/S0129054113400042}
}
Guillemot, Sylvain and Sikora, Florian:
Finding and counting vertex-colored subtrees.
Algorithmica Vol. 65 (4) , pp. 828-844. 2013.

[BibTeX] [DOI] [URL]
BibTeX: 
@article{guillemotfinding,
  author = {Guillemot, Sylvain and Sikora, Florian},
  title = {Finding and counting vertex-colored subtrees},
  journal = {Algorithmica},
  year = {2013},
  volume = {65},
  number = {4},
  pages = {828-844},
  url = {http://arxiv.org/abs/1002.1880},
  doi = {10.1007/s00453-011-9600-8}
}
Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Sikora, Florian:
On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem.
Information Processing Letters Vol. 112 (7) , pp. 272 - 276. 2012.

[BibTeX] [DOI] [URL]
BibTeX: 
@article{blin12parameterized,
  author = {Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Sikora, Florian},
  title = {On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem},
  journal = {Information Processing Letters},
  year = {2012},
  volume = {112},
  number = {7},
  pages = {272 - 276},
  url = {http://hal-upec-upem.archives-ouvertes.fr/hal-00637255},
  doi = {10.1016/j.ipl.2011.12.009}
}
Blin, Guillaume and Sikora, Florian and Vialette, Stéphane:
Querying Graphs in Protein-Protein Interactions Networks using Feedback Vertex Set.
IEEE/ACM Transactions on Computational Biology and Bioinformatics Vol. 7 (4) , pp. 628-635. IEEE Computer Society, 2010. Special Issue-ISBRA 2009-Bioinformatics Research and Applications.

[BibTeX] [DOI] [URL]
BibTeX: 
@article{IGMA_BliSikVia10b,
  author = {Blin, Guillaume and Sikora, Florian and Vialette, Stéphane},
  title = {Querying Graphs in Protein-Protein Interactions Networks using Feedback Vertex Set},
  journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
  publisher = {IEEE Computer Society},
  year = {2010},
  volume = {7},
  number = {4},
  pages = {628--635},
  note = {Special Issue-ISBRA 2009-Bioinformatics Research and Applications},
  url = {http://igm.univ-mlv.fr/~fsikora/pub/2010-TCBB.pdf},
  doi = {http://doi.ieeecomputersociety.org/10.1109/TCBB.2010.53}
}
Inproceedings
Bazgan, Cristina and Chopin, Morgan and Nichterlein, André and Sikora, Florian:
Parameterized Approximability of Maximizing the Spread of Influence in Networks.
In Proc. of the 19th Annual International Computing and Combinatorics Conference (COCOON'13). (7936) , pp. 543-554. Springer-Verlag, 2013.

[BibTeX] [URL]
BibTeX: 
@inproceedings{Bazgan2013,
  author = {Bazgan, Cristina and Chopin, Morgan and Nichterlein, André and Sikora, Florian},
  editor = {Du, Dingzhu and Zhang, Guochuan},
  title = { Parameterized Approximability of Maximizing the Spread of Influence in Networks},
  booktitle = {Proc. of the 19th Annual International Computing and Combinatorics Conference (COCOON'13)},
  publisher = {Springer-Verlag},
  year = {2013},
  number = {7936},
  pages = {543-554},
  url = {http://arxiv.org/abs/1303.6907}
}
Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Rizzi, Romeo and Sikora, Florian:
Complexity Insights of the Minimum Duplication Problem.
In Proc. of 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012). Vol. 7147 of Lecture Notes in Computer Science , pp. 153-164. Springer, 2012.

[BibTeX] [DOI] [URL]
Abstract: The Minimum Duplication problem is a well-known problem in phylogenetics and comparative genomics. Given a set of gene trees, the Minimum Duplication problem asks for a species tree that induces the minimum number of gene duplications in the input gene trees. More recently, a variant of the Minimum Duplication problem, called Minimum Duplication Bipartite, has been introduced in [14], where the goal is to find all pre-duplications, that is duplications that precede, in the evolution, the first speciation with respect to a species tree. In this paper, we investigate the complexity of both Minimum Duplication and Minimum Duplication Bipartite problems. First of all, we prove that the Minimum Duplication problem is APX-hard, even when the input consists of five uniquely leaf-labelled gene trees (progressing on the complexity of the problem). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently by a randomized algorithm when the input gene trees have bounded depth.
BibTeX: 
@inproceedings{blin12complexity,
  author = {Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Rizzi, Romeo and Sikora, Florian},
  editor = {Mária Bieliková and Gerhard Friedrich and Georg Gottlob and Stefan Katzenbeisser and György Turán and Mária Bieliková and Gerhard Friedrich and Georg Gottlob and Stefan Katzenbeisser and György Turán},
  title = {Complexity Insights of the Minimum Duplication Problem},
  booktitle = {Proc. of 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012)},
  publisher = {Springer},
  year = {2012},
  volume = {7147},
  pages = {153-164},
  url = {http://hal-upec-upem.archives-ouvertes.fr/hal-00629047},
  doi = {10.1007/978-3-642-27660-6_13}
}
Rizzi, Romeo and Sikora, Florian:
Some results on more flexible versions of Graph Motif.
In Proc. of the 7th International Computer Science Symposium in Russia (CSR 2012). Vol. 7353 of Lecture Notes in Computer Science , pp. 278-289. Springer, 2012.

[BibTeX] [DOI] [URL]
BibTeX: 
@inproceedings{rizzi12some,
  author = {Rizzi, Romeo and Sikora, Florian},
  editor = {Edward A. Hirsch and Juhani Karhumäki and Arto Lepistö and Michail Prilutskii},
  title = {Some results on more flexible versions of Graph Motif},
  booktitle = {Proc. of the 7th International Computer Science Symposium in Russia (CSR 2012)},
  publisher = {Springer},
  year = {2012},
  volume = {7353},
  pages = {278-289},
  url = {http://arxiv.org/abs/1202.5184},
  doi = {10.1007/978-3-642-30642-6_26}
}
Yang, Xiao and Sikora, Florian and Blin, Guillaume and Hamel, Sylvie and Rizzi, Romeo and Aluru, Srinivas:
An Algorithmic View on Multi-related-segments: a unifying model for approximate common interval.
In Proc. of the 9th annual conference on Theory and Applications of Models of Computation (TAMC 2012). Vol. 7287 of Lecture Notes in Computer Science , pp. 319-329. Springer, 2012.

[BibTeX] [DOI] [URL]
BibTeX: 
@inproceedings{yang12algorithmic,
  author = {Yang, Xiao and Sikora, Florian and Blin, Guillaume and Hamel, Sylvie and Rizzi, Romeo and Aluru, Srinivas},
  editor = {Manindra Agrawal and S. Barry Cooper and Angsheng Li and Manindra Agrawal and S. Barry Cooper and Angsheng Li},
  title = {An Algorithmic View on Multi-related-segments: a unifying model for approximate common interval},
  booktitle = {Proc. of the 9th annual conference on Theory and Applications of Models of Computation (TAMC 2012)},
  publisher = {Springer},
  year = {2012},
  volume = {7287},
  pages = {319-329},
  url = {http://hal-upec-upem.archives-ouvertes.fr/hal-00630150},
  doi = {10.1007/978-3-642-29952-0_33}
}
Blin, Guillaume and Fertin, Guillaume and Mohamed-Babou, Hafedh and Rusu, Irena and Sikora, Florian and Vialette, Stéphane:
Algorithmic Aspects of Heterogeneous Biological Networks Comparison.
In 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA'11). Vol. 6831 of Lecture Notes in Computer Science , pp. 272-286. Springer-Verlag, 2011.

[BibTeX] [DOI] [URL]
BibTeX: 
@inproceedings{IGMA_BliFerMoh11,
  author = {Blin, Guillaume and Fertin, Guillaume and Mohamed-Babou, Hafedh and Rusu, Irena and Sikora, Florian and Vialette, Stéphane},
  editor = {Wang, W and Zhu, X and Du, D.-Z.},
  title = {Algorithmic Aspects of Heterogeneous Biological Networks Comparison},
  booktitle = {5th Annual International Conference on Combinatorial Optimization and Applications (COCOA'11)},
  publisher = {Springer-Verlag},
  year = {2011},
  volume = {6831},
  pages = {272--286},
  url = {http://hal.archives-ouvertes.fr/hal-00606375/en},
  doi = {10.1007/978-3-642-22616-8_22}
}
Blin, Guillaume and Rizzi, Romeo and Sikora, Florian and Vialette, Stéphane:
Minimum Mosaic Inference of a Set of Recombinants.
In 17th Computing: the Australasian Theory Symposium (CATS'11). Perth Vol. 119 of CRPIT , pp. 23-30. ACS, 2011.

[BibTeX] [URL]
BibTeX: 
@inproceedings{IGMA_BliRizSik10,
  author = {Blin, Guillaume and Rizzi, Romeo and Sikora, Florian and Vialette, Stéphane},
  editor = {Potanin, Alex and Viglas, Taso},
  title = {Minimum Mosaic Inference of a Set of Recombinants},
  booktitle = {17th Computing: the Australasian Theory Symposium (CATS'11)},
  publisher = {ACS},
  year = {2011},
  volume = {119},
  pages = {23--30},
  url = {http://hal.archives-ouvertes.fr/hal-00512458/fr/}
}
Blin, Guillaume and Sikora, Florian and Vialette, Stéphane:
GraMoFoNe: a Cytoscape plugin for querying motifs without topology in Protein-Protein Interactions networks.
In 2nd International Conference on Bioinformatics and Computational Biology (BICoB'10). Honolulu, USA , pp. 38-43. International Society for Computers and their Applications (ISCA), 2010.

[BibTeX] [URL]
BibTeX: 
@inproceedings{IGMA_BliSikVia10,
  author = {Blin, Guillaume and Sikora, Florian and Vialette, Stéphane},
  editor = {Al-Mubaid, Hisham},
  title = {GraMoFoNe: a Cytoscape plugin for querying motifs without topology in Protein-Protein Interactions networks},
  booktitle = {2nd International Conference on Bioinformatics and Computational Biology (BICoB'10)},
  publisher = {International Society for Computers and their Applications (ISCA)},
  year = {2010},
  pages = {38--43},
  url = {http://hal.archives-ouvertes.fr/hal-00425661/fr/}
}
Guillemot, Sylvain and Sikora, Florian:
Finding and counting vertex-colored subtrees.
In 35th International Symposium on Mathematical Foundations of Computer Science (MFCS'10). Brno, Czech Republic Vol. 6281 of LNCS , pp. 405-416. Springer, 2010.

[BibTeX] [DOI] [URL]
BibTeX: 
@inproceedings{IGMA_GuiSik10,
  author = {Guillemot, Sylvain and Sikora, Florian},
  editor = {Hlinený, Petr and Kucera, Antonín},
  title = {Finding and counting vertex-colored subtrees},
  booktitle = {35th International Symposium on Mathematical Foundations of Computer Science (MFCS'10)},
  publisher = {Springer},
  year = {2010},
  volume = {6281},
  pages = {405--416},
  url = {http://fr.arxiv.org/abs/1002.1880},
  doi = {10.1007/978-3-642-15155-2_36}
}
Blin, Guillaume and Fertin, Guillaume and Sikora, Florian and Vialette, Stéphane:
The Exemplar Breakpoint Distance for non-trivial genomes cannot be approximated.
In 3rd Annual Workshop on Algorithms and Computation (WALCOM'09). Kolkata, India Vol. 5431 of LNCS , pp. 357-368. Springer-Verlag, 2009.

[BibTeX] [DOI] [URL]
BibTeX: 
@inproceedings{IGMA_BliFerSik09,
  author = {Blin, Guillaume and Fertin, Guillaume and Sikora, Florian and Vialette, Stéphane},
  editor = {Das, S. and Uehara, R.},
  title = {The Exemplar Breakpoint Distance for non-trivial genomes cannot be approximated},
  booktitle = {3rd Annual Workshop on Algorithms and Computation (WALCOM'09)},
  publisher = {Springer-Verlag},
  year = {2009},
  volume = {5431},
  pages = {357--368},
  url = {http://igm.univ-mlv.fr/~gblin/pdf/Blin_Fertin_Sikora_Vialette_WALCOM_2009.pdf},
  doi = {10.1007/978-3-642-00202-1_31}
}
Blin, Guillaume and Sikora, Florian and Vialette, Stéphane:
Querying Protein-Protein Interaction Networks.
In 5th International Symposium on Bioinformatics Research and Applications (ISBRA'09). Fort Lauderdale, FL, USA Vol. 5542 of LNBI , pp. 52-62. Springer-Verlag, 2009.

[BibTeX] [DOI]

BibTeX: 
@inproceedings{IGMA_BliSikVia09,
  author = {Blin, Guillaume and Sikora, Florian and Vialette, Stéphane},
  editor = {Mandoiu, Ion and Narasimhan, Giri and Zhang, Yanqing},
  title = {Querying Protein-Protein Interaction Networks},
  booktitle = {5th International Symposium on Bioinformatics Research and Applications (ISBRA'09)},
  publisher = {Springer-Verlag},
  year = {2009},
  volume = {5542},
  pages = {52--62},
  doi = {10.1007/978-3-642-01551-9_6}
}
Phdthesis
Sikora, Florian:
Aspects algorithmiques de la comparaison d'éléments biologiques.
Université Paris-Est 2011. In French.

[BibTeX] [URL]
BibTeX: 
@phdthesis{Sikora2011,
  author = {Sikora, Florian},
  title = {Aspects algorithmiques de la comparaison d'éléments biologiques},
  school = {Université Paris-Est},
  year = {2011},
  note = {In French},
  url = {http://igm.univ-mlv.fr/~fsikora/these_0911.pdf}
}

Talks:

  • 2013-04 : Journées du LAMSADE: Comment trouver des problèmes difficiles faciles ?
  • 2012-10 : Séminaire LAMSADE
  • 2012-07 : CSR - Substitution talk for Approximating minimum-power edge-multicovers.
  • 2012-07 : CSR - Some results on more flexible versions of Graph Motif.
  • 2012-04 : Séminaire MabioVis, LABRI
  • 2011-09 : PhD. Thesis.
  • 2011-01 : Workshop Algorithmique, combinatoire du texte et applications en bio-informatique and CATS 2011 - Minimum Mosaic Inference of a Set of Recombinants.
  • 2010-05 : Séminaire Combi LINA - Recherche de motifs dans des graphes colorés.
  • 2010-05 : Séminaire LIRMM Doctorants - Recherche de motifs dans des graphes colorés.
  • 2010-05 : MSBC - GraMoFoNe: a Cytoscape plugin for querying motifs without topology in Protein-Protein Interactions networks. (Poster session)
  • 2010-03 : BICoB 10 - GraMoFoNe.
  • 2010-02 : Séminaire IRISA - Symbiose - Recherche de motifs dans des graphes colorés.
  • 2009-05 : ISBRA 09 - Querying Protein-Protein Interaction Networks.
  • 2009-02 : WALCOM 09 - The Exemplar Breakpoint Distance Problem is not approximable for genomes with duplicated genes.
  • 2008-10 : RECOMB-CG 08 - The Exemplar Breakpoint Distance is not approximable... at all. (Poster session)
  • 2008-09 : Soutenance de Stage de M2.
  • 2008-05 : Pré-Soutenance de Stage de M2, état de l'art du sujet.
  • 2008-03 : Présentation d'un article de Sémon et Wolfe.

Softs (available upon request) :

Some pointers on lectures

I was in:

CFP :