CSDAI Department

Institut Polytechnique de Paris

Group amibio

amibio (Algorithms and models for integrative biology)

LIX, Ecole Polytechnique

Themes: computer science in biology and health

Amibio (LIX, Ecole Polytechnique) is a research group in computational biology with a primary interest on the molecular levels of organization in the cell, and a strong focus on RNAs. Starting from the genomic sequences and NGS data, we currently concentrate our efforts on structures, interactions, evolution and design, trying to meet the growing needs for a rational synthetic biology. Towards that goal, we develop methodological approaches, based on abstract models that are computationally tractable and biologically relevant. A common toolkit of computational methods is developed, relying on our strong background in discrete mathematics, algorithmic design and analysis. Our ultimate goal is to provide software tools and platform elements, to formulate and test hypotheses for the sequence/structure/function relationship in molecular biology.

Contact person: Yann Ponty, https://www.lix.polytechnique.fr/~ponty

Web site: https://www.lix.polytechnique.fr/amibio/

Journal articles

2022

ref_biblio
Bertrand Marchand, Yann Ponty, Laurent Bulteau. Tree Diet: Reducing the Treewidth to Unlock FPT Algorithms in RNA Bioinformatics. Algorithms for Molecular Biology, BioMed Central, 2022. ⟨hal-03608412v2⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03608412/file/Treewidth_Reduction_AMB.pdf BibTex

2021

ref_biblio
Grégoire de Bisschop, Delphine Allouche, Elisa Frezza, Benoît Masquida, Yann Ponty, et al.. Progress Toward SHAPE Constrained Computational Prediction of Tertiary Interactions in RNA Structure. Non-Coding RNA, MDPI, 2021, 7 (4), pp.71. ⟨10.3390/ncrna7040071⟩. ⟨hal-03413594⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03413594/file/ncrna-1422092.pdf BibTex
ref_biblio
Gregor Entzian, Ivo Hofacker, Yann Ponty, Ronny Lorenz, Andrea Tanzer. RNAxplorer: Harnessing the Power of Guiding Potentials to Sample RNA Landscapes. Bioinformatics, Oxford University Press (OUP), 2021. ⟨hal-02889448v3⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02889448/file/RNAxplorer-preprint-2020.pdf BibTex
ref_biblio
Ha Nguyen, Haoliang Xue, Virginie Firlej, Yann Ponty, Mélina Gallopin, et al.. Reference-free transcriptome signatures for prostate cancer prognosis. BMC Cancer, BioMed Central, 2021, 21 (394), ⟨10.1186/s12885-021-08021-1⟩. ⟨hal-02948844⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02948844/file/39043604_File000004_951818349-1.pdf BibTex
ref_biblio
Dehe Wang, Ao Jiang, Jiangpeng Feng, Guangnan Li, Dong Guo, et al.. The SARS-CoV-2 Subgenome Landscape and its Novel Regulatory Features. Molecular Cell, Cell Press, In press, ⟨10.1016/j.molcel.2021.02.036⟩. ⟨hal-03154155v2⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03154155/file/main.pdf BibTex

2020

ref_biblio
Milad Miladi, Martin Raden, Sebastian Will, Rolf Backofen. Fast and accurate structure probability estimation for simultaneous alignment and folding of RNAs with Markov chains. Algorithms for Molecular Biology, BioMed Central, 2020, 15 (1), ⟨10.1186/s13015-020-00179-w⟩. ⟨hal-03131203⟩
Accès au bibtex
BibTex
ref_biblio
Teresa Müller, Milad Miladi, Frank Hutter, Ivo Hofacker, Sebastian Will, et al.. The locality dilemma of Sankoff-like RNA alignments. Bioinformatics, Oxford University Press (OUP), 2020, 36 (Supplement_1), pp.i242-i250. ⟨10.1093/bioinformatics/btaa431⟩. ⟨hal-02909014⟩
Accès au bibtex
BibTex
ref_biblio
Matan Drory Retwitzer, Vladimir Reinharz, Alexander Churkin, Yann Ponty, Jérôme Waldispühl, et al.. IncaRNAfbinv 2.0 - A webserver and software with motif control for fragment-based design of RNAs. Bioinformatics, Oxford University Press (OUP), 2020, 36 (9), pp.2910--2922. ⟨10.1093/bioinformatics/btaa039⟩. ⟨hal-02423237⟩
Accès au bibtex
BibTex
ref_biblio
Afaf Saaidi, Delphine Allouche, Mireille Regnier, Bruno Sargueil, Yann Ponty. IPANEMAP: Integrative Probing Analysis of Nucleic Acids Empowered by Multiple Accessibility Profiles. Nucleic Acids Research, Oxford University Press, 2020, 48 (15), pp.8276--8289. ⟨10.1093/nar/gkaa607⟩. ⟨hal-02889041v3⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02889041/file/IPANEMAP-BioRXvix-2020.pdf BibTex

