Recherche

"Tu aimerais changer la face du monde, c'est louable mais cela me fait peur. Imagine que tu le rates et qu'il ait le même nez que Michael Jackson."
Klub des loosers, Toute la vérité

Je m'interesse à l'aspect algorithmique (NP-Complétude, algortihmes FPT, W[1]-difficulté, approximation,...) de certains problèmes motivés depuis la biologie (recherche de motifs dans les réseaux biologiques, structures d'ARN...). Si ces sujets vous interessent (oh !), une première approche peut-être trouvée dans ma thèse. Je me suis particulièrement interessé au problème Graph Motif, dont un (une tentative de ?) panorama des définitions et résultat est disponible ici.

J'essaie de maintenir une liste des taux d'acceptation de quelques conférences, ici.

Publications :

Voici l'ensemble de mes publications :

JabRef references

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}
}

Présentations :

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.

Logiciels (disponibles sur demande) :

GraMoFoNe, un plugin Cytoscape. Implémentation pour le problème Graph Motif.
PADA1, une implémentation python pour la recherche de graphes (motifs) dans des Réseaux d'Interactions Protéiques. Complexité dépendante du Vertex Feedback Set du motif. Détail des algorithmes dans mon rapport de stage de Master 2. Utilisation de BLAST, Network-X, Psyco, GraphViz. (2008)
Une implémentation Java sous licence GPL de complexité cubique pour répondre au problème du Road Coloring, d'après un article de Trahtman. Travail avec Marie-Pierre Béal et Dominique Perrin (slides). Utilisation de GraphViz et de REGAL pour les tests. Pour information, Marie-Pierre Beal et Dominique Perrin ont donné un algorithme de complexité quadratique. Code source. (2008)
Une implémentation Python pour la recherche automatique de mots-clés dans un texte en utilisant un corpus d'apprentissage. Utilisation du wrapper python pour treetagger de Laurent Pointal. Projet pour Xeres. (2007)
Une gestion en C du graphe des commentaires et des groupes de Flickr pour analyse sociologique. Travail avec Christophe Prieur. (2007)

Some pointers on lectures

Vous m'y avez peut-être vu :

AGAPE 2013 du 28 janvier au 1er février 2013
Verona University, Italy 5-15 decembre 2012
COMATEGE-SeqBio 2012 les 26 et 27 novembre 2012
1ere journées GT CoA les 21 et 22 novembre 2012
27ème JFRO le 20 novembre 2012
JGA 2012 du 14 au 16 novembre 2012
CSR 2012, 3/07/2012 - 7/07/2012
APEX 2012 : 28/02/2012
CATS 2011 : 17/01/11 - 20/01/11
GTSeq : 10/01/11 - 11/01/11
Milan Bicocca, Italy : 29/11/10 - 3/12/10
Udine, Italy : 22/11/10 - 27/11/10
LINA : 21/06/10 - 25/06/10
ED MSTIC : 10/06/10
LIRMM : 25/05/10 - 28/05/10
MCBS 2010 : 03/05/10 - 07/05/10
Udine, Italy : 12/04/10 - 28/04/10
EJC GDR-IM 2010 : 29/03/10 - 02/04/10
BICoB 2010 : 24/03/10 - 26/03/10
Lisboa, Portugal : 9/12/09 - 16/12/09
JOBIM 2009 : 09/06/09 - 11/06/09
AGAPE 2009 : 25/05/09 - 29/05/09
ISBRA 2009 : 13/05/09 - 16/05/09
EJC GDR-IM 2009 : 30/03/09 - 03/04/09
WALCOM 2009 : 18/02/09 - 20/02/09
RECOMB-CG 2008 : 13/10/08 - 15/10/08

Recherche

Publications :

Présentations :

Logiciels (disponibles sur demande) :

Some pointers on lectures

Vous m'y avez peut-être vu :

CFP :