Comparative genomics.

• Reconstruction and assembly of ancestral and ancient genomes (See also Section "Consecutive-Ones Property and PQ-trees" in Discrete Mathematics, algorithms and computational complexity below)
  • Improved assemblies and comparison of two ancient Yersinia pestis genomes. bioRxiv:073445. 2016.
  • The SCJ small parsimony problem for weighted gene adjacencies. LNCS/LNBI 9683:200-210. ISBRA 2016.
    The SCJ small parsimony problem for weighted gene adjacencies. arXiv:1603.08819 [cs.DS]. 2016.
  • Scaffolding of Ancient Contigs and Ancestral Reconstruction in a Phylogenetic Framework. LNCS/LNBI 8826:135-143, BSB 2014.
  • FPSAC: Fast Phylogenetic Scaffolding of Ancient Contigs. Bioinformatics, 29:2987-2994. 2013.
    The genome of the medieval Black Death agent (extended abstract). arXiv:1307.7642 [q-bio.GN]. 2013.
  • ANGES: reconstructing ANcestral GEnomeS maps. Bioinformatics, 28:2388-2390. 2012.
  • Mapping ancestral genomes with massive gene loss: a matrix sandwich problem. Bioinformatics 27:i257-i265, ISMB/ECCB 2011.
  • Yeast ancestral genome reconstructions: the possibilities of computational methods II. J. Comput. Biol. 17:1097-1112. 2010.
  • Reconstructing the architecture of the ancestral amniote genome. Bioinformatics 27(19):2664-2671. 2011.
    Insight into the structural evolution of amniote genomes. Poster 137 (abstract), CSHL Genome Informatics 2009.
    Prediction of contiguous ancestral regions in the amniote ancestral genome. LNCS/LNBI 5542:173-185, ISBRA 2009.
    Prédiction de synténies dans le génome ancestral des amniotes. Paper 11, JOBIM 2008.
  • A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes. PLoS Comput. Biol. 4(11):e1000234. 2008
  • Reconstructing ancestral gene orders using conserved intervals. LNCS/LNBI 3240:14-25, WABI 2004.
  • Intervalles conservés et Neighbor-Joining. Comptes-rendus des 11emes Rencontres de la Société Francophone de Classification, pp. 111-114. 2004.
  
  
• Cancer genomics and NGS
  • Joint inference of genome structure and content in heterogeneous tumor samples. LNCS/LNBI 9069:256-258, RECOMB 2015.
    Joint inference of genome structure and content in heterogeneous tumor samples, arXiv:1504.03080 [q-bio.GN]. 2015.
  • Consistency-based detection of potential tumor-specific deletions in matched normal/tumor genomes. BMC Bioinformatics 12(Suppl 9):S21 (Proceedings of RECOMB-CG). 2011.
  
  
• Evolution of gene families and gene adjacencies.
  • ecceTERA: Comprehensive gene tree-species tree reconciliation using parsimony. Bioinformatics 32(13)56-58. 2016.
  • Ancestral gene synteny reconstruction improves extant species scaffolding. BMC Genomics 16(Suppl 10):S11 (Proceedings of RECOMB-CG). 2015.
    Ancestral gene synteny reconstruction improves extant species scaffolding. bioRxiv:023085
  • Assessing the robustness of parsimonious predictions for gene neighborhoods from reconciled phylogenies. LNCS/LNBI 9096:260-271, ISBRA 2015.
    Preprint: HAL: hal-0104587, arXiv:1503.05292.
  • Evolution of genes neighborhood within reconciled phylogenies: an ensemble approach. BMC Bioinformatics 2015, 16(Suppl 19):S6, 2015.
    Evolution of genes neighborhood within reconciled phylogenies: an ensemble approach. BiorXiv:026310, 2015.
    Evolution of genes neighborhood within reconciled phylogenies: an ensemble approach. LNCS/LNBI 8826:49-56, BSB 2014.
  • Polytomy Refinement for the Correction of Dubious Duplications in Gene Trees. Bioinformatics 30:i519-i526, ECCB 2014.
  • Duplication, Rearrangement and Reconciliation: A Follow-Up 13 Years Later. Computational Biology 19:47-62, Models and Algorithms for Genome Evolution. 2013.
  • An Efficient Method for Exploring the Space of Gene Tree/Species Tree Reconciliations in a Probabilistic Framework. IEEE/ACM TCBB 9(1):26-39. 2012.
    An Efficient Method for Exploring the Space of Gene Tree/Species Tree Reconciliations in a Probabilistic Framework. LIRMM technical report RR-10002. 2010.
  • A 2-Approximation for the Minimum Duplication Speciation Problem J. Comp. Biol. 18:1041-1053. 2011.
    An approximation algorithm for computing a parsimonious first speciation in the gene duplication model. LNCS/LNBI 6398:290-301, RECOMB-CG 2010.
    A 3-approximation algorithm for computing a parsimonious first speciation in the gene duplication model. arXiv:cs.DM/0904.1645v2 and HAL: hal-00374851, version 2. 2009.
  • Branch-and-Bound Approach for Parsimonious Inference of a Species Tree From a Set of Gene Family Trees. Chapter 29 of Software Tools and Algorithms for Biological Systems. 2011.
    Branch-and-Bound Approach for Parsimonious Inference of a Species Tree From a Set of Gene Family Trees. LIRMM technical report RR-10001. 2010.
  • New perspectives on gene family evolution: losses in reconciliation and a link with supertrees. LNCS/LNBI 5541:46-58, RECOMB 2009.
  • Space of Gene/Species Trees Reconciliations and Parsimonious Models, J. Comput. Biol., 16(10):1399-1418. 2009.
    Algorithms for exploring the space of gene tree/species tree reconciliations. LNCS/LNBI 5267:1-13, RCG 2008.
  • Gene family evolution by duplication, speciation and loss. J. Comput. Biol. 15:1043-1062. 2008.
    Inferring a duplication, speciation and loss history from a gene tree (extended abstract). LNCS/LNBI 4751:45-57, RCG 2007.
    Inferring a duplication and speciation history from a gene tree. Poster T69, SMBE 2007.
  
  