2019

ref_biblio
Cedric Chauve, Yann Ponty, Michael Wallner. Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models. Journal of Mathematical Biology, Springer Verlag (Germany), 2019, 80 (5), pp.1353--1388. ⟨10.1007/s00285-019-01465-x⟩. ⟨hal-02169271⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02169271/file/Counting_DLT_Histories_notes.pdf BibTex
ref_biblio
Stefan Hammer, Wei Wang, Sebastian Will, Yann Ponty. Fixed-parameter tractable sampling for RNA design with multiple target structures. BMC Bioinformatics, BioMed Central, 2019, 20 (1), pp.209. ⟨10.1186/s12859-019-2784-7⟩. ⟨hal-02112888⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02112888/file/RNARedPrint.pdf BibTex
ref_biblio
Defne Surujon, Yann Ponty, Peter Clote. Small-world networks and RNA secondary structures. Journal of Computational Biology, Mary Ann Liebert, 2019, 26 (1), pp.16--26. ⟨10.1089/cmb.2018.0125⟩. ⟨hal-01424452v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01424452/file/main2018.pdf BibTex

2018

ref_biblio
Nika Abdollahi, Alexandre Albani, Eric Anthony, Agnes Baud, Mélissa Cardon, et al.. Meet-U: educating through research immersion. PLoS Computational Biology, Public Library of Science, 2018, 14 (3), pp.1-10. ⟨10.1371/journal.pcbi.1005992⟩. ⟨hal-01722019⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01722019/file/journal.pcbi.1005992.pdf BibTex
ref_biblio
Cedric Chauve, Julien Courtiel, Yann Ponty. Counting, generating, analyzing and sampling tree alignments. International Journal of Foundations of Computer Science, World Scientific Publishing, 2018, 29 (5), pp.741--767. ⟨hal-01500116⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01500116/file/main.pdf BibTex
ref_biblio
Alexander Churkin, Matan Drory Retwitzer, Vladimir Reinharz, Yann Ponty, Jérôme Waldispühl, et al.. Design of RNAs: comparing programs for inverse RNA folding.. Briefings in Bioinformatics, Oxford University Press (OUP), 2018, 19 (2), pp.350--358. ⟨10.1093/bib/bbw120⟩. ⟨hal-01392958⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01392958/file/Design_Software_Review_2016.pdf BibTex
ref_biblio
Hosna Jabbari, Ian Wark, Carlo Montemagno, Sebastian Will. Knotty: efficient and accurate prediction of complex RNA pseudoknot structures. Bioinformatics, Oxford University Press (OUP), 2018, 34 (22), pp.3849-3856. ⟨10.1093/bioinformatics/bty420⟩. ⟨hal-02908990⟩
Accès au bibtex
BibTex

2017

ref_biblio
Wandrille Duchemin, Yoann Anselmetti, Murray Patterson, Yann Ponty, Sèverine Bérard, et al.. DeCoSTAR: Reconstructing the ancestral organization of genes or genomes using reconciled phylogenies. Genome Biology and Evolution, Society for Molecular Biology and Evolution, 2017, 9 (5), pp.1312-1319. ⟨10.1093/gbe/evx069⟩. ⟨hal-01503766v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01503766/file/evx069.pdf BibTex
ref_biblio
Jozef Haleš, Alice Héliou, Ján Maňuch, Yann Ponty, Ladislav Stacho. Combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson-Crick and Nussinov-Jacobson Energy Models. Algorithmica, Springer Verlag, 2017, 79 (3), pp.835--856. ⟨10.1007/s00453-016-0196-x⟩. ⟨hal-01285499v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01285499/file/CombinatorialRNADesign-Hales-Manuch-Ponty-Stacho-Algorithmica-2015.pdf BibTex
ref_biblio
Benedikt Löwes, Cedric Chauve, Yann Ponty, Robert Giegerich. The BRaliBase dent - a tale of benchmark design and interpretation.. Briefings in Bioinformatics, Oxford University Press (OUP), 2017, 18 (2), pp.306--311. ⟨10.1093/bib/bbw022⟩. ⟨hal-01273406⟩
Accès au bibtex
BibTex

Conference papers

2021

