DNA31*, Ens de Lyon, Aug 25-29, 2025 ==== Past Event ==== * Conférence en l'honneur d'Éric Rémila pour ses 60 ans, ÉNS de Lyon, France, May 28, 2019
(Co-organizer with Kevin Perrot) Founded by ANR, LIP and Codrin Nichitiu. * Workshop: Computing with molecular geometry, Villa Finaly, Florence, Italie, Nov. 20-23, 2017
(Co-organizer with Claire Lesieur and Damien Woods) Founded by IXXI, Tapdance and la mission pour l'interdisciplinarité du CNRS * 6èmes journées du GT CoA (Complexités et Algorithmes), LIP, Lyon, Nov. 27-28, 2017 * Research school on Molecular Programming: Theory & Wet Lab Nano-Scale Computation at ENS Lyon, Jan 16-20, 2017. Free to register and open to everyone ==== My current researches include ==== * DNA Computing: Algorithmic self-assembly, Molecular folding, Experiments * Algorithms: approximation, randomized, online, distributed,… * Complex systems: such as * Complex networks: clustering and drawing of dynamical networks * Stochastic cellular automata: definition, analysis, intrinsic simulations, local probabilistic correlations,… * Small world phenomenon: analysis, algorithms design, modelization,… * Random systems My work is supported by the “projet à risque” CalcADN (2025-2030), ANR Scalmazène (2022-2026), ANR NanoShapeLearn (2023-2027), the LIP Installation BQR (2017-18), MoPrExProgMol (2018) and AMARP (2018-20) by CNRS Mission pour l'interdisplinarité, and IXXI CalcASMol (2018-19) grants. ==== Internship proposal ==== 2024 Internship proposal: DNA computing: Theory, Models and wet lab experiments ==== Students ==== * Octave Hazard (M2, 2021; PhD advisor 2022-2025) * Nicolas Levy (M2, 2020; PhD advisor 2020-2023) * Pierre Marcus (M2, 2020; 4A, 2021; PhD Advisor 2022-2024) * Amaury Jacques (M1, 2021) * Daria Pchelina (M1, 2019) [ Report ] * Enka (Nikola) Blanchard (M2, 2015; PhD co-advisor with Ted Selker 2016-2019) Prix de thèse PSL SHS “Interface Sciences/Humanités” [ web | Remise du prix ] * Alberto Vera Azócar (U. Chile, several research internships 2013, 2015) * Damien Regnault (PhD co-advisor with Éric Thierry, 2005-2008) * Julien Robert (PhD advisor, 2006-2009) * Emmanuelle Lebhar (PhD co-advisor with Michel Morvan, 2003-2005) * Sandeep Dey (Master thesis advisor, 2005) ==== Teaching ==== * M2IF CR07 Molecular programming: Theory & wet-lab experiments [ past lectures ] * MPRI 2.11.1 Approximation Algorithms & Molecular Algorithms * 2022 Internship proposal: DNA computing: Theory, Models and wet lab experiments ==== Softwares ==== * ENSnano: a 3D DNA nanostructure design software for Windows, Mac OS and linux
codeveloped with Nicolas Levy, 2021 [ website | youtube channel ] * OS simulator: a fast and memory-efficient iPad app that simulates arbitrary Oritatami Systems (works with limitations on Apple silicon M1 too), 2021 [ website | download ] * CAOS simulator: an iOS app implementing our Oritatami cellular automata simulation, 2020
[ source code ] * Scary Pacman: an iOS app implementing our Oritatami scaling algorihms, 2018
[ source code ] * Clean scan: an iOS app to take printable pictures of white, green and black board, 2015 ==== Publications ==== * 2023 * Ok: A Kinetic Model for Locally Reconfigurable Molecular Systems
Pierre Marcus, Nicolas Schabanel and Shinnosuke Seki. In: Jonoska, N., Winfree, E. (eds) Visions of DNA Nanotechnology at 40 for the Next 40. Natural Computing Series. Springer, Singapore. * 2022 * Rule-of-thumb-free geometry-driven design of arbitrary complex curved DNA origami with ENSnano (Abstract)
Nicolas Levy, Allan Mills, Gaëtan Bellot*, Nicolas Schabanel*. DNA28, New Mexico, Aug. 2022.
* Turedo a new computational model for molecular nanobots?, Nicolas Schabanel.
Invited talk at the special session «Computing with bio-molecules» at CiE 2022, Swansea, Jul 2022. * Oritatami systems assemble shapes no less complex than tile assembly model (aTAM)
Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, Guillaume Theyssier. STACS, 26:1-23, 2022.
Supplementary material: [ Turedo2oritatami compiler | Full version ] * 2021 * ENSnano: a 3D modeling software for DNA nanostructures
Nicolas Levy, Nicolas Schabanel. In DNA27, LIPIcs, vol. 205, pp.5:1-23, doi:10.4230/LIPIcs.DNA.27.5, 2021.
best student paper & best presentation award.
Download ENSnano at: [ ENSnano website ] [ Youtube channel ] * 2020 * Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model [ Full version ]
Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, Yuki Ubukata. In LATIN, LNCS 12118:425-436, Sao Paulo, 2020. doi:10.1007/978-3-030-61792-9_34 hal-02410874
Download the iOS app CAOS simulator implementing our simulation [ source code ] * 2019 * Oritatami: A Computational Model for Molecular Co-Transcriptional Folding [ PDF & supplementary materials ]
Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. IJMS (Int. J. of Molecular Sciences), Special Issue Nucleic Acid Nanotechnology, 2019, 20(9), 2259.
https://doi.org/10.3390/ijms20092259 * 2018 * Proving the Turing Universality of Oritatami Co-Transcriptional Folding [ Supplementary materials ]
Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. ISAAC 2018, LIPIcs.ISAAC.2018.23:1-23:13, Jiaoxi, Yilan County, Taiwan, Dec. 2018. [ Arxiv ] * Know When to Fold ’Em: Self-Assembly of Shapes by Folding in Oritatami
Erik D. Demaine, Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Nicolas Schabanel, Shinnosuke Seki, and Hadley Thomas. DNA24, LNCS 11145:19-36, Jinan, China, Oct. 2018.
Invited talk at UCNC2018 Self-assembly, geometry and computation workshop, Fontainebleau, June 2018.
Download the iOS app Scary Pacman implementing our algorithms [ source code ] * 2017 * Dynamic Facility Location: Minimizing the Sum of Radii
Nicolas K. Blanchard, Nicolas Schabanel. WALCOM, LNCS 10167:30-41, march 2017. * 2016 * Oritatami systems: a computational model for co-transcriptional folding
Nicolas Schabanel. Invited plenary talk at Automata, Jun. 2016. * Programming biomolecules that fold greedily during transcription
Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. MFCS, LIPIcs 58, 43:1-43:14, Aug. 2016. * Folding Turing is hard but feasible
Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki.HALG, Jun. 2016. * 2015 * Efficient universal computation by molecular co-transcriptional folding (Short announcement)
Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki. DNA21, 1 page, 2015. * Facility Location in Evolving Metrics
with David Eisenstat and Claire Mathieu. ICALP, pages 459-470, 2014. * 2013 * Stochastic Cellular Automata: Correlations, Decidability and Simulations
with Pablo Arrighi and Guillaume Theyssier. Fundamenta Informaticæ, 126:121-156, 2013. * 2012 * Intrinsic simulations between stochastic cellular automata
with Pablo Arrighi and Guillaume Theyssier. AUTOMATA & JAC, EPTCS, 90:208–224, 2012. * Randomness + Determinism = Progresses: Why random processes could be favored by evolution
Progress in Biophysics and Molecular Biology (Special edition on the conference ”Chance at the heart of the cell”), 110(1):129–136, 2012. * 2011 * Les complexités : point de vue d’un institut des systèmes complexes (in French)
with Éric Bertin, Guillaume Beslon, Olivier Gandrillon, Sébastian Grauwin, and Pablo Jensen. Hermès, 60:145–150, 2011. * Optimal path search in small worlds: Dimension matters
with George Giakkoupis. STOC, 43:393–402, 2011. * Analyzing search algorithms in smallworlds
TERANET (colocated with DISC), 4 pages, Roma, Italy, Sep. 2011. * 2010 * Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability
with Kirk Pruhs and Julien Robert. WAOA, LNCS 6534:237–248, 2010. * Systèmes complexes & algorithmes (in French)
Habilitation à diriger des recherches, Université Paris Diderot, 2010. Slides * On the analysis of “simple” 2D stochastic cellular automata
with Damien Regnault and Éric Thierry. Invited publication to the special issue of DMTCS in honor of Philippe Flajolet, 12(2):263–294, 2009. * 2009 * Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority
with Damien Regnault and Éric Thierry. TCS, 410(47-49):4844-4855S, 2009. doi:10.1016/j.tcs.2009.06.024 * 2008 * Non-Clairvoyant Scheduling with Precedence Constraints
with Julien Robert. SODA, 491-500, Jan. 2008. * On the analysis of ”simple” 2D stochastic cellular automata
with Damien Regnault and Éric Thierry. LATA, LNCS 5196:452-463, Mar. 2008. * Time optimal self-assembling of 2D and 3D shapes: the case of squares and cubes
with Florent Becker and Éric Rémila. DNA14, LNCS 5347:144–155, June 2008. * Graph augmentation via metrics embedding
with Emmanuelle Lebhar. OPODIS, LNCS 5401:217-225, Dec. 2008. * 2007 * Non-clairvoyant batch sets scheduling: Fairness is fair enough
with Julien Robert. ESA, LNCS 4698:742-753, Oct. 2007. * Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority
with Damien Regnault and Éric Thierry. MFCS, LNCS 4708:320-332, Aug. 2007. * Small alliances in graphs
with Rodolfo Carvajal, Martín Matamala, and Iván Rapaport. MFCS, LNCS 4708:218-227, Aug. 2007. * Pull-Based Data Broadcast with Dependencies: Be Fair to Users, not to Items
with Julien Robert. SODA, p. 238-247, Jan. 2007. * 2006 * Customized Newspaper Problem: Data Broadcast with dependancies
with Sandeep Dey. LATIN, LNCS 3887:362-373, Valdivia, march 2006. * Asynchronous behavior of double-quiescent elementary cellular automata
with Nazim Fatès, Damien Regnault and Éric Thierry. LATIN, LNCS 3887:455-466, Valdivia, march 2006. * Could any graph be turn into a smallworld?
with Philippe Duchon, Nicolas Hanusse and Emmanuelle Lebhar. TCS, 355(1):96-103, 2006. * Towards small world emergence
with Philippe Duchon, Nicolas Hanusse and Emmanuelle Lebhar.SPAA, 225-232, july 2006. * Fully asynchronous behavior of double-quiescent elementary cellular automata
with Nazim Fatès, Michel Morvan, Éric Thierry.TCS, 362(1-3):1-16, 2006. * 2005 * Close to optimal decentralized routing in long-range contact networks
with Emmanuelle Lebhar. TCS, 348:294–310, 2005. * Could any graph be turn into a smallworld?
with Philippe Duchon, Nicolas Hanusse and, Emmanuelle Lebhar. DISC, LNCS 3724:512-513, Cracow, september 2005. * Fully asynchronous behavior of double-quiescent elementary cellular automata
with Nazim Fatès, Michel Morvan and Éric Thierry. MFCS, LNCS 3618:316-327, Gdansk, september 2005. * 2004 * Almost optimal decentralized routing in long-range contact networks
with Emmanuelle Lebhar. ICALP, Turku, Finland, july 2004. Full * An Internet Graph Model based on trade-off optimization
with José-Ignacio Alvarez-Hamelin. European Physical Journal B (EPJB), 38(2):231-238, 2004.
A preliminary version of the paper was presented at the Conference on Growing Networks and Graphs in Statistical Physics, Finance, Biology and Social Systems, Rome, 1-5 Sep. 2003. * 2003 * The data broadcast problem with non-uniform transmission times
with Claire Kenyon. Algorithmica, 35:146-175, February 2003.
A preliminary version of this paper was published in SODA 1999, pages 547-556. * 2000 * Algorithmes d'approximation pour les télécommunications sans fil : Ordonnancement pour la dissémination de données et Allocation statique de fréquences (in French) PDF
PhD Thesis, École normale supérieure de Lyon, 2000. Advisors: Claire Kenyon and Stéphane Ubéda (local advisor). * Polynomial-Time Approximation Scheme for Data Broadcast
with Claire Kenyon and Neal E. Young. STOC, pages 659-666, May 2000. * The databroadcast problem with preemption
STACS, LNCS 1770:181-192, Lille, February 2000. Full * 1999 * The data broadcast problem with non-uniform transmission times
with Claire Kenyon. SODA, pp.547–556. SIAM, Jan. 1999. * A randomized BSP algorithm for the maximal independent set problem
with Afonso Ferreira. In PPL, 9(3):411-422, 1999.
A preliminary version was published in I-SPAN'99, pages 284-289, june 1999. * 1998 and beyond * Parallel algorithm for the optimization of the span of an hexagonal frequency planning graph
with Stéphane Ubéda and Janez Žerovnik. Telepar, pages 237-241, Boston, Avril 1998. SCS. * Concurrent rebalancing of AVL trees: a fine-grained approach
with Luc Bougé, J. Gabarro, and X. Messeguer. Euro-Par, LNCS 1300:421-429, Août 1997. Full * Basic linear algebra operations in SLI arithmetic
with M. A. Anuta, D. W. Lozier, and Peter R. Turner. Euro-Par, LNCS 1124:193-202, Août 1996. ==== Popularization ==== * 2016 * Vérifier une preuve en n'en lisant que quelques lettres !
Nicolas Schabanel. Tangente, Hors série n°55:144-147 Les démonstrations, Jan. 2016 * Le «petit» théorème PCP
Nicolas Schabanel. Tangente, Hors série n°55:148-151 Les démonstrations, Jan. 2016 * Réduire la taille d'une preuve
Nicolas Schabanel. Tangente, Hors série n°55:152-155 Les démonstrations, Jan. 2016 * 2015 * La médiation en informatique vue par le CNRS
with Laure Guion. 1024 (Bulletin de la Société Informatique de France), Hors-série numéro 1 « Médiation scientifique : de la science informatique au grand public », p.19-21, février 2015. * Les hottes du Père Noël
1024 (Bulletin de la Société Informatique de France), Hors-série numéro 1 « Médiation scientifique : de la science informatique au grand public », p.79-82, février 2015. * 2013 * Couper, attendrir, trancher, réduire : un conte culinaire sur la résolution informatique des problèmes difficiles. (in French)
With Pierre Pansu. Mathématiques, l’explosion continue, pages 15-22, 2013. * 2007 * Routage dans les petits mondes PDF
with Emmanuelle Lebhar. )i( interstices INRIA popularization website, 2007. * 2003 * Thèse idiote: le hasard fabrique des certitudes** (in French)
Le minotaure (trimenstrial journal, 20 000ex), 1:66-69, april-june 2003.