• Perfect rearrangement algorithms
  • Average-case analysis of perfect sorting by reversals. DMAA 3(3):369-392. 2011.
    Average-case analysis of perfect sorting by reversals. LNCS 5577:314-325, CPM 2009.
    Average-case analysis of perfect sorting by reversals. arXiv:math.CO/0901.2847 and HAL:hal-00354235, version 1. 2009.
  • Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes, J. Comput. Biol., 16(10):1287-1309. 2009.
    Perfect DCJ rearrangement. LNCS/LNBI 5267:158-169, RCG 2008.
  • A more efficient algorithm for perfect sorting by reversals. IPL 106:90-95. 2008.
  • Perfect sorting by reversals is not always difficult. IEEE/ACM TCBB 4:4-16. 2007.
    Perfect sorting by reversals is not always difficult (extended abstract). LNCS/LNBI 3692:228-238, WABI 2005.
  • Conserved structures in evolution scenarios. LNCS/LNBI 3388:1-15, RCG 2004.


• RNA secondary structure comparison
  • Counting, generating and sampling tree alignments. LNCS/LNBI 9702:53-64. AlCoB 2016
    Counting, generating and sampling tree alignments. Preprint. 2016.
  • The Bralibase dent: A tale of benchmark design and interpretation. Briefings in Bioinformatics. Advance access. 2016.
  • Chaining fragments in sequences: to sweep or not (Extended abstract). LNCS 9309:116-123, SPIRE 2015.
    Chaining fragments in sequences: to sweep or not. arXiv:1506.07458 [cs.DS]
  • An Unambiguous And Complete Dynamic Programming Algorithm For Tree Alignment. arXiv:1505.05983, 2015.
  • Chaining Sequence/Structure Seeds for Computing RNA Similarity. J. Comput. Biol. 23:205-217. 2015.
    Chaining Sequence/Structure Seeds for Computing RNA Similarity. CMSR 2014, pp. 1-12. 2014.
  • Efficient chaining of seeds in ordered trees. JDA 14:107-118. 2012.
    Efficient chaining of seeds in ordered trees. arXiv:q-bio.QM/1007.0942. 2010.
    Efficient chaining of seeds in ordered trees. LNCS 6460:260-273, IWOCA 2010.
  • BRASERO: A resource for benchmarking RNA secondary structure comparison algorithms. Advances in Bioinformatics, article 893048. 2012.
    Benchmarking RNA secondary structure comparison algorithms. Poster 77 (abstract), JOBIM 2008.
  • A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes. TCS 412:753-764. 2011.
    New algorithms for aligning nested arc-annotated sequences. LaBRI Research Report 1443-08. 2008.
  • RNA StrAT: RNA Structure Analysis Toolkit. Poster D31 (abstract), ISMB 2008.
    RNA StrAT. Webserver. 2007.
  • An edit distance between RNA stem-loops. LNCS 3772:334-345, SPIRE 2005.


• Conserved structures in gene orders (See also section "Common intervals of permutations" in Discrete Mathematics, algorithms and computational complexity below)
  • Formal models of gene clusters. Chapter 8 of Bioinformatics Algorithms: Techniques and Applications , pp. 177-202. 2008.
  • A software tool for whole genomes synteny comparisons. Poster, RCG 2005.
  • Fast identification of gene clusters in prokaryotic genomes. Texts in Algorithms 5:??-??, CompBioNets 2005. Additional material.
    Fast identification of gene clusters in prokaryotic genomes. Poster, RCG 2005.
  
  