ref_biblio
Laurent Bulteau, Bertrand Marchand, Yann Ponty. A new parametrization for independent set reconfiguration and applications to RNA kinetics. IPEC 2021 - 16th International Symposium on Parameterized and Exact Computation, Sep 2021, Lisbon, Portugal. ⟨hal-03272963v2⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03272963/file/article.pdf BibTex
ref_biblio
Sammy Khalife, Yann Ponty, Laurent Bulteau. Sequence graphs realizations and ambiguity in language models. COCOON 2021 - 27th International Computing and Combinatorics Conference, Oct 2021, Tainan, Taiwan. ⟨hal-02495333v3⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02495333/file/Sequence_graphs_ambiguity_language_models_HAL_v1.pdf BibTex
ref_biblio
Bertrand Marchand, Yann Ponty, Laurent Bulteau. Tree Diet: Reducing the Treewidth to Unlock FPT Algorithms in RNA Bioinformatics. WABI 2021 - 21st Workshop on Algorithms in Bioinformatics, 2021, Paris, France. ⟨hal-03206132⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03206132/file/main.pdf BibTex
ref_biblio
Hua-Ting Yao, Jérôme Waldispühl, Yann Ponty, Sebastian Will. Taming Disruptive Base Pairs to Reconcile Positive and Negative Structural Design of RNA. RECOMB 2021 - 25th international conference on research in computational molecular biology, Apr 2021, Padova, France. ⟨hal-02987566v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02987566/file/main.pdf BibTex

2020

ref_biblio
Alexander Churkin, Yann Ponty, Danny Barash. IndelsRNAmute: Predicting deleterious multiple point substitutions and indels mutations. ISBRA 2020 - 16th International Symposium on Bioinformatics Research and Applications, Dec 2020, Moscow, Russia. ⟨hal-02936276⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02936276/file/RNAMute_Evolved.pdf BibTex
ref_biblio
Roman Sarrazin-Gendron, Hua-Ting Yao, Vladimir Reinharz, Carlos Oliver, Yann Ponty, et al.. Stochastic Sampling of Structural Contexts Improves the Scalability and Accuracy of RNA 3D Modules Identification. RECOMB 2020 - 24th Annual International Conference on Research in Computational Molecular Biology, May 2020, Padova, Italy. ⟨hal-02354733⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02354733/file/BayesPairing2_recomb_submitted.pdf BibTex

2019

ref_biblio
Maher Mallem, Alain Denise, Yann Ponty. Forbidden substrings and the connectivity of the Hamming graph of RNA sequences: Partial disconnectivity tests. SEQBIM 2019 - Séquences en Bioinformatique, Informatique et Mathématiques, Dec 2019, Marne-la-Vallée, France. ⟨hal-02403517⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02403517/file/Design_Connectivity_Maher_2019%283%29.pdf BibTex
ref_biblio
Adrien Poulenard, Marie-Julie Rakotosaona, Yann Ponty, Maks Ovsjanikov. Effective Rotation-invariant Point CNN with Spherical Harmonics kernels. 3DV - International Conference on 3D Vision - 2019, Sep 2019, Québec City, Canada. ⟨hal-02167454v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02167454/file/Spherical_harmonic_cnn_Pro_version.pdf BibTex
ref_biblio
Maria Waldl, Sebastian Will, Peter F. Stadler, Michael T. Wolfinger, Ivo L. Hofacker. Bi-alignments as Models of Incongruent Evolution of RNA Sequence and Secondary Structure. CIBB 2019 - 16th International Conference on Computational Intelligence Methods for Bioinformatics and Biostatistics, Sep 2019, Bergamo, Italy. pp.159-170, ⟨10.1007/978-3-030-63061-4_15⟩. ⟨hal-03131248⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03131248/file/cibb_lnbi.pdf BibTex
ref_biblio
Hua-Ting Yao, Cedric Chauve, Mireille Regnier, Yann Ponty. Exponentially few RNA structures are designable. ACM-BCB 2019 - 10th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics, Sep 2019, Niagara-Falls, United States. pp.289-298, ⟨10.1145/3307339.3342163⟩. ⟨hal-02141853v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02141853/file/CountingDesigns.pdf BibTex

2018