• Computing gene order distances and orthologs from genomes with duplicated genes
  • The Potential of Family-Free Genome Comparison. Computational Biology 19:287-307, Models and Algorithms for Genome Evolution. 2013.
  • Inferring positional homologs using common intervals of sequences. LNCS/LNBI 4205:24-38, RCG 2006. Additional material.
    CIGAL: Common Intervals Global ALigner. Poster, International Conference on Phylogenomics 2006.
  • Comparing genomes with duplicates: a computational complexity point of view. IEEE/ACM TCBB 4(4):523-534. 2007.
    Genome containing duplicates are hard to compare (extended abstract). LNCS 3992:783-790, IWBRA 2006.
  • Genes order and phylogenetic reconstruction: application to gamma-Proteobacteria. LNCS/LNBI 3678:11-20, RCG 2005. Additional material.
  • The breakpoints distance for signed sequences. Texts in Algorithms 3:3-16, CompBioNets 2004.
  
  
• Virtual hybridation for gene order datasets.
  • Exploring genome rearrangements using virtual hybridization. Adv. Bioinfo. Comput. Biol. 5:205-214, APBC 2007.
    Exploring genome rearrangements using virtual hybridization Poster 42, JOBIM 2006.


• Theoretical properties of genomic distances.
  • The Gene Family-Free Median of Three. LNCS/LNBI 9838:102-120. WABI 2016.
  • The Gene Family-Free Median of Three. arXiv:1606.05910v1 [cs.DS]. 2016.
  • Breakpoint distance and PQ-trees. LNCS 6219:112-124, CPM 2010.
  • On maximal instances for the original syntenic distance. TCS 326(1-3):29-43. 2004.
  • On the properties of sequences of reversals that sort a signed permutation. JOBIM 2002, pp. 99-108. 2002.
    Enumerating optimal sequences of reversals: tools and experiments. Currents in Comput. Mol. Biol. pp. 20-21 (poster PA-112), RECOMB 2002.

Applied bioinformatics.

• Highly evolvable malaria vectors: The genomes of 16 Anopheles mosquitoes . Science 347(6217). 2014.


• Biochemical clustering of monomeric GTPases of the Ras superfamily. Mol. Cell. Proteomics 4:936-944. 2005.


• Identification, expression and evolutionary analyses of plant lipocalins. Plant Physiology 139(4):2017-2028. 2005.


• Detection of GPI-anchored protein sequences.
  • FragAnchor: GPI-Anchored Protein Prediction Tandem System (NN+HMM). Webserver. 2007
  • FragAnchor a large-scale all Eukaryota predictor of glycosylphosphatidylinositol-anchor in protein sequences by qualitative scoring. Genomics, Proteomics & Bioinformatics 5(2):121-130. 2007.
    Hybrid system NN/HMM for large-scale GPI-anchored protein prediction. Poster I-87, ISMB/ECCB 2004.
    Prediction of post translational GPI-anchor modification of protein by machine-learning. Abstract 71.7, MCP 2(9):826. 2003.

Discrete Mathematics, algorithms and computational complexity.

• Consecutive-Ones Property and variants, PQ-trees
  • Algorithms and complexity results for genome mapping problems. IEEE/ACM TCBB 14(2):418-430. 2017.
    Hypergraph covering problems motivated by genome assembly questions. arXiV:1306.4353v2 [cs.DS]. 2013.
    Hypergraph covering problems motivated by genome assembly questions. LNCS 8288:428-432, IWOCA 2013.
  • Linearization of ancestral multichromosomal genomes. BMC Bioinformatics 13(Suppl. 19):S11 (Proceedings of RECOMB-CG). 2012.
  • A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix. IPL 112:799-803. 2012.
    A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix. arXiv:1109.0562v1 [cs.DS]. 2011.
  • Tractability results for the Consecutive-Ones Property with multiplicity. LNCS 6661:90-103, CPM 2011.
  • Minimal Conflicting Sets for the Consecutive Ones Property in ancestral genome reconstruction. J. Comput. Biol. 17:1167-1181. 2010.
    Minimal Conflicting Sets for the Consecutive Ones Property in ancestral genome reconstruction. arXiv:0912.4196v1. 2009.
    Minimal Conflicting Sets for the Consecutive Ones Property in ancestral genome reconstruction. LNCS/LNBI 5817:48-58, RECOMB-CG 2009.
  • Hardness Results for the Gapped Consecutive-Ones Property. Discrete Applied Math 160(18):2760-2768. 2012.
    Hardness Results for the Gapped Consecutive-Ones Property. arXiv:cs.CC/0912.0309v1. 2009.
    On the Gapped Consecutive-Ones Property. ENDM 34:121-125, EUROCOMB 2009.