ref_biblio
Stefan Hammer, Yann Ponty, Wei Wang, Sebastian Will. Fixed-Parameter Tractable Sampling for RNA Design with Multiple Target Structures. RECOMB - 22nd Annual International Conference on Research in Computational Molecular Biology - 2018, Apr 2018, Paris, France. ⟨hal-01631277v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01631277/file/RNARedPrint-Bioinfo2018.pdf BibTex
ref_biblio
Yann Ponty, Sebastian Will, Stefan Hammer. Nucleic Acids design targeting integer-valued features: FPT counting and uniform sampling. WEPA 2018 - 2nd International Workshop on Enumeration Problems and Applications, Nov 2018, Pisa, Italy. ⟨hal-01911878⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01911878/file/WEPA_2018.pdf BibTex

2017

ref_biblio
Juraj Michálik, Hélène Touzet, Yann Ponty. Efficient approximations of RNA kinetics landscape using non-redundant sampling. ISMB/ECCB - 25th Annual international conference on Intelligent Systems for Molecular Biology/16th European Conference on Computational Biology - 2017, Jul 2017, Prague, Czech Republic. pp.i283 - i292, ⟨10.1093/bioinformatics/btx269⟩. ⟨hal-01500115⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01500115/file/michalik-ISMB-2017.pdf BibTex
ref_biblio
Afaf Saaidi, Yann Ponty, Mathieu Blanchette, Mireille Regnier, Bruno Sargueil. An EM algorithm for mapping short reads in multiple RNA structure probing experiments. Matbio2017, King's College London Sep 2017, London, United Kingdom. ⟨hal-01590528⟩
Accès au bibtex
BibTex

2015

ref_biblio
Jozef Haleš, Ján Maňuch, Yann Ponty, Ladislav Stacho. Combinatorial RNA Design: Designability and Structure-Approximating Algorithm. CPM - 26th Annual Symposium on Combinatorial Pattern Matching, Jun 2015, Ischia Island, Italy. ⟨hal-01115349v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01115349/file/RNADesign-CPM2015-Final.pdf BibTex

Book sections

2022

ref_biblio
Yann Ponty, Vladimir Reinharz. RNA Folding. From text to graphs: Discrete structures and methods for Bioinformatics, ISTE, 2022. ⟨hal-03614168⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03614168/file/Book.pdf BibTex

2021

ref_biblio
Yann Ponty, Stefan Hammer, Hua-Ting Yao, Sebastian Will. Advanced design of structural RNAs using RNARedPrint. Ernesto Picardi. RNA Bioinformatics, 2284, pp.1--15, 2021, Methods in Molecular Biology, 978-1-0716-1306-1. ⟨10.1007/978-1-0716-1307-8_1⟩. ⟨hal-02990264⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02990264/file/RNARedPrint_Chapter_MiMB.pdf BibTex

2020

ref_biblio
Yann Ponty, Vladimir Reinharz. Repliement de l'ARN. Annie Chateau; Mikaël Salson. Du texte aux graphes : méthodes et structures discrètes pour la bioinformatique, A paraître. ⟨hal-02864246⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02864246/file/Chapitre_ISTE%283%29.pdf BibTex

2019

ref_biblio
Delphine Allouche, Grégoire de Bisschop, Afaf Saaidi, Yann Ponty, Sargueil Bruno. RNA secondary structure modelling following the IPANEMAP workflow. RNA Folding - Methods and Protocols, Springer Nature, In press, Methods in Molecular Biology. ⟨hal-02324783⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02324783/file/RNA_Probing_IPANEMAP12_07.pdf BibTex

Habilitation à diriger des recherches

2020

ref_biblio
Yann Ponty. Ensemble Algorithms and Analytic Combinatorics in RNA Bioinformatics and Beyond. Bioinformatics [q-bio.QM]. Université Paris-Saclay, 2020. ⟨tel-03219977v2⟩
Accès au texte intégral et bibtex
https://tel.archives-ouvertes.fr/tel-03219977/file/HDR-Ponty.pdf BibTex

Theses

2021

ref_biblio
Hua-Ting Yao. Local Decomposition in RNA Structural Design. Bioinformatics [q-bio.QM]. Ecole Polytechnique (Palaiseau, France); Université McGill [Montréal], 2021. English. ⟨NNT : 2021IPPAX126⟩. ⟨tel-03538576v2⟩
Accès au texte intégral et bibtex
https://tel.archives-ouvertes.fr/tel-03538576/file/phd_thesis_Yao_final.pdf BibTex

Preprints, Working Papers, ...

2022

ref_biblio
Bertrand Marchand, Sebastian Will, Sarah Berkemer, Laurent Bulteau, Yann Ponty. Automated design of dynamic programming schemes for RNA folding with pseudoknots. 2022. ⟨hal-03676377⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-03676377/file/auto_DP%283%29.pdf BibTex