• Common intervals of permutations
  • On common intervals with errors. Report 2006-02, Technische Fakultat der Universitat Bielefeld. 2006.
  • Computing common intervals of K permutations with application to graph decomposition. SIAM J. Discrete Math. 22:1022-1039. 2008.
    Computing common intervals of K permutations with application to graph decomposition (extended abstract). LNCS 3669:779-790, ESA 2005.

• Trees and arc-annotated sequences edit distance
  See section "RNA secondary structure comparison" in Comparative bioinformatics above.

• Pattern matching
  • Chaining fragments in sequences: to sweep or not. arXiv:1506.07548. 2015.
  • Tree pattern matching with a more general notion of occurrence of the pattern. IPL 82(4):197-201. 2002.
  • Tree pattern matching for linear static terms. LNCS 2476:160-169, SPIRE 2002.

Enumerative and algebraic combinatorics.

• Combinatorial operators for Kronecker powers of representations of Sn. SLC 54:B54j. 2007.
  Combinatorial operators for Kronecker powers of representations of Sn. arXiv:math.RT/0503307. 2007.


• Maps and tree-like structures enumeration and generation.
  • An Exact Enumeration of Distance-Hereditary Graphs. arXiv:1608.01464 [math.CO]. 2016. To appear in the proceedings of ANALCO 2017.
  • Factorizations of signed permutations. Corrected version of the FPSAC 2003 paper below. 2003.
    Fatcorizations of signed permutations. FPSAC 2003, pp. 109-120. 2003.
  • A bijection between planar constellations and some colored Lagrangian trees. DMTCS 6(1):13-40. 2003.
    Another enumeration of constellations. FPSAC 2001, pp. 119-128. 2001.
  • Two bijective proof for the arborescent form of the Good-Lagrange formula and some applications to rooted trees and cacti. TCS 307(2):277-302. 2003. (Software GenCacti).
    A bijective proof of the arborescent form of the multivariable Lagrange inversion formula. Trends in Mathematics (Birkhauser, ISBN 3-7643-6430-0), pp. 89-100, Mathematics and Computer Science 2000.
    Enumération et génération aléatoire de cactus m-aires. Publications du LaCIM 27:81-91, Colloque LaCIM 2000.


• Enumeration of families of labelled trees
  • Enumerating alternating trees. JCTA 94(1):142-151. 2001.
  • Enumeration of some labelled trees. FPSAC 2000, pp. 146-157. 2000.
    Enumeration of some labelled trees. Research report RR-1226-99, LaBRI, 1999.
  • Une généralisation des résultats de Kreweras sur le polynôme énumérateur des inversions dans les arborescences. Research report RR-1241-00, LaBRI. 2000.
    Une généralisation des résultats de Kreweras sur le polynôme énumérateur des inversions dans les arborescences. ASMQ 24(2-3):23-38. 2000.
  
  
• The Robinson-Schensted correspondance for oscillating tableaux
  • A geometric version of the Robinson-Schensted Correspondence for skew oscillating tableaux. Discrete Math. 246(1-3):67-81. 2002.
  • Properties of the Robinson-Schensted Correspondence for oscillating and skew oscillating tableaux (extended abstract). FPSAC 1999, pp. 141-152, 1999.
    Properties of the Robinson-Schensted Correspondence for oscillating and skew oscillating tableaux. Research report RR-1211-99, LaBRI, 1999.
  • Une bijection entre tableaux gauches et tableaux oscillants gauches. Unpublished notes, 1997.
  
  
• Misc.
  • Generalized Motzkin numbers and skew tableaux. Unpublished notes. 2000.
  • Half of the nodes of Catalan trees are leaves. Unpublished notes, 1999.
  
  

Academic works (in french)

• À la recherche des génomes perdus : Modèles, Méthodologies et Algorithmes pour la Comparaison de Génomes. Habilitation à diriger des recherches. LaBRI, University Bordeaux I. 2011.


• Structure arborescentes : problèmes algorithmiques et combinatoires. Thèse de doctorat/Ph.D Thesis. LaBRI, University Bordeaux I. 2000.


• Quelques nouvelles propriétés des tableaux oscillants. Mémoire de DEA/Master thesis. LaBRI, University Bordeaux I. 1996.


• AMoRE.LaBRI. (Cedric Chauve, Gabriel de Dietrich, Danièle Sabatié). Software for languages and automaton, Undergraduate project. LaBRI, University Bordeaux I. 1995.