Author: "Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE)"' showing total 330 results

Start Over Author "Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE)"

330 results on '"Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE)"'

1. Computational pan-genomics : Status, promises and challenges

Author: Lodewyk F. A. Wessels, Jan O. Korbel, Jasmijn A. Baaijens, Francesca Chiaromonte, Gunnar W. Klau, Kai Ye, Alexander Schönhuth, Francesca D. Ciccarelli, Tobias Marschall, Robin Cijvat, Matthias Schlesner, Adam M. Novak, Eleazar Eskin, Ashley D. Sanders, Sven Rahmann, Carl Shneider, Wigard P. Kloosterman, Knut Reinert, Eric-Wubbo Lameijer, Sandra Smit, Benedict Paten, Mohammed El-Kebir, Valentina Boeva, Evan E. Eichler, Cornelia M. van Duijn, Can Alkan, Jeroen de Ridder, Benjamin Langmead, Dick de Ridder, Jiayin Wang, David Porubsky, Fabio Vandin, Erwin Datema, Ben Raphael, Paul Kersey, Nadia Pisanti, Corinna Ernst, Klaasjan G. Ouwens, Y. Zhang, Thomas Abeel, Erik Garrison, Veli Mäkinen, Paul I.W. de Bakker, Victor Guryev, Siavash Sheikhizadeh, Manja Marz, Marcel Martin, Ole Schulz-Trieglaff, Pieter B. Neerincx, Rayan Chikhi, Eric Rivals, John C. Mu, Raoul J. P. Bonnal, Bas E. Dutilh, Paul Medvedev, Louis Dijkstra, Pierre Peterlongo, Ali Ghaffaari, Daniel Valenzuela, Epidemiology, Gastroenterology & Hepatology, Erasmus MC other, Alkan, Can, Saarland University [Saarbrücken], Max Planck Institute for Informatics [Saarbrücken], Karlsruhe Institute of Technology (KIT), Broad Institute of MIT and Harvard (BROAD INSTITUTE), Harvard Medical School [Boston] (HMS)-Massachusetts Institute of Technology (MIT)-Massachusetts General Hospital [Boston], Delft Bioinformatics Lab [Delft], Delft University of Technology (TU Delft), Computational Science Lab [Amsterdam], University of Amsterdam [Amsterdam] (UvA), Theoretical Biology & Bioinformatics [Utrecht], University Medical Center [Utrecht], Universidade Federal do Rio de Janeiro (UFRJ), European Bioinformatics Institute [Hinxton] (EMBL-EBI), EMBL Heidelberg, Section genetics [Utrecht], Center for Molecular medicine [Utrecht], University Medical Center [Utrecht]-University Medical Center [Utrecht], Helsinki Institute for Information Technology, Department of Computer Science [Helsinki], Falculty of Science [Helsinki], University of Helsinki-University of Helsinki, Howard Hughes Medical Institute [Santa Cruz] (HHMI), Center for Biomolecular Science & Engineering, European Research Institute for the Biology of Ageing [Groningen] (ERIBA), University Medical Center Groningen [Groningen] (UMCG), Institut de Biologie Computationnelle (IBC), Institut National de la Recherche Agronomique (INRA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Méthodes et Algorithmes pour la Bioinformatique (MAB), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Engineering (Bilkent-CS), Bilkent, Life Sciences [Amsterdam] (MAC4), Centrum Wiskunde & Informatica (CWI), Institut Cochin (IC UM3 (UMR 8104 / U1016)), Université Paris Descartes - Paris 5 (UPD5)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), PSL Research University (PSL), Centre de Bioinformatique (CBIO), MINES ParisTech - École nationale supérieure des mines de Paris-PSL Research University (PSL), Cancer et génôme: Bioinformatique, biostatistiques et épidémiologie d'un système complexe, MINES ParisTech - École nationale supérieure des mines de Paris-Institut Curie-Institut National de la Santé et de la Recherche Médicale (INSERM), Integrative Biology Program [Milano], Istituto Nazionale Genetica Molecolare [Milano] (INGM), Department of Statistics [Pennsylvania], Pennsylvania State University (Penn State), Penn State System-Penn State System, Bioinformatics and Sequence Analysis (BONSAI), Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 (CRIStAL), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Monet DB Solutions [Amsterdam], KeyGene [Wageningen], Department of Epidemiology [Rotterdam], Erasmus University Medical Center [Rotterdam] (Erasmus MC), Howard Hughes Medical Institute [Berkeley], University of California [Berkeley], University of California-University of California, Genome Informatics [Duisburg], Universität Duisburg-Essen [Essen], Departement of human genetics [Los Angeles], Computer Science Department [Los Angeles] (UCLA), University of California [Los Angeles] (UCLA), University of California-University of California-University of California [Los Angeles] (UCLA), The Wellcome Trust Sanger Institute [Cambridge], Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Universiteit Leiden [Leiden], Department of Computer Science [Baltimore], Johns Hopkins University (JHU), Centre de Physique des Particules de Marseille (CPPM), Centre National de la Recherche Scientifique (CNRS)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Aix Marseille Université (AMU), University of Pennsylvania [Philadelphia], China Agricultural University (CAU), University of Groningen [Groningen], Department of Biological Psychology [Amsterdam], Vrije Universiteit Amsterdam [Amsterdam] (VU), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Dipartimento di Informatica [Pisa] (DI), University of Pisa - Università di Pisa, Faculty of Computer Science [Dortmund], Technische Universität Dortmund [Dortmund] (TU), Service de Pneumologie A [Paris], AP-HP - Hôpital Bichat - Claude Bernard [Paris], Department of Mathematics and Computer Science (Freie Universität Berlin), Freie Universität Berlin, Wageningen University and Research Centre [Wageningen] (WUR), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), Division of Theoretical Bioinformatics [Heidelberg], German Cancer Research Center - Deutsches Krebsforschungszentrum [Heidelberg] (DKFZ), Illumina Cambridge, Illumina, Terry Fox Laboratory, BC Cancer Agency (BCCRC)-British Columbia Cancer Agency Research Centre, Bioinformatics Group [Wageningen], Leiden Observatory [Leiden], Regeneron Pharmaceuticals [Tarrytown], Shaanxi University of Science and Technology, Netherlands Cancer Institute (NKI), Antoni van Leeuwenhoek Hospital, Universita degli Studi di Padova, The Netherlands Organization for Scientific Research (NWO) Vidi (639.072.309 to A.S., 864.14.004 to B.E.D.), CAPES/BRASIL (to B.E.D.), the Academy of Finland (284598 [CoECGR] to V.M. and D.V.), the Russian Scientific Foundation (14–11–00826 to L.D.), Institut de Biologie Computationnelle (ANR-11-BINF- 0002 to E.R.), and the French Colib’read project (ANR–12– BS02–0008 to E.R.). NSFC 31671372 (to K. Y.), the Dutch Graduate School for Experimental Plant Sciences (054EPS15 to S.S.), the EMGO Institute for Health and Care Research (EMGO+) to K.O., the National Human Genome Research Institute (1U54HG007990 [BD2K] to B.P. and A.M.N., 5U41HG007234 [GENCODE] to B.P.), the W. M. Keck Foundation (DT06172015 to B.P. and A.M.N.), the Simons Foundation (SFLIFE# 351901 to B.P. and A.M.N.), the ARCS Foundation (2014–15 ARCS fellowship to A.M.N.), Edward Schulak (Edward Schulak Fellowship in Genomics to A.M.N.), ANR-11-BINF-0002,IBC,Institut de Biologie Computationnelle de Montpellier(2011), ANR-12-BS02-0008,Colib'read,Méthodes d'extraction d'information biologique dans les données HTS non assemblées(2012), Karlsruhe Institute of Technology ( KIT ), Broad Institute of MIT and Harvard ( BROAD INSTITUTE ), Harvard Medical School [Boston] ( HMS ) -Massachusetts General Hospital [Boston] ( MGH ) -Massachusetts Institute of Technology ( MIT ), Delft University of Technology ( TU Delft ), University of Amsterdam [Amsterdam] ( UvA ), Universidade Federal do Rio de Janeiro ( UFRJ ), European Bioinformatics Institute [Hinxton] ( EMBL-EBI ), European Molecular Biology Laboratory [Hinxton], Department of Computer Science, Howard Hughes Medical Institute [Santa Cruz] ( HHMI ), European Research Institute for the Biology of Ageing [Groningen] ( ERIBA ), University Medical Center Groningen [Groningen] ( UMCG ), Institut de Biologie Computationnelle ( IBC ), Centre de Coopération Internationale en Recherche Agronomique pour le Développement ( CIRAD ) -Institut National de la Recherche Agronomique ( INRA ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ), Méthodes et Algorithmes pour la Bioinformatique ( MAB ), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier ( LIRMM ), Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ), Department of Computer Engineering ( Bilkent-CS ), Life Sciences [Amsterdam] ( MAC4 ), Centrum Wiskunde & Informatica ( CWI ), Institut Cochin ( UM3 (UMR 8104 / U1016) ), Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Centre National de la Recherche Scientifique ( CNRS ), PSL Research University ( PSL ), Centre de Bioinformatique ( CBIO ), MINES ParisTech - École nationale supérieure des mines de Paris-PSL Research University ( PSL ), MINES ParisTech - École nationale supérieure des mines de Paris-Institut National de la Santé et de la Recherche Médicale ( INSERM ) -INSTITUT CURIE, Istituto Nazionale Genetica Molecolare [Milano] ( INGM ), PennState University [Pennsylvania] ( PSU ), Bioinformatics and Sequence Analysis ( BONSAI ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 ( CRIStAL ), Ecole Centrale de Lille-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut Mines-Télécom [Paris]-Université de Lille-Centre National de la Recherche Scientifique ( CNRS ) -Ecole Centrale de Lille-Institut Mines-Télécom [Paris]-Université de Lille-Centre National de la Recherche Scientifique ( CNRS ) -Centre National de la Recherche Scientifique ( CNRS ), Centre National de la Recherche Scientifique ( CNRS ), Erasmus University Medical Center [Rotterdam], Computer Science Department [Los Angeles] ( UCLA ), University of California at Los Angeles [Los Angeles] ( UCLA ) -University of California at Los Angeles [Los Angeles] ( UCLA ), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale ( ERABLE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Johns Hopkins University ( JHU ), Centre de Physique des Particules de Marseille ( CPPM ), Centre National de la Recherche Scientifique ( CNRS ) -Institut National de Physique Nucléaire et de Physique des Particules du CNRS ( IN2P3 ) -Aix Marseille Université ( AMU ), China Agricultural University ( CAU ), Vrije Universiteit Amsterdam [Amsterdam] ( VU ), Scalable, Optimized and Parallel Algorithms for Genomics ( GenScale ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -GESTION DES DONNÉES ET DE LA CONNAISSANCE ( IRISA_D7 ), Institut de Recherche en Informatique et Systèmes Aléatoires ( IRISA ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Institut National des Sciences Appliquées - Rennes ( INSA Rennes ) -Université de Bretagne Sud ( UBS ) -École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Institut National des Sciences Appliquées - Rennes ( INSA Rennes ) -Université de Bretagne Sud ( UBS ) -École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ) -Institut de Recherche en Informatique et Systèmes Aléatoires ( IRISA ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Institut National des Sciences Appliquées - Rennes ( INSA Rennes ) -Université de Bretagne Sud ( UBS ) -École normale supérieure - Rennes ( ENS Rennes ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ), Dipartimento di Informatica [Pisa] ( DI ), University of Pisa [Pisa], Technische Universität Dortmund [Dortmund] ( TU ), Department of Mathematics and Computer Science ( Freie Universität Berlin ), Freie Universität Berlin [Berlin], Wageningen University and Research Centre [Wageningen] ( WUR ), K.U.Leuven, German Cancer Research Center [Heidelberg] ( DKFZ ), Helmholtz-Gemeinschaft-Helmholtz-Gemeinschaft, BC Cancer Agency ( BCCRC ) -British Columbia Cancer Agency Research Centre, Netherlands Cancer Institute ( NKI ), ANR-11-BINF-0002,IBC,Institut de Biologie Computationnelle de Montpellier ( 2011 ), ANR-12-BS02-0008,Colib'read,Méthodes d'extraction d'information biologique dans les données HTS non assemblées ( 2012 ), Helsinki Institute for Information Technology (HIIT), Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University, Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Helsingin yliopisto = Helsingfors universitet = University of Helsinki, University of California [Santa Cruz] (UC Santa Cruz), University of California (UC), Bilkent University [Ankara], Université Paris sciences et lettres (PSL), Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Cancer et génome: Bioinformatique, biostatistiques et épidémiologie d'un système complexe, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut Curie [Paris]-Institut National de la Santé et de la Recherche Médicale (INSERM), Department of Statistics [PennState], Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), University of Washington [Seattle], Howard Hughes Medical Institute (HHMI), Universität Duisburg-Essen = University of Duisburg-Essen [Essen], University of California (UC)-University of California (UC)-University of California [Los Angeles] (UCLA), University of California (UC)-University of California (UC), Universiteit Leiden, Aix Marseille Université (AMU)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), University of Pennsylvania, Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP), Department of Mathematics and Computer Science, Wageningen University and Research [Wageningen] (WUR), Università degli Studi di Padova = University of Padua (Unipd), ANR-11-BINF-0002,IBC,Institut de biologie Computationnelle(2011), Aalto University-University of Helsinki, University of California [Santa Cruz] (UCSC), University of California, Université de Montpellier (UM)-Institut National de la Recherche Agronomique (INRA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Centre National de la Recherche Scientifique (CNRS)-Université Paris Descartes - Paris 5 (UPD5)-Institut National de la Santé et de la Recherche Médicale (INSERM), MINES ParisTech - École nationale supérieure des mines de Paris, Centre National de la Recherche Scientifique (CNRS)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), and Groningen Research Institute for Asthma and COPD (GRIAC)
Subjects: 0301 basic medicine, Data structures, Computer science, Medizin, 02 engineering and technology, computer.software_genre, Genome, Computational and Statistical Genetics, data structures, haplotypes, pan-genome, read mapping, sequence graph, Tumours of the digestive tract Radboud Institute for Molecular Life Sciences [Radboudumc 14], 0303 health sciences, education.field_of_study, Point (typography), Genomics, Papers, Data mining, Sequence graph, Computational problem, Construct (philosophy), Algorithms, Human, Information Systems, Bioinformatics, 0206 medical engineering, Population, Pan-genome, 03 medical and health sciences, [ INFO.INFO-BI ] Computer Science [cs]/Bioinformatics [q-bio.QM], Bioinformatica, Humans, Haplotypes, Read mapping, Computational Biology, Genome, Human, Software, Molecular Biology, education, Representation (mathematics), 030304 developmental biology, Computational genomics, Data structure, Data science, Human genetics, 030104 developmental biology, Paradigm shift, ddc:004, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], EPS, computer, 020602 bioinformatics
Abstract: Many disciplines, from human genetics and oncology to plant breeding, microbiology and virology, commonly face the challenge of analyzing rapidly increasing numbers of genomes. In case ofHomo sapiens, the number of sequenced genomes will approach hundreds of thousands in the next few years. Simply scaling up established bioinformatics pipelines will not be sufficient for leveraging the full potential of such rich genomic datasets. Instead, novel, qualitatively different computational methods and paradigms are needed. We will witness the rapid extension ofcomputational pan-genomics, a new sub-area of research in computational biology. In this paper, we generalize existing definitions and understand apan-genomeas any collection of genomic sequences to be analyzed jointly or to be used as a reference. We examine already available approaches to construct and use pan-genomes, discuss the potential benefits of future technologies and methodologies, and review open challenges from the vantage point of the above-mentioned biological disciplines. As a prominent example for a computational paradigm shift, we particularly highlight the transition from the representation of reference genomes as strings to representations as graphs. We outline how this and other challenges from different application domains translate into common computational problems, point out relevant bioinformatics techniques and identify open problems in computer science. With this review, we aim to increase awareness that a joint approach to computational pan-genomics can help address many of the problems currently faced in various domains.
Published: 2018
Full Text: View/download PDF

2. Insights on the virulence of swine respiratory tract mycoplasmas through genome-scale metabolic modeling

Author: Franciele Maboni Siqueira, Florence Tardy, Mariana Galvão Ferrarini, Ana Tereza Ribeiro de Vasconcelos, Marie-France Sagot, Arnaldo Zaha, Bénédicte Elena-Herrmann, Elodie Jobard, Tony Lionel Palama, Scheila G. Mucha, Irene Silveira Schrank, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centro de Biotecnologia [Porto Alegre] (CBiot), Universidade Federal do Rio Grande do Sul [Porto Alegre] (UFRGS), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Ingénierie des Systèmes Biologiques et des Procédés (LISBP), Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de la Recherche Agronomique (INRA), Centre Léon Bérard [Lyon], NMR Methods for Metabolism - Methodes RMN en métabolomique, Institut des Sciences Analytiques (ISA), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Laboratorio Nacional de Computação Cientifica [Rio de Janeiro] (LNCC / MCT), Mycoplasmoses des Ruminants - UMR (MYCO), Université de Lyon-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS), VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS), Baobab, Département PEGASE [LBBE] (PEGASE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale ( ERABLE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Centro de Biotecnologia [Porto Alegre] ( CBiot ), Universidade Federal do Rio Grande do Sul [Porto Alegre] ( UFRGS ), Laboratoire de Biométrie et Biologie Evolutive ( LBBE ), Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire d'Ingénierie des Systèmes Biologiques et des Procédés ( LISBP ), Institut National de la Recherche Agronomique ( INRA ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Centre National de la Recherche Scientifique ( CNRS ), Institut des Sciences Analytiques ( ISA ), École normale supérieure - Lyon ( ENS Lyon ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique ( CNRS ) -École normale supérieure - Lyon ( ENS Lyon ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique ( CNRS ), Laboratorio Nacional de Computação Cientifica [Rio de Janeiro] ( LNCC / MCT ), Mycoplasmoses des ruminants [Lyon], Université de Lyon-VetAgro Sup ( VAS ), VetAgro Sup ( VAS ), Institut National de la Recherche Agronomique (INRA)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), ISA NMR Methods for Metabolism - Methodes RMN en métabolomique (2014-2018), Institut de Chimie du CNRS (INC)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0301 basic medicine, Magnetic Resonance Spectroscopy, Swine, Whole-genome metabolic reconstruction, Mycoplasma hyorhinis, [SDV]Life Sciences [q-bio], 030106 microbiology, Mollicutes, Virulence, Biology, medicine.disease_cause, Models, Biological, Microbiology, 03 medical and health sciences, Mycoplasma, Mycoplasma hyopneumoniae, Genetics, medicine, Animals, Metabolomics, Biomass, Microbial Viability, [ SDV ] Life Sciences [q-bio], Computational Biology, Metabolic network, Genomics, Pneumonia of Swine, Mycoplasmal, biology.organism_classification, medicine.disease, Hydrogen peroxide, Virology, Bacterial Load, Gene Ontology, medicine.anatomical_structure, Metabolism, Enzootic, Energy Metabolism, Pneumonia (non-human), Genome, Bacterial, Metabolic Networks and Pathways, Research Article, Biotechnology, Respiratory tract
Abstract: Background The respiratory tract of swine is colonized by several bacteria among which are three Mycoplasma species: Mycoplasma flocculare, Mycoplasma hyopneumoniae and Mycoplasma hyorhinis. While colonization by M. flocculare is virtually asymptomatic, M. hyopneumoniae is the causative agent of enzootic pneumonia and M. hyorhinis is present in cases of pneumonia, polyserositis and arthritis. The genomic resemblance among these three Mycoplasma species combined with their different levels of pathogenicity is an indication that they have unknown mechanisms of virulence and differential expression, as for most mycoplasmas. Methods In this work, we performed whole-genome metabolic network reconstructions for these three mycoplasmas. Cultivation tests and metabolomic experiments through nuclear magnetic resonance spectroscopy (NMR) were also performed to acquire experimental data and further refine the models reconstructed in silico. Results Even though the refined models have similar metabolic capabilities, interesting differences include a wider range of carbohydrate uptake in M. hyorhinis, which in turn may also explain why this species is a widely contaminant in cell cultures. In addition, the myo-inositol catabolism is exclusive to M. hyopneumoniae and may be an important trait for virulence. However, the most important difference seems to be related to glycerol conversion to dihydroxyacetone-phosphate, which produces toxic hydrogen peroxide. This activity, missing only in M. flocculare, may be directly involved in cytotoxicity, as already described for two lung pathogenic mycoplasmas, namely Mycoplasma pneumoniae in human and Mycoplasma mycoides subsp. mycoides in ruminants. Metabolomic data suggest that even though these mycoplasmas are extremely similar in terms of genome and metabolism, distinct products and reaction rates may be the result of differential expression throughout the species. Conclusions We were able to infer from the reconstructed networks that the lack of pathogenicity of M. flocculare if compared to the highly pathogenic M. hyopneumoniae may be related to its incapacity to produce cytotoxic hydrogen peroxide. Moreover, the ability of M. hyorhinis to grow in diverse sites and even in different hosts may be a reflection of its enhanced and wider carbohydrate uptake. Altogether, the metabolic differences highlighted in silico and in vitro provide important insights to the different levels of pathogenicity observed in each of the studied species. Electronic supplementary material The online version of this article (doi:10.1186/s12864-016-2644-z) contains supplementary material, which is available to authorized users.
Published: 2016
Full Text: View/download PDF

3. Metabolic Investigation of the Mycoplasmas from the Swine Respiratory Tract

Author: Ferrarini , Mariana G, Siqueira , Franciele Maboni, Mucha , Scheila G, Palama , Tony, Jobard , Elodie, Elena-Herrmann , Bénédicte, Vasconcelos , Ana Tereza Ribeiro, Tardy , Florence, Schrank , Irene S, Zaha , A, Sagot , Marie-France, Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Centro de Biotecnologia [Porto Alegre] (CBiot), Universidade Federal do Rio Grande do Sul [Porto Alegre] (UFRGS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ISA NMR Methods for Metabolism - Methodes RMN en métabolomique (2014-2018), Institut des Sciences Analytiques (ISA), Institut de Chimie du CNRS (INC)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre Léon Bérard [Lyon], Laboratorio Nacional de Computação Cientifica [Rio de Janeiro] (LNCC / MCT), VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS), Mycoplasmoses des Ruminants - UMR (MYCO), Université de Lyon-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS), Laboratoire de Biométrie et Biologie Evolutive ( LBBE ), Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ), Centro de Biotecnologia [Porto Alegre] ( CBiot ), Universidade Federal do Rio Grande do Sul [Porto Alegre] ( UFRGS ), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale ( ERABLE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), NMR Methods for Metabolism - Methodes RMN en métabolomique, Institut des Sciences Analytiques ( ISA ), École normale supérieure - Lyon ( ENS Lyon ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique ( CNRS ) -École normale supérieure - Lyon ( ENS Lyon ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique ( CNRS ), Laboratorio Nacional de Computação Cientifica [Rio de Janeiro] ( LNCC / MCT ), VetAgro Sup ( VAS ), Mycoplasmoses des ruminants [Lyon], Université de Lyon-VetAgro Sup ( VAS ), Université de Lyon-Université de Lyon-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)
Subjects: MESH: Mycoplasma, Mollicutes, Metabolic network, Metabolism, Whole-genome metabolic reconstruction, Hydrogen peroxide, [SDV.BBM.BM]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular biology, [ SDV.BBM.BM ] Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular biology, [ SDV.BIBS ] Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], MESH : Mycoplasma
Abstract: International audience; BackgroundThe respiratory tract of swine is colonized by several bacteria among which are three Mycoplasma species: Mycoplasma flocculare, Mycoplasma hyopneumoniae and Mycoplasma hyorhinis. While colonization by M. flocculare is virtually asymptomatic, M. hyopneumoniae is the causative agent of enzootic pneumonia and M. hyorhinis is present in cases of pneumonia, polyserositis and arthritis. The genomic resemblance among these three Mycoplasma species combined with their different levels of pathogenicity is an indication that they have unknown mechanisms of virulence and differential expression, as for most mycoplasmas.MethodsIn this work, we performed whole-genome metabolic network reconstructions for these three mycoplasmas. Cultivation tests and metabolomic experiments through nuclear magnetic resonance spectroscopy (NMR) were also performed to acquire experimental data and further refine the models reconstructed in silico.ResultsEven though the refined models have similar metabolic capabilities, interesting differences include a wider range of carbohydrate uptake in M. hyorhinis, which in turn may also explain why this species is a widely contaminant in cell cultures. In addition, the myo-inositol catabolism is exclusive to M. hyopneumoniae and may be an important trait for virulence. However, the most important difference seems to be related to glycerol conversion to dihydroxyacetone-phosphate, which produces toxic hydrogen peroxide. This activity, missing only in M. flocculare, may be directly involved in cytotoxicity, as already described for two lung pathogenic mycoplasmas, namely Mycoplasma pneumoniae in human and Mycoplasma mycoides subsp. mycoides in ruminants. Metabolomic data suggest that even though these mycoplasmas are extremely similar in terms of genome and metabolism, distinct products and reaction rates may be the result of differential expression throughout the species.ConclusionsWe were able to infer from the reconstructed networks that the lack of pathogenicity of M. flocculare if compared to the highly pathogenic M. hyopneumoniae may be related to its incapacity to produce cytotoxic hydrogen peroxide. Moreover, the ability of M. hyorhinis to grow in diverse sites and even in different hosts may be a reflection of its enhanced and wider carbohydrate uptake. Altogether, the metabolic differences highlighted in silico and in vitro provide important insights to the different levels of pathogenicity observed in each of the studied species.
Published: 2016
Full Text: View/download PDF

4. High-Throughput Sequencing of Transposable Element Insertions Suggests Adaptive Evolution of the Invasive Asian Tiger Mosquito Towards Temperate Environments

Author: Cristina Vieira, Claire Valiente Moro, Hélène Henri, Clément Goubert, Guillaume Minard, Matthieu Boulesteix, Patrick Mavingui, Eléments transposables, évolution, populations, Département génétique, interactions et évolution des génomes [LBBE] (GINSENG), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Ecologie Microbienne - UMR 5557 (LEM), Institut National de la Recherche Agronomique (INRA)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Ecole Nationale Vétérinaire de Lyon (ENVL), Processus Infectieux en Milieu Insulaire Tropical (PIMIT), Centre National de la Recherche Scientifique (CNRS)-IRD-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de La Réunion (UR), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), French Ministry of Superior Education, Centre National de la Recherche Scientifique, Institut Universitaire de France, Federation de Recherche 41 'Bio-Environnement et Sante', Université de Lyon-Université de Lyon-Ecole Nationale Vétérinaire de Lyon (ENVL)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Université de La Réunion (UR)-Institut National de la Santé et de la Recherche Médicale (INSERM)-IRD-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Ecole Nationale Vétérinaire de Lyon (ENVL)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Recherche Agronomique (INRA)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS), Laboratoire de Biométrie et Biologie Evolutive ( LBBE ), Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ), Ecologie microbienne ( EM ), Centre National de la Recherche Scientifique ( CNRS ) -Ecole Nationale Vétérinaire de Lyon ( ENVL ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de la Recherche Agronomique ( INRA ) -VetAgro Sup ( VAS ), Processus Infectieux en Milieu Insulaire Tropical ( PIMIT ), Centre National de la Recherche Scientifique ( CNRS ) -IRD-Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Université de la Réunion ( UR ), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale ( ERABLE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Institut Universitaire de France ( IUF ), and Ministère de l'Éducation nationale, de l’Enseignement supérieur et de la Recherche ( M.E.N.E.S.R. )
Subjects: 0301 basic medicine, 0106 biological sciences, Aedes albopictus, Genotype, Climate, [SDV]Life Sciences [q-bio], aedes albopictus, genome scan, Diapause, medicine.disease_cause, 010603 evolutionary biology, 01 natural sciences, Invasive species, DNA sequencing, invasive species, Evolution, Molecular, 03 medical and health sciences, Aedes, Genetics, medicine, Animals, Chikungunya, Genotyping, Ecology, Evolution, Behavior and Systematics, 030304 developmental biology, Local adaptation, 0303 health sciences, Natural selection, [ SDV ] Life Sciences [q-bio], biology, Ecology, High-Throughput Nucleotide Sequencing, biology.organism_classification, Adaptation, Physiological, Insect Vectors, Europe, 030104 developmental biology, Genetics, Population, Vietnam, Evolutionary biology, Vector (epidemiology), DNA Transposable Elements, transposable elements, local adaptation
Abstract: Invasive species represent unique opportunities to evaluate the role of local adaptation during colonization of new environments. Among these species, the Asian tiger mosquito,Aedes albopictus, is a threatening vector of several human viral diseases, including dengue and chikungunya, and raises concerns about the Zika fever. Its broad presence in both temperate and tropical environments has been considered the reflection of great “ecological plasticity”. However, no study has been conducted to assess the role of adaptive evolution in the ecological success ofAe. albopictusat the molecular level. In the present study, we performed a genomic scan to search for potential signatures of selection leading to local adaptation in one-hundred-forty field-collected mosquitoes from native populations of Vietnam and temperate invasive populations of Europe. High-throughput genotyping of transposable element insertions led to the discovery of more than 120 000 polymorphic loci, which, in their great majority, revealed a virtual absence of structure between the bio-geographic areas. Nevertheless, 92 outlier loci showed a high level of differentiation between temperate and tropical populations. The majority of these loci segregates at high insertion frequencies among European populations, indicating that this pattern could have been caused by recent adaptive evolution events in temperate areas. An analysis of the overlapping and neighboring genes highlighted several candidates, including diapause, lipid and juvenile hormone pathways.
Published: 2016
Full Text: View/download PDF

5. Approximation algorithms for replenishment problems with fixed turnover times

Author: Yang Jiao, R. Ravi, Thomas Bosman, Martijn van Ee, Leen Stougie, Alberto Marchetti-Spaccamela, Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands, Vrije Universiteit Amsterdam [Amsterdam] (VU), Tepper School of Business, Carnegie Mellon University [Pittsburgh] (CMU), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centrum Wiskunde & Informatica (CWI), University of Amsterdam [Amsterdam] (UvA), Netherlands Defence Academy, Boeing Research and Technology Europe, Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), The research of YJ and RR was supported in part by the U. S. National Science Foundation under award numbers CCF-1527032 and CCF-1655442, and the U. S. Office of Naval Research under award number N00014-18-1-2099. The research of LS was supported by the Netherlands Organisation for Scientific Research (NWO) through the Gravitation Programme Networks (024.002.003), Bender, Michael A., Farach-Colton, Martin, Mosteiro, Miguel A., Econometrics and Operations Research, Tinbergen Institute, Amsterdam Business Research Institute, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], and Operations Analytics
Subjects: FOS: Computer and information sciences, Schedule, Mathematical optimization, Optimization problem, Computational complexity theory, General Computer Science, Computer science, 0211 other engineering and technologies, Time horizon, G.2.2, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Traveling salesman, Computer Science - Data Structures and Algorithms, Inventory routing, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Approximation algorithms, F.2.2, 021103 operations research, Applied Mathematics, Approximation algorithm, SDG 8 - Decent Work and Economic Growth, Pinwheel scheduling, Computer Science Applications, Periodic maintenance, 010201 computation theory & mathematics, Replenishment problem, Node (circuits), Routing (electronic design automation), Constant (mathematics)
Abstract: We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min–avg minimizes the average tour cost and min–max minimizes the maximum tour cost over all days. For min–max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min–avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.
Published: 2022
Full Text: View/download PDF

6. A whole-genome sequence and transcriptome perspective on HER2-positive breast cancers

Author: Marta Gut, Iris Pauporté, Cécile Mannina, Sancha Martin, Michael R. Stratton, Frédérique Penault-Llorca, Vincent Le Texier, Laurent Arnould, Pierre Saintigny, Marie-Christine Mathieu, P. Fumoleau, Xavier Pivot, Jean-François Deleuze, Hélène Blanché, Anthony Ferrari, Janice Kielbassa, Eskeatnaf Mulugeta, Olivier Tredan, Sandrine Boyault, Anne Vincent-Salomon, Thomas Bachelot, Emilie Thomas, Jean-Yves Pierga, Odette Mariani, Suzette Delaloge, Ivo Gut, Hervé Bonnefoi, Fabien Calvo, Frédéric Bibeau, Alain Viari, Serena Nik-Zainal, Anne-Sophie Sertier, Gilles Romieu, Maria Rios, Gaëtan MacGrogan, Jocelyne Jacquemier, Laurie Tonon, Gilles Thomas, Jean-Marc Ferrero, Isabelle Treilleux, Daniel Birnbaum, Catherine Bouteille, Carole Tarpin, Centre Léon Bérard [Lyon], Génétique et Biologie du Développement, Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut Curie [Paris]-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Interactions hôte-greffon-tumeur, ingénierie cellulaire et génique - UFC (UMR INSERM 1098) (RIGHT), Institut National de la Santé et de la Recherche Médicale (INSERM)-Etablissement français du sang [Bourgogne-Franche-Comté] (EFS BFC)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC), Validation et identification de nouvelles cibles en oncologie (VINCO), Institut Bergonié [Bordeaux], UNICANCER-UNICANCER-Université Bordeaux Segalen - Bordeaux 2-Institut National de la Santé et de la Recherche Médicale (INSERM), Lipides - Nutrition - Cancer (U866) (LNC), Université de Bourgogne (UB)-Institut National de la Santé et de la Recherche Médicale (INSERM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Ecole Nationale Supérieure de Biologie Appliquée à la Nutrition et à l'Alimentation de Dijon (ENSBANA), Département de Biologie et pathologie des tumeurs [Centre Georges-François Leclerc], Centre Régional de Lutte contre le cancer Georges-François Leclerc [Dijon] (UNICANCER/CRLCC-CGFL), UNICANCER-UNICANCER, Centre d'Etude du Polymorphisme Humain (CEPH), Université Paris Diderot - Paris 7 (UPD7)-Institut Universitaire d'Hématologie (IUH), Université Paris Diderot - Paris 7 (UPD7)-Fondation Jean Dausset, Institut Paoli-Calmettes, Fédération nationale des Centres de lutte contre le Cancer (FNCLCC), Institut Gustave Roussy (IGR), Equipe de recherche sur les traitements individualisés des cancers (ERTICa), Université d'Auvergne - Clermont-Ferrand I (UdA), Institut de Recherche en Cancérologie de Montpellier (IRCM - U1194 Inserm - UM), CRLCC Val d'Aurelle - Paul Lamarque-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM), Centre de Ressources Biologiques [Paris], Institut Curie [Paris], Département de pathologie, Physico-Chimie-Curie (PCC), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut Curie [Paris]-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS), Université Paris Descartes - Paris 5 (UPD5), Department of Medical Oncology [Lyon], UNICANCER - Institut régional du Cancer Montpellier Val d'Aurelle (ICM), CRLCC Val d'Aurelle - Paul Lamarque, UNICANCER, Pathologie mammaire, Département de médecine oncologique [Gustave Roussy], Institut Gustave Roussy (IGR)-Institut Gustave Roussy (IGR), Institut de Cancérologie de Lorraine - Alexis Vautrin [Nancy] (UNICANCER/ICL), Pôle de Chirurgie Oncologique générale, Gynécologique et Mammaire [Centre Antoine-Lacassagne], Centre de Lutte contre le Cancer Antoine Lacassagne [Nice] (UNICANCER/CAL), UNICANCER-Université Côte d'Azur (UCA)-UNICANCER-Université Côte d'Azur (UCA), Centre de Recherche en Cancérologie de Marseille (CRCM), Aix Marseille Université (AMU)-Institut Paoli-Calmettes, Fédération nationale des Centres de lutte contre le Cancer (FNCLCC)-Fédération nationale des Centres de lutte contre le Cancer (FNCLCC)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Chirurgie gynécologique, mammaire et réparatrice [Saint-Etienne], Clinique Mutualiste Chirurgicale [Saint-Étienne], Direction de la recherche [Gustave Roussy], Centre for Genomic Regulation [Barcelona] (CRG), Universitat Pompeu Fabra [Barcelona] (UPF)-Centro Nacional de Analisis Genomico [Barcelona] (CNAG), The Wellcome Trust Sanger Institute [Cambridge], Institut National du Cancer [Boulogne Billancourt] (INC), Centre de Recherche en Cancérologie de Lyon (UNICANCER/CRCL), Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Institut National de la Santé et de la Recherche Médicale ( INSERM ) -INSTITUT CURIE-Centre National de la Recherche Scientifique ( CNRS ), Interactions hôte-greffon-tumeur, ingénierie cellulaire et génique - UFC (UMR INSERM 1098) ( HOTE GREFFON ), Université de Franche-Comté ( UFC ) -Etablissement français du sang [Bourgogne-France-Comté] ( EFS [Bourgogne-France-Comté] ) -Institut National de la Santé et de la Recherche Médicale ( INSERM ), Validation et identification de nouvelles cibles en oncologie ( VINCO ), Université Bordeaux Segalen - Bordeaux 2-Institut Bergonié - CRLCC Bordeaux-Institut National de la Santé et de la Recherche Médicale ( INSERM ), Lipides - Nutrition - Cancer (U866) ( LNC ), Université de Bourgogne ( UB ) -Institut National de la Santé et de la Recherche Médicale ( INSERM ) -AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Ecole Nationale Supérieure de Biologie Appliquée à la Nutrition et à l'Alimentation de Dijon ( ENSBANA ), Centre Régional de Lutte contre le cancer - Centre Georges-François Leclerc ( CRLCC - CGFL ), Centre d'Etude du Polymorphisme Humain ( CEPH ), Université Paris Diderot - Paris 7 ( UPD7 ) -Institut Universitaire d'Hématologie ( IUH ), Université Paris Diderot - Paris 7 ( UPD7 ) -Fondation Jean Dausset, Institut Gustave Roussy ( IGR ), Equipe de recherche sur les traitements individualisés des cancers ( ERTICa ), Université d'Auvergne - Clermont-Ferrand I ( UdA ), UNICANCER - Institut régional du Cancer [Montpellier] ( ICM ), Institut Curie, Institut Bergonié - CRLCC Bordeaux, Physico-Chimie-Curie ( PCC ), Centre National de la Recherche Scientifique ( CNRS ) -INSTITUT CURIE-Université Pierre et Marie Curie - Paris 6 ( UPMC ), Université Paris Descartes - Paris 5 ( UPD5 ), Institut Gustave Roussy ( IGR ) -Institut Gustave Roussy ( IGR ), Institut de Cancérologie de Lorraine - Alexis Vautrin ( ICL ), CRLCC Antoine Lacassagne, Centre de Recherche en Cancérologie de Marseille ( CRCM ), Centre National de la Recherche Scientifique ( CNRS ) -Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Institut Paoli-Calmettes, Fédération nationale des Centres de lutte contre le Cancer (FNCLCC)-Fédération nationale des Centres de lutte contre le Cancer (FNCLCC)-Aix Marseille Université ( AMU ), Centre for Genomic Regulation [Barcelona] ( CRG ), Universitat Pompeu Fabra [Barcelona]-Centro Nacional de Analisis Genomico [Barcelona] ( CNAG ), Institut National du Cancer [Boulogne Billancourt] ( INC ), Centre de Recherche en Cancérologie de Lyon ( CRCL ), Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Centre National de la Recherche Scientifique ( CNRS ), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale ( ERABLE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Nik-Zainal Abidin, Serena [0000-0001-5054-1727], Apollo - University of Cambridge Repository, Institut National de la Santé et de la Recherche Médicale (INSERM)-Etablissement français du sang [Bourgogne-Franche-Comté] (EFS [Bourgogne-Franche-Comté])-Université de Franche-Comté (UFC), Sagot, Marie-France, Centre National de la Recherche Scientifique (CNRS)-Institut Curie [Paris]-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Pierre et Marie Curie - Paris 6 (UPMC), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Etablissement français du sang [Bourgogne-Franche-Comté] (EFS [Bourgogne-Franche-Comté]), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Bourgogne (UB)-Ecole Nationale Supérieure de Biologie Appliquée à la Nutrition et à l'Alimentation de Dijon (ENSBANA)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement, Centre National de la Recherche Scientifique (CNRS)-Institut Curie [Paris]-Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut de Chimie du CNRS (INC), Centre National de la Recherche Scientifique (CNRS)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut Paoli-Calmettes, Fédération nationale des Centres de lutte contre le Cancer (FNCLCC)-Fédération nationale des Centres de lutte contre le Cancer (FNCLCC)-Aix Marseille Université (AMU), Interactions hôte-greffon-tumeur, ingénierie cellulaire et génique - UFC ( HOTE GREFFON ), Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Etablissement français du sang [Bourgogne-France-Comté] ( EFS [Bourgogne-France-Comté] ) -Université de Franche-Comté ( UFC ), Institut Paoli Calmettes, Université Pierre et Marie Curie - Paris 6 ( UPMC ) -INSTITUT CURIE-Centre National de la Recherche Scientifique ( CNRS ), Centre National de la Recherche Scientifique ( CNRS ) -Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Institut Paoli-Calmettes-Aix Marseille Université ( AMU ), Université Claude Bernard Lyon 1 ( UCBL ), and Université de Lyon-Université de Lyon-Centre Léon Bérard [Lyon]-Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Centre National de la Recherche Scientifique ( CNRS )
Subjects: 0301 basic medicine, DNA Copy Number Variations, Receptor, ErbB-2, Science, [SDV]Life Sciences [q-bio], General Physics and Astronomy, Breast Neoplasms, Biology, Genome, Polymorphism, Single Nucleotide, General Biochemistry, Genetics and Molecular Biology, Article, 03 medical and health sciences, 0302 clinical medicine, Breast cancer, Germline mutation, Gene duplication, medicine, Humans, Copy-number variation, skin and connective tissue diseases, Genetics, Multidisciplinary, Whole Genome Sequencing, [ SDV ] Life Sciences [q-bio], Gene Expression Profiling, Estrogen Receptor alpha, Gene Amplification, General Chemistry, Amplicon, medicine.disease, 3. Good health, Gene expression profiling, [SDV] Life Sciences [q-bio], 030104 developmental biology, 030220 oncology & carcinogenesis, Mutation, Human genome, Female, Receptors, Progesterone, Transcriptome
Abstract: HER2-positive breast cancer has long proven to be a clinically distinct class of breast cancers for which several targeted therapies are now available. However, resistance to the treatment associated with specific gene expressions or mutations has been observed, revealing the underlying diversity of these cancers. Therefore, understanding the full extent of the HER2-positive disease heterogeneity still remains challenging. Here we carry out an in-depth genomic characterization of 64 HER2-positive breast tumour genomes that exhibit four subgroups, based on the expression data, with distinctive genomic features in terms of somatic mutations, copy-number changes or structural variations. The results suggest that, despite being clinically defined by a specific gene amplification, HER2-positive tumours melt into the whole luminal–basal breast cancer spectrum rather than standing apart. The results also lead to a refined ERBB2 amplicon of 106 kb and show that several cases of amplifications are compatible with a breakage–fusion–bridge mechanism., Breast cancer is separated into multiple subtypes based on the expression of HER2 and hormone receptors. Here, the authors report the whole genome sequence of 64 HER2 positive tumours and show that these can be further separated into four groups with different gene expression profiles and genomic features.
Published: 2016
Full Text: View/download PDF

7. Landscape of somatic mutations in 560 breast cancer whole-genome sequences

Author: John W.M. Martens, Sandrine Boyault, David Jones, Stefania Tommasi, Jeong-Yeon Lee, Germán Fg Rodríguez-González, Inigo Martincorena, Sung-Min Ahn, Alastair M Thompson, Manasa Ramakrishna, Gilles Thomas, Helen Davies, Savitri Krishnamurthy, Stian Knappskog, Steven Van Laere, Lucy Stebbings, Andrea L. Richardson, Andrew Tutt, Anne Lise Børresen-Dale, Olafur Oa Stefansson, Sunil R. Lakhani, Michiel M. Smid, Gerrit Gk Hooijer, Young Seok Ju, Tari Ta King, Rebecca Shepherd, Luc Dirix, Xavier Pivot, Adam Butler, Aquila Fatima, Peter Pt Simpson, Serena Nik-Zainal, Sancha Martin, Hyung-Yong Kim, Hendrik G. Stunnenberg, Jos Jonkers, Michael R. Stratton, Jon W. Teague, Se Jin Jang, Sandro Morganella, Ville Mustonen, Moritz Gerstung, Gu Kong, Carlos Caldas, Anne Vincent-Salomon, Anieta M. Sieuwerts, Lucy R. Yates, Sarah O’Meara, Peter B. Vermeulen, Dominik Glodzik, Peter Van Loo, Naoto T. Ueno, Arie B. Brinkman, Stuart McLaren, Yang Li, Marc J. van de Vijver, Laura Van't Veer, P. Andrew Futreal, Markus Ringnér, Christos Sotiriou, Ewan Birney, Kamna Ramakrishnan, Miriam Ragle Aure, Johan Staaf, Jane E. Brock, Benita Kiat Tee Bk Tan, Alain Viari, Xueqing Zou, Anita Langerød, David C. Wedge, Hee Jin Lee, Christine Desmedt, Gilles Romieu, Paul N. Span, Jorunn E. Eyfjord, Annegien Broeks, Isabelle Treilleux, Åke Borg, Colin Ca Purdie, Ole Christian Lingjærde, Gert Van den Eynden, John A. Foekens, Serge Dronov, Andrew Menzies, Peter J. Campbell, Iris Pauporté, Ludmil B. Alexandrov, Keiran Raine, The Wellcome Trust Sanger Institute [Cambridge], Lund University [Lund], Erasmus University Medical Center [Rotterdam] (Erasmus MC), Radboud university [Nijmegen], Oslo University Hospital Radiumhospitalet, University of Oslo (UiO), Gachon University Hospital, Génomique Fonctionnelle des Tumeurs Solides (U1162), Université Paris 13 (UP13)-Université Paris Diderot - Paris 7 (UPD7)-Université Paris Descartes - Paris 5 (UPD5)-Institut National de la Santé et de la Recherche Médicale (INSERM), Brigham and Women's Hospital [Boston], Netherlands Cancer Institute (NKI), Antoni van Leeuwenhoek Hospital, Breast Cancer Translational Research Laboratory, Institut Jules Bordet [Bruxelles], Faculté de Médecine [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB)-Faculté de Médecine [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Algemeen Ziekenhuis St Augustinus Oncology, Dana-Farber Cancer Institute [Boston], Academic Medical Center - Academisch Medisch Centrum [Amsterdam] (AMC), University of Amsterdam [Amsterdam] (UvA), University of Ulsan, NASA Johnson Space Center (JSC), NASA, University of Stuttgart, Esso UK Ltd, Department of Exploration, Esso UK Ltd, Department of Computer Science & Engineering [Riverside] (CSE), University of California [Riverside] (UCR), University of California-University of California, Department of Geriatric Medicine [Singapore] (Alexandra Hospital), Institut national du cancer [Boulogne] (INCA), Centre Hospitalier Régional Universitaire de Besançon (CHRU Besançon), Department of Pathology [Dundee], Ninewells Hospital and Medical School [Dundee], Canary Institute for Cancer Research (ICIC), Department of Biochemistry and Physiology, Faculty of Health Sciences, University of Las Palmas de Gran Canaria (ULPGC), Institut de Recherche en Cancérologie de Montpellier (IRCM - U1194 Inserm - UM), CRLCC Val d'Aurelle - Paul Lamarque-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM), Department of Medical Oncology [Rotterdam], Cancer Genomics Centre, University of Queensland [Brisbane], University of Iceland [Reykjavik], Beckman Research Institute [Duarte, CA], Centre de Recherche en Cancérologie de Lyon (UNICANCER/CRCL), Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National de la Santé et de la Recherche Médicale (INSERM), University of Antwerp (UA), European Central Bank (ECB), European Central Bank, Unité de génétique et biologie des cancers (U830), Université Paris Descartes - Paris 5 (UPD5)-Institut Curie [Paris]-Institut National de la Santé et de la Recherche Médicale (INSERM), Department of Tumor Biology, Institut Curie [Paris], University of Cambridge [UK] (CAM), Division of Diagnostic Oncology, Netherlands Cancer Institute, Agendia BV, Breakthrough Breast Cancer Centre, London Institute of Cancer, University of Bergen (UiB), National Cancer Centre Singapore (NCCS), National Cancer Centre Singapore, Division of Molecular Biology, National Institutes of Natural Sciences, The Graduate University for Advanced Studies, Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Radiation Oncology 874, Radboud University Medical Center [Nijmegen], Department of Laboratory Medicine, Department Medical Oncology, Department of Pathology, Ospedale 'Mater Salutis', Goddard Earth Sciences and Technology and Research (GESTAR), NASA-Universities Space Research Association (USRA), Department of Molecular Biology [Nijmegen], Department of Organismic and Evolutionary Biology [Cambridge] (OEB), Harvard University [Cambridge], Department of Computing [London], Biomedical Image Analysis Group [London] (BioMedIA), Imperial College London-Imperial College London, Synergie Lyon Cancer [Lyon], Centre Léon Bérard [Lyon], Sagot, Marie-France, Radboud University [Nijmegen], University of California [Riverside] (UC Riverside), University of California (UC)-University of California (UC), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Nik-Zainal, Serena [0000-0001-5054-1727], Zou, Xueqing [0000-0003-1143-1028], Caldas, Carlos [0000-0003-3547-1489], Apollo - University of Cambridge Repository, Medical Oncology, Harvard University, Fondation Synergie Lyon Cancer [Lyon], CCA -Cancer Center Amsterdam, Pathology, Erasmus University Medical Center [Rotterdam], University of Oslo ( UiO ), Genomique Fonctionnelle des Tumeurs Solides, Université Paris Diderot - Paris 7 ( UPD7 ) -IFR105-Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National de la Santé et de la Recherche Médicale ( INSERM ), Netherlands Cancer Institute ( NKI ), Institut Jules Bordet, Academic Medical Center [Amsterdam] ( AMC ), University of Amsterdam [Amsterdam] ( UvA ), NASA Johnson Space Center ( JSC ), Department of Computer Science & Engineering [Riverside] ( CSE ), University of California [Riverside] ( UCR ), Institut national du cancer [Boulogne] ( INCA ), Hôpital Jean Minjoz, Centre Hospitalier Régional Universitaire [Besançon] ( CHRU Besançon ), Department of Medical Oncology, Erasmus Medical Center Rotterdam, Josephine Nefkens Institute and Cancer Genomics Centre, University of Las Palmas de Gran Canaria ( ULPGC ), Institut de Recherche en Cancérologie de Montpellier ( IRCM - U1194 Inserm - UM ), CRLCC Val d'Aurelle - Paul Lamarque-Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Université de Montpellier ( UM ), Erasmus MC, Beckman Research Institute, Centre de Recherche en Cancérologie de Lyon ( CRCL ), Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Centre National de la Recherche Scientifique ( CNRS ), University of Antwerp ( UA ), European Central Bank ( ECB ), U 830, Institut National de la Santé et de la Recherche Médicale, Institut Curie, University of Cambridge [UK] ( CAM ), University of Bergen ( UIB ), National Cancer Centre Singapore ( NCCS ), Laboratoire de Biométrie et Biologie Evolutive ( LBBE ), Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale ( ERABLE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Goddard Earth Sciences and Technology and Research ( GESTAR ), NASA-Universities Space Research Association ( USRA ), Department of Organismic and Evolutionary Biology ( OEB ), and Biomedical Image Analysis Group [London] ( BioMedIA )
Subjects: 0301 basic medicine, DNA Replication, Male, Mutation rate, DNA repair, [SDV]Life Sciences [q-bio], DNA Mutational Analysis, Genes, BRCA2, Genes, BRCA1, Breast Neoplasms, Biology, medicine.disease_cause, Genome, Cohort Studies, 03 medical and health sciences, Germline mutation, SDG 3 - Good Health and Well-being, Mutation Rate, medicine, Humans, Gene, Molecular Biology, Genetics, Mutation, Multidisciplinary, [ SDV ] Life Sciences [q-bio], Genome, Human, Recombinational DNA Repair, DNA, Neoplasm, Genomics, Oncogenes, Women's cancers Radboud Institute for Health Sciences [Radboudumc 17], 3. Good health, [SDV] Life Sciences [q-bio], 030104 developmental biology, Mutagenesis, Human genome, Female, Engineering sciences. Technology
Abstract: Item does not contain fulltext We analysed whole-genome sequences of 560 breast cancers to advance understanding of the driver mutations conferring clonal advantage and the mutational processes generating somatic mutations. We found that 93 protein-coding cancer genes carried probable driver mutations. Some non-coding regions exhibited high mutation frequencies, but most have distinctive structural features probably causing elevated mutation rates and do not contain driver mutations. Mutational signature analysis was extended to genome rearrangements and revealed twelve base substitution and six rearrangement signatures. Three rearrangement signatures, characterized by tandem duplications or deletions, appear associated with defective homologous-recombination-based DNA repair: one with deficient BRCA1 function, another with deficient BRCA1 or BRCA2 function, the cause of the third is unknown. This analysis of all classes of somatic mutation across exons, introns and intergenic regions highlights the repertoire of cancer genes and mutational processes operating, and progresses towards a comprehensive account of the somatic genetic basis of breast cancer.
Published: 2016
Full Text: View/download PDF

8. An average study of hypergraphs and their minimal transversals

Author: François Rioult, Arnaud Mary, Julien David, Loïck Lhote, Laboratoire d'Informatique de Paris-Nord ( LIPN ), Université Paris 13 ( UP13 ) -Université Sorbonne Paris Cité ( USPC ) -Institut Galilée-Centre National de la Recherche Scientifique ( CNRS ), Computer mediated exchange of structured knowledge ( EXMO ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Laboratoire d'Informatique de Grenoble ( LIG ), Université Pierre Mendès France - Grenoble 2 ( UPMF ) -Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut National Polytechnique de Grenoble ( INPG ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ) -Université Pierre Mendès France - Grenoble 2 ( UPMF ) -Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut National Polytechnique de Grenoble ( INPG ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ), Equipe AMACC - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen ( GREYC ), Université de Caen Normandie ( UNICAEN ), Normandie Université ( NU ) -Normandie Université ( NU ) -Ecole Nationale Supérieure d'Ingénieurs de Caen ( ENSICAEN ), Normandie Université ( NU ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Caen Normandie ( UNICAEN ), Normandie Université ( NU ) -Centre National de la Recherche Scientifique ( CNRS ), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale ( ERABLE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Laboratoire de Biométrie et Biologie Evolutive ( LBBE ), Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ), Equipe CODAG - Laboratoire GREYC - UMR6072, Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Computer mediated exchange of structured knowledge (EXMO), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), and Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Discrete mathematics, Hypergraph, Polynomial, [ INFO ] Computer Science [cs], General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Probabilistic logic, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Upper and lower bounds, Theoretical Computer Science, Exponential function, Combinatorics, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Enumeration, Order (group theory), Probabilistic analysis of algorithms, [INFO]Computer Science [cs], [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; In this paper, we study some average properties of hypergraphs and the average com-plexity of algorithms applied to hypergraphs under different probabilistic models. Our approach is both theoretical and experimental since our goal is to obtain a random model that is able to capture the real-data complexity. Starting from a model that generalizes the Erdös-Renyi model [9, 10], we obtain asymptotic estimations on the average number of transversals, minimals and minimal transversals in a random hy-pergraph. We use those results to obtain an upper bound on the average complexity of algorithms to generate the minimal transversals of an hypergraph. Then we make our random model more complex in order bring it closer to real-data and identify cases where the average number of minimal tranversals is at most polynomial, quasi-polynomial or exponential.
Published: 2015
Full Text: View/download PDF

9. Incremental complexity of a bi-objective hypergraph transversal problem

Author: Marie-France Sagot, Thomas Picchetti, Ricardo Andrade, Etienne Birmelé, Arnaud Mary, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS), Baobab, Département PEGASE [LBBE] (PEGASE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Service d'Epidémiologie et de santé publique, AP-HP Hôpital Bicêtre (Le Kremlin-Bicêtre), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale ( ERABLE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Laboratoire de Biométrie et Biologie Evolutive ( LBBE ), Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ), Mathématiques Appliquées à Paris 5 ( MAP5 - UMR 8145 ), and Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National des Sciences Mathématiques et de leurs Interactions-Centre National de la Recherche Scientifique ( CNRS )
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Hypergraph, Generalization, Dimension (graph theory), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], hypergraph, 0102 computer and information sciences, Computational Complexity (cs.CC), 01 natural sciences, Combinatorics, 03 medical and health sciences, Transversal (geometry), transversal, Computer Science::Discrete Mathematics, [ INFO.INFO-BI ] Computer Science [cs]/Bioinformatics [q-bio.QM], TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Enumeration, [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 030304 developmental biology, Mathematics, Discrete mathematics, Polynomial (hyperelastic model), 0303 health sciences, Mathematics::Combinatorics, Degree (graph theory), Computer Science - Computational Complexity, [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC], 010201 computation theory & mathematics, Bounded function, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], complexity, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: The hypergraph transversal problem has been intensively studied, both from a theoretical and a practical point of view. In particular, its incremental complexity is known to be quasi-polynomial in general and polynomial for bounded hypergraphs. Recent applications in computational biology however require to solve a generalization of this problem, that we call bi-objective transversal problem. The instance is in this case composed of a pair of hypergraphs $(\mathcal {A},\mathcal {B})$, and the aim is to enumerate minimal sets which hit all the hyperedges of $\mathcal {A}$ while intersecting a minimal set of hyperedges of $\mathcal {B}$. In this paper, we formalize this problem and relate it to the enumeration of minimal hitting sets of bundles. We show cases when under degree or dimension contraints these problems remain NP-hard, and give a polynomial algorithm for the case when $\mathcal {A}$ has bounded dimension, by building a hypergraph whose transversals are exactly the hitting sets of bundles.
Published: 2015
Full Text: View/download PDF

10. ELASTIC-DEGENERATE STRING MATCHING VIA FAST MATRIX MULTIPLICATION

Author: Giulia Bernardini, Paweł Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone, Dipartimento di Informatica Sistemistica e Comunicazione (DISCo), Università degli Studi di Milano-Bicocca = University of Milano-Bicocca (UNIMIB), University of Wrocław [Poland] (UWr), Dipartimento di Informatica [Pisa] (DI), University of Pisa - Università di Pisa, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Centrum Wiskunde & Informatica (CWI), Sagot, Marie-France, Bioinformatics, AIMMS, Bio Informatics (IBIVU), Bernardini, G., Gawrychowski, P., Pisanti, N., Pissis, S. P., and Rosone, G.
Subjects: FOS: Computer and information sciences, General Computer Science, pattern matching, string algorithms, elastic-degenerate string, matrix multiplication, fast Fourier transform, General Mathematics, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], string algorithm
Abstract: An elastic-degenerate (ED) string is a sequence of $n$ sets of strings of total length $N$, which was recently proposed to model a set of similar sequences. The ED string matching (EDSM) problem is to find all occurrences of a pattern of length $m$ in an ED text. An $O(nm^{1.5}\sqrt{\log m}+N)$-time algorithm for EDSM is known [Aoyama et al., CPM 2018]. The standard assumption in the prior work on this question is that $N$ is substantially larger than both $n$ and $m$, and thus we would like to have a linear dependency on the former. Under this assumption, the natural open problem is whether we can decrease the 1.5 exponent in the time complexity, similarly as in the related (but, to the best of our knowledge, not equivalent) word break problem [Backurs and Indyk, FOCS 2016]. Our starting point is a conditional lower bound for EDSM. We use the popular combinatorial Boolean Matrix Multiplication (BMM) conjecture stating that there is no truly subcubic combinatorial algorithm for BMM [Abboud and Williams, FOCS 2014]. By designing an appropriate reduction we show that a combinatorial algorithm solving the EDSM problem in $O(nm^{1.5-e}+N)$ time, for any $e>0$, refutes this conjecture. Our reduction should be understood as an indication that decreasing the exponent requires fast matrix multiplication. String periodicity and fast Fourier transform are two standard tools in string algorithms. Our main technical contribution is that we successfully combine these tools with fast matrix multiplication to design a non-combinatorial $\tilde{O}(nm^{\omega-1}+N)$-time algorithm for EDSM, where $\omega$ denotes the matrix multiplication exponent. To the best of our knowledge, we are the first to combine these tools. In particular, using the fact that $\omega, Comment: Extended version of paper in ICALP 2019
Published: 2022
Full Text: View/download PDF

11. A General Framework for Enumerating Equivalence Classes of Solutions

Author: Yishu Wang, Arnaud Mary, Marie-France Sagot, Blerina Sinaimeri, Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS), Mutzel, Petra and Pagh, Rasmus and Herman, and Grzegorz
Subjects: FOS: Computer and information sciences, J.3, General Computer Science, F.2, Applied Mathematics, Enumeration algorithm, Enumeration algorithms, Equivalence relation, Dynamic programming, Dynamic programming, Computer Science Applications, Mathematics of computing → Graph enumeration, 68W40, 68Q25, 68R99, Equivalence relation, Computer Science - Data Structures and Algorithms, Dynamic programming, Enumeration algorithms, Equivalence relation, Theory of computation → Dynamic programming, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Enumeration algorithms, Theory of computation → Backtracking
Abstract: When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of contexts, including optimization ones that can be addressed by dynamic programming algorithms, and for certain types of equivalence relations between solutions., 36 pages, 8 figures
Published: 2023
Full Text: View/download PDF

12. De novo assembly and annotation of the Asian tiger mosquito (Aedes albopictus) repeatome with dnaPipeTE from raw genomic reads and comparative analysis with the yellow fever mosquito (Aedes aegypti)

Author: Goubert, Clément, Modolo, Laurent, Vieira, Cristina, ValienteMoro, Claire, Mavingui, Patrick, Boulesteix, Matthieu, Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Université de Lyon, Ecologie Mircobienne, Institut National de la Recherche Agronomique (INRA), Université de La Réunion (UR), Agence Nationale de la Recherche (ANR Genemobile), Centre National de La Recherche Scientifique, Institut Universitaire de France, Federation de Recherche 41 'Bio-Environnement et Sante', French Ministry of Superior Education, A. albopictus genome sequencing project - Agence Nationale de la Recherche (ANR Immunsymbart), Eléments transposables, évolution, populations, Département génétique, interactions et évolution des génomes [LBBE] (GINSENG), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Statistique en grande dimension pour la génomique, Département PEGASE [LBBE] (PEGASE), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Ecologie Microbienne - UMR 5557 (LEM), Institut National de la Recherche Agronomique (INRA)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Ecole Nationale Vétérinaire de Lyon (ENVL), Processus Infectieux en Milieu Insulaire Tropical (PIMIT), Centre National de la Recherche Scientifique (CNRS)-IRD-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de La Réunion (UR), Université de Lyon-Université de Lyon-Ecole Nationale Vétérinaire de Lyon (ENVL)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Université de La Réunion (UR)-Institut National de la Santé et de la Recherche Médicale (INSERM)-IRD-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Ecole Nationale Vétérinaire de Lyon (ENVL)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Recherche Agronomique (INRA)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS), Sagot, Marie-France, Laboratoire de Biométrie et Biologie Evolutive ( LBBE ), Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale ( ERABLE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Ecologie microbienne ( EM ), Centre National de la Recherche Scientifique ( CNRS ) -Ecole Nationale Vétérinaire de Lyon ( ENVL ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de la Recherche Agronomique ( INRA ) -VetAgro Sup ( VAS ), Processus Infectieux en Milieu Insulaire Tropical ( PIMIT ), and Université de la Réunion ( UR ) -Institut National de la Santé et de la Recherche Médicale ( INSERM ) -IRD-Centre National de la Recherche Scientifique ( CNRS )
Subjects: bioinformatic pipeline, [ SDV ] Life Sciences [q-bio], repeated DNA, Trinity, [SDV]Life Sciences [q-bio], Genome, Insect, TE analysis, Molecular Sequence Annotation, DNA, Genomics, Aedes albopictus, [SDV] Life Sciences [q-bio], Aedes, DNA Transposable Elements, Animals, transposable elements, Software, Research Article, Repetitive Sequences, Nucleic Acid
Abstract: International audience; Repetitive DNA, including transposable elements (TEs), is found throughout eukaryotic genomes. Annotating and assembling the "repeatome" during genome-wide analysis often poses a challenge. To address this problem, we present dnaPipeTE-a new bioinformatics pipeline that uses a sample of raw genomic reads. It produces precise estimates of repeated DNA content and TE consensus sequences, as well as the relative ages of TE families. We shows that dnaPipeTE performs well using very low coverage sequencing in different genomes, losing accuracy only with old TE families. We applied this pipeline to the genome of the Asian tiger mosquito Aedes albopictus, an invasive species of human health interest, for which the genome size is estimated to be over 1 Gbp. Using dnaPipeTE, we showed that this species harbors a large (50% of the genome) and potentially active repeatome with an overall TE class and order composition similar to that of Aedes aegypti, the yellow fever mosquito. However, intraorder dynamics show clear distinctions between the two species, with differences at the TE family level. Our pipeline's ability to manage the repeatome annotation problem will make it helpful for new or ongoing assembly projects, and our results will benefit future genomic studies of A. albopictus.
Published: 2015
Full Text: View/download PDF

13. Approximate Circular Pattern Matching

Author: Charalampopoulos, Panagiotis, Rotenberg, Eva, Herman, Grzegorz, Kociumaka, Tomasz, Radoszewski, Jakub, Pissis, Solon P., Rytter, Wojciech, Waleń, Tomasz, Zuba, Wiktor, Chechik, Shiri, Navarro, Gonzalo, Chechik, Shiri, Navarro, Gonzalo, Rotenberg, Eva, Herman, Grzegorz, Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands, Birkbeck College [University of London], Max Planck Institute for Informatics [Saarbrücken], University of Warsaw (UW), Centrum Wiskunde & Informatica (CWI), Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Bioinformatics, AIMMS, and Bio Informatics (IBIVU)
Subjects: FOS: Computer and information sciences, SDG 16 - Peace, approximate circular pattern matching, Hamming distance, Computer Science - Data Structures and Algorithms, SDG 16 - Peace, Justice and Strong Institutions, [INFO]Computer Science [cs], Data Structures and Algorithms (cs.DS), edit distance, Theory of computation → Pattern matching, Pattern matching, Justice and Strong Institutions
Abstract: We investigate the complexity of approximate circular pattern matching (CPM, in short) under the Hamming and edit distance. Under each of these two basic metrics, we are given a length-n text T, a length-m pattern P, and a positive integer threshold k, and we are to report all starting positions (called occurrences) of fragments of T that are at distance at most k from some cyclic rotation of P. In the decision version of the problem, we are to check if there is any such occurrence. All previous results for approximate CPM were either average-case upper bounds or heuristics, with the exception of the work of Charalampopoulos et al. [CKP^+, JCSS'21], who considered only the Hamming distance. For the reporting version of the approximate CPM problem, under the Hamming distance we improve upon the main algorithm of [CKP^+, JCSS'21] from 𝒪(n+(n/m) ⋅ k⁴) to 𝒪(n+(n/m) ⋅ k³ log log k) time; for the edit distance, we give an 𝒪(nk²)-time algorithm. Notably, for the decision versions and wide parameter-ranges, we give algorithms whose complexities are almost identical to the state-of-the-art for standard (i.e., non-circular) approximate pattern matching: - For the decision version of the approximate CPM problem under the Hamming distance, we obtain an 𝒪(n+(n/m) ⋅ k² log k / log log k)-time algorithm, which works in 𝒪(n) time whenever k = 𝒪(√{m log log m / log m}). In comparison, the fastest algorithm for the standard counterpart of the problem, by Chan et al. [CGKKP, STOC’20], runs in 𝒪(n) time only for k = 𝒪(√m). We achieve this result via a reduction to a geometric problem by building on ideas from [CKP^+, JCSS'21] and Charalampopoulos et al. [CKW, FOCS'20]. - For the decision version of the approximate CPM problem under the edit distance, the 𝒪(nklog³ k) runtime of our algorithm near matches the 𝒪(nk) runtime of the Landau-Vishkin algorithm [LV, J. Algorithms'89] for approximate pattern matching under edit distance; the latter algorithm remains the fastest known for k = Ω(m^{2/5}). As a stepping stone, we propose an 𝒪(nklog³ k)-time algorithm for solving the Longest Prefix k'-Approximate Match problem, proposed by Landau et al. [LMS, SICOMP'98], for all k' ∈ {1,…,k}. Our algorithm is based on Tiskin’s theory of seaweeds [Tiskin, Math. Comput. Sci.'08], with recent advancements (see Charalampopoulos et al. [CKW, FOCS'22]), and on exploiting the seaweeds' relation to Monge matrices. In contrast, we obtain a conditional lower bound that suggests a polynomial separation between approximate CPM under the Hamming distance over the binary alphabet and its non-circular counterpart. We also show that a strongly subquadratic-time algorithm for the decision version of approximate CPM under edit distance would refute the Strong Exponential Time Hypothesis., LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 35:1-35:19
Published: 2022
Full Text: View/download PDF

14. Hybrid modelling to Solve Optimal Concentrations of Metabolites and Enzymes in Constraint-based modelling

Author: Peres, Sabine, Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and ITMO cancer - 21CM141-00
Subjects: Metabolic Network, Answer Set Programming, Kinetics Constraints, Geometric Programming, [SDV]Life Sciences [q-bio], [INFO]Computer Science [cs], Elementary Flux Modes, Constraint-Based Modelling
Abstract: International audience; The Constraint-based modelling is a widely used approach to analyze genotype-phenotype relationships. The main key concepts are stoichiometric analysis such as flux balance analysis (FBA), Resource Balance Analysis (RBA) or elementary flux mode (EFM) analysis. While FBA identifies optimal flux distribution with respect to a given objective, the EFM characterizes the totality of the available solution space in terms of minimal pathways but their number leads to a combinatorial explosion for large networks. The RBA predicts for a specific environment, the set of possible cell configurations compatible with the available resources and extends very significantly the predictive power of the FBA. However, when stoichiometric and kinetic constraints are considered together, the set of possible flux configurations does not generally define a convex set since the kinetic function are not linear. The problem resolution has thus multiple local maxima. Recent works showed that the optimal solution of constraint enzyme allocation problems with general kinetics is an EFM. Based in this recent outcome, we write the resource allocation constraint on kinetic optimization problem into a geometric problem in an EFM, i.e. a convex optimal problem easily solved. Thus to predict optimal flux modes, we compute constraints EFMs with our tool ASPefm based on Answer Set Programming to save time and space computation. ASPefm allows the integration of Boolean and linear constraints such as thermodynamic, environment, transcriptomic regulatory rules, and resource operating cost (that identify the most efficient EFMs for converting substrate into biomass) using the solver ClingoLP which combined logic programming and linear programming. The convex optimization problem is then resolved on each constraint EFMs which provides for this mode, the optimal repartition of resources among enzymes and the associated metabolite concentrations. We applied our method to the central carbon metabolism of E. coli, with a detailed model of the respiration chains, ATPase (including explicitly the proton motive force). The optimal flux mode is the overflow of acetate which is in agreement with known experimental results. This approach allowed us to explore whether certain experimental properties observed on E. coli are consistent and consequences of an optimal repartition of bacterial resources. Our method is very promising in synthetic biology and increased the ability to efficiently design biological systems.
Published: 2023

15. Mutations in the non-coding RNU4ATAC gene affect the homeostasis and function of the Integrator complex

Author: Fatimat Almentina Ramos Shidi, Audric Cologne, Marion Delous, Alicia Besson, Audrey Putoux, Anne-Louise Leutenegger, Vincent Lacroix, Patrick Edery, Sylvie Mazoyer, Rémy Bordonné, Institut de Génétique Moléculaire de Montpellier (IGMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Centre de recherche en neurosciences de Lyon - Lyon Neuroscience Research Center (CRNL), Université de Lyon-Université de Lyon-Université Jean Monnet - Saint-Étienne (UJM)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Hospices Civils de Lyon (HCL), Maladies neurodéveloppementales et neurovasculaires (NeuroDiderot (UMR_S_1141 / U1141)), and Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Paris Cité (UPCité)
Subjects: [SDV]Life Sciences [q-bio], Genetics
Abstract: Various genetic diseases associated with microcephaly and developmental defects are due to pathogenic variants in the U4atac small nuclear RNA (snRNA), a component of the minor spliceosome essential for the removal of U12-type introns from eukaryotic mRNAs. While it has been shown that a few RNU4ATAC mutations result in impaired binding of essential protein components, the molecular defects of the vast majority of variants are still unknown. Here, we used lymphoblastoid cells derived from RNU4ATAC compound heterozygous (g.108_126del;g.111G>A) twin patients with MOPD1 phenotypes to analyze the molecular consequences of the mutations on small nuclear ribonucleoproteins (snRNPs) formation and on splicing. We found that the U4atac108_126del mutant is unstable and that the U4atac111G>A mutant as well as the minor di- and tri-snRNPs are present at reduced levels. Our results also reveal the existence of 3’-extended snRNA transcripts in patients’ cells. Moreover, we show that the mutant cells have alterations in splicing of INTS7 and INTS10 minor introns, contain lower levels of the INTS7 and INTS10 proteins and display changes in the assembly of Integrator subunits. Altogether, our results show that compound heterozygous g.108_126del;g.111G>A mutations induce splicing defects and affect the homeostasis and function of the Integrator complex.
Published: 2022
Full Text: View/download PDF

16. Efficient compartmentalization in insect bacteriomes protects symbiotic bacteria from host immune system

Author: Mariana Galvão Ferrarini, Elisa Dell’Aglio, Agnès Vallier, Séverine Balmand, Carole Vincent-Monégat, Sandrine Hughes, Benjamin Gillet, Nicolas Parisot, Anna Zaidman-Rémy, Cristina Vieira, Abdelaziz Heddi, Rita Rebollo, Biologie Fonctionnelle, Insectes et Interactions (BF2I), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Institut de Génomique Fonctionnelle de Lyon (IGFL), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Eléments transposables, évolution, populations, Département génétique, interactions et évolution des génomes [LBBE] (GINSENG), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-17-CE20-0031,GREEN,Comprendre les mécanismes de régulation et la fonction des gènes de la réponse immunitaire de l'hôte pour perturber la symbiose et le contrôle des endosymbiotes chez les insectes nuisibles(2017), and ANR-17-CE20-0015,Unleash,Découverte de la relation entre épigénétique et symbiose chez l'insecte(2017)
Subjects: Microbiology (medical), [SDV.GEN.GPO]Life Sciences [q-bio]/Genetics/Populations and Evolution [q-bio.PE], Bacteria, fungi, Immunity, Peptidoglycan, biochemical phenomena, metabolism, and nutrition, Microbiology, Coleoptera, [SDV.MP]Life Sciences [q-bio]/Microbiology and Parasitology, Immune System, bacteria, Animals, Insect Proteins, Weevils, Antimicrobial peptides, TCT, Symbiosis, [SDV.EE.IEO]Life Sciences [q-bio]/Ecology, environment/Symbiosis
Abstract: Background Many insects house symbiotic intracellular bacteria (endosymbionts) that provide them with essential nutrients, thus promoting the usage of nutrient-poor habitats. Endosymbiont seclusion within host specialized cells, called bacteriocytes, often organized in a dedicated organ, the bacteriome, is crucial in protecting them from host immune defenses while avoiding chronic host immune activation. Previous evidence obtained in the cereal weevil Sitophilus oryzae has shown that bacteriome immunity is activated against invading pathogens, suggesting endosymbionts might be targeted and impacted by immune effectors during an immune challenge. To pinpoint any molecular determinants associated with such challenges, we conducted a dual transcriptomic analysis of S. oryzae’s bacteriome subjected to immunogenic peptidoglycan fragments. Results We show that upon immune challenge, the bacteriome actively participates in the innate immune response via induction of antimicrobial peptides (AMPs). Surprisingly, endosymbionts do not undergo any transcriptomic changes, indicating that this potential threat goes unnoticed. Immunohistochemistry showed that TCT-induced AMPs are located outside the bacteriome, excluding direct contact with the endosymbionts. Conclusions This work demonstrates that endosymbiont protection during an immune challenge is mainly achieved by efficient confinement within bacteriomes, which provides physical separation between host systemic response and endosymbionts.
Published: 2022
Full Text: View/download PDF

17. SMAD2/3 mediate oncogenic effects of TGF-β in the absence of SMAD4

Author: Adrien Bertrand-Chapel, Cassandre Caligaris, Tanguy Fenouil, Clara Savary, Sophie Aires, Sylvie Martel, Paul Huchedé, Christelle Chassot, Véronique Chauvet, Victoire Cardot-Ruffino, Anne-Pierre Morel, Fabien Subtil, Kayvan Mohkam, Jean-Yves Mabrut, Laurie Tonon, Alain Viari, Philippe Cassier, Valérie Hervieu, Marie Castets, Alain Mauviel, Stéphanie Sentis, Laurent Bartholin, Centre Léon Bérard [Lyon], Centre de Recherche en Cancérologie de Lyon (UNICANCER/CRCL), Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Hospices Civils de Lyon (HCL), Synergie Lyon Cancer-Platform of Bioinformatics-Gilles Thomas, Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and Institut Curie [Paris]
Subjects: Carcinogenesis, [SDV]Life Sciences [q-bio], Medicine (miscellaneous), Smad2 Protein, General Biochemistry, Genetics and Molecular Biology, Pancreatic Neoplasms, Transforming Growth Factor beta1, Transforming Growth Factor beta, Humans, RNA, Smad3 Protein, General Agricultural and Biological Sciences, Carcinoma, Pancreatic Ductal, Smad4 Protein
Abstract: TGF-β signaling is involved in pancreatic ductal adenocarcinoma (PDAC) tumorigenesis, representing one of the four major pathways genetically altered in 100% of PDAC cases. TGF-β exerts complex and pleiotropic effects in cancers, notably via the activation of SMAD pathways, predominantly SMAD2/3/4. Though SMAD2 and 3 are rarely mutated in cancers, SMAD4 is lost in about 50% of PDAC, and the role of SMAD2/3 in a SMAD4-null context remains understudied. We herein provide evidence of a SMAD2/3 oncogenic effect in response to TGF-β1 in SMAD4-null human PDAC cancer cells. We report that inactivation of SMAD2/3 in SMAD4-negative PDAC cells compromises TGF-β-driven collective migration mediated by FAK and Rho/Rac signaling. Moreover, RNA-sequencing analyses highlight a TGF-β gene signature related to aggressiveness mediated by SMAD2/3 in the absence of SMAD4. Using a PDAC patient cohort, we reveal that SMAD4-negative tumors with high levels of phospho-SMAD2 are more aggressive and have a poorer prognosis. Thus, loss of SMAD4 tumor suppressive activity in PDAC leads to an oncogenic gain-of-function of SMAD2/3, and to the onset of associated deleterious effects.
Published: 2022
Full Text: View/download PDF

18. Constructing Antidictionaries of Long Texts in Output-Sensitive Space

Author: Solon P. Pissis, Golnaz Badkobeh, Alice Héliou, Gabriele Fici, Lorraine A.K. Ayad, Department of Informatics [King's College London], King‘s College London, Goldsmiths, University of London (Goldsmiths College), University of London [London], Dipartimento di Matematica e Informatica [Palermo], Università degli studi di Palermo - University of Palermo, Centrum Wiskunde & Informatica (CWI), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Bioinformatics, AIMMS, Bio Informatics (IBIVU), Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands, Ayad L.A.K., Badkobeh G., Fici G., Heliou A., and Pissis S.P.
Subjects: 0301 basic medicine, Antidictionary, Settore INF/01 - Informatica, Output sensitive algorithm, 0102 computer and information sciences, Space (mathematics), 01 natural sciences, Theoretical Computer Science, String algorithm, Prefix, Set (abstract data type), Combinatorics, 03 medical and health sciences, 030104 developmental biology, Computational Theory and Mathematics, 010201 computation theory & mathematics, Data compression, Output-sensitive algorithm, [INFO]Computer Science [cs], Suffix, Alphabet, Absent word, Word (group theory), Mathematics
Abstract: A wordxthat is absent from a wordyis calledminimalif all its proper factors occur iny. Given a collection ofkwordsy1, … ,ykover an alphabetΣ, we are asked to compute the set$\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$M{y1,…,yk}ℓof minimal absent words of length at mostℓof the collection {y1, … ,yk}. The set$\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$M{y1,…,yk}ℓcontains all the wordsxsuch thatxis absent from all the words of the collection while there existi,j, such that the maximal proper suffix ofxis a factor ofyiand the maximal proper prefix ofxis a factor ofyj. In data compression, this corresponds to computing the antidictionary ofkdocuments. In bioinformatics, it corresponds to computing words that are absent from a genome ofkchromosomes. Indeed, the set$\mathrm {M}^{\ell }_{y}$Myℓof minimal absent words of a wordyis equal to$\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$M{y1,…,yk}ℓfor any decomposition ofyinto a collection of wordsy1, … ,yksuch that there is an overlap of length at leastℓ− 1 between any two consecutive words in the collection. This computation generally requiresΩ(n) space forn= |y| using any of the plenty available$\mathcal {O}(n)$O(n)-time algorithms. This is because anΩ(n)-sized text index is constructed overywhich can be impractical for largen. We do the identical computation incrementally using output-sensitive space. This goal is reasonable when$\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| =o(n)$∥M{y1,…,yN}ℓ∥=o(n), for allN∈ [1,k], where ∥S∥ denotes the sum of the lengths of words in setS. For instance, in the human genome,n≈ 3 × 109but$\| \mathrm {M}^{12}_{\{y_1,\ldots ,y_k\}}\| \approx 10^{6}$∥M{y1,…,yk}12∥≈106. We consider a constant-sized alphabet for stating our results. We show thatall$\mathrm {M}^{\ell }_{y_{1}},\ldots ,\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$My1ℓ,…,M{y1,…,yk}ℓcan be computed in$\mathcal {O}(kn+{\sum }^{k}_{N=1}\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| )$O(kn+∑N=1k∥M{y1,…,yN}ℓ∥)total time using$\mathcal {O}(\textsc {MaxIn}+\textsc {MaxOut})$O(MaxIn+MaxOut)space, where MaxIn is the length of the longest word in {y1, … ,yk} and$\textsc {MaxOut}=\max \limits \{\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| :N\in [1,k]\}$MaxOut=max{∥M{y1,…,yN}ℓ∥:N∈[1,k]}. Proof-of-concept experimental results are also provided confirming our theoretical findings and justifying our contribution.
Published: 2021
Full Text: View/download PDF

19. On the domination number of $t$-constrained de Bruijn graphs

Author: Calamoneri, Tiziana, Monti, Angelo, Sinaimeri, Blerina, Department of Informatics and System Sciences (Sapienza University of Rome), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and This work is partially supported by the following research projects: Sapienza University of Rome, projects: no. RM120172A3F313FE 'Measuring the similarity of biological and medical structures through graph isomorphism', no. RM11916B462574AD 'A deep study of phylogenetic tree reconciliations' and no. RM1181642702045E 'Comparative Analysis of Phylogenies
Subjects: Mathematics::Combinatorics, Domination number, de Bruijn graph, Kautz graph, General Computer Science, Mathematics::History and Overview, 05Cxx, 05C69, Kautz graph, Domination number, Nonlinear Sciences::Cellular Automata and Lattice Gases, Quantitative Biology::Genomics, Theoretical Computer Science, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, FOS: Mathematics, Discrete Mathematics and Combinatorics, Computer Science::Programming Languages, Mathematics - Combinatorics, [INFO]Computer Science [cs], Combinatorics (math.CO), de Bruijn graph, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: Motivated by the work on the domination number of directed de Bruijn graphs and some of its generalizations, in this paper we introduce a natural generalization of de Bruijn graphs (directed and undirected), namely $t$-constrained de Bruijn graphs, where $t$ is a positive integer, and then study the domination number of these graphs. Within the definition of $t$-constrained de Bruijn graphs, de Bruijn and Kautz graphs correspond to 1-constrained and 2-constrained de Bruijn graphs, respectively. This generalization inherits many structural properties of de Bruijn graphs and may have similar applications in interconnection networks or bioinformatics. We establish upper and lower bounds for the domination number on $t$-constrained de Bruijn graphs both in the directed and in the undirected case. These bounds are often very close and in some cases we are able to find the exact value.
Published: 2022
Full Text: View/download PDF

20. Immune and Genetic Signatures of Breast Carcinomas Triggering Anti-Yo–Associated Paraneoplastic Cerebellar Degeneration

Author: Elise Peter, Isabelle Treilleux, Valentin Wucher, Emma Jougla, Alberto Vogrig, Daniel Pissaloux, Sandrine Paindavoine, Justine Berthet, Géraldine Picard, Véronique Rogemond, Marine Villard, Clémentine Vincent, Laurie Tonon, Alain Viari, Jérôme Honnorat, Bertrand Dubois, Virginie Desestret, Centre Léon Bérard [Lyon], Synergie Lyon Cancer-Platform of Bioinformatics-Gilles Thomas, Centre de Recherche en Cancérologie de Lyon (UNICANCER/CRCL), Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and ANR-18-RHUS-0012,BETPSY,Biomarkers in autoimmune EncephaliTis and Paraneoplastic neurological SYndromes(2018)
Subjects: Neurology, Antibodies, Neoplasm, [SDV]Life Sciences [q-bio], Humans, Neoplasm, Nerve Tissue Proteins, Female, Breast Neoplasms, Neurology (clinical), Autoantibodies, Paraneoplastic Cerebellar Degeneration, Antibodies
Abstract: Background and ObjectivesParaneoplastic cerebellar degeneration (PCD) with anti-Yo antibodies is a cancer-related autoimmune disease directed against neural antigens expressed by tumor cells. A putative trigger of the immune tolerance breakdown is genetic alteration of Yo antigens. We aimed to identify the tumors' genetic and immune specificities involved in Yo-PCD pathogenesis.MethodsUsing clinicopathologic data, immunofluorescence (IF) imaging, and whole-transcriptome analysis, 22 breast cancers (BCs) associated with Yo-PCD were characterized in terms of oncologic characteristics, genetic alteration of Yo antigens, differential gene expression profiles, and morphofunctional specificities of their in situ antitumor immunity by comparing them with matched control BCs.ResultsYo-PCD BCs were invasive carcinoma of no special type, which early metastasized to lymph nodes. They overexpressed human epidermal growth factor receptor 2 (HER2) but were hormone receptor negative. All Yo-PCD BCs carried at least 1 genetic alteration (variation or gain in copy number) on CDR2L, encoding the main Yo antigen that was found aberrantly overexpressed in Yo-PCD BCs. Analysis of the differentially expressed genes found 615 upregulated and 54 downregulated genes in Yo-PCD BCs compared with HER2-driven control BCs without PCD. Ontology enrichment analysis found significantly upregulated adaptive immune response pathways in Yo-PCD BCs. IF imaging confirmed an intense immune infiltration with an overwhelming predominance of immunoglobulin G–plasma cells.DiscussionThese data confirm the role of genetic alterations of Yo antigens in triggering the immune tolerance breakdown but also outline a specific biomolecular profile in Yo-PCD BCs, suggesting a cancer-specific pathogenesis.
Published: 2022
Full Text: View/download PDF

21. Phyloformer: towards fast and accurate phylogeny estimation with self-attention networks

Author: Luca Nesterenko, Bastien Boussau, Laurent Jacob, Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Le Cocon, Département PEGASE [LBBE] (PEGASE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and Baobab
Subjects: [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], [SDV.BID.SPT]Life Sciences [q-bio]/Biodiversity/Systematics, Phylogenetics and taxonomy, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: An important problem in molecular evolution is that of phylogenetic reconstruction, that is, given a set of sequences descending from a common ancestor, the reconstruction of the binary tree describing their evolution from the latter. State-of-the-art methods for the task, namely Maximum likelihood and Bayesian inference, have a high computational cost, which limits their usability on large datasets. Recently researchers have begun investigating deep learning approaches to the problem but so far these attempts have been limited to the reconstruction of quartet tree topologies, addressing phylogenetic reconstruction as a classification problem. We present here a radically different approach with a transformer-based network architecture that, given a multiple sequence alignment, predicts all the pairwise evolutionary distances between the sequences, which in turn allow us to accurately reconstruct the tree topology with standard distance-based algorithms. The architecture and its high degree of parameter sharing allow us to apply the same network to alignments of arbitrary size, both in the number of sequences and in their length. We evaluate our network Phyloformer on two types of simulations and find that its accuracy matches that of a Maximum Likelihood method on datasets that resemble training data, while being significantly faster.
Published: 2022
Full Text: View/download PDF

22. Local improvement algorithms for a path packing problem: a performance analysis based on linear programming

Author: Leen Stougie, Magnús M. Halldórsson, K.M.J. de Bontridder, R. Ravi, Cor A. J. Hurkens, Jan Karel Lenstra, Bjarni V. Halldorsson, Mathematics and Computer Science, Combinatorial Optimization 1, Discrete Mathematics, Operations Analytics, Tinbergen Institute, Amsterdam Business Research Institute, Mapscape [Eindhoven], Reykjavík University, Eindhoven University of Technology [Eindhoven] (TU/e), Centrum Wiskunde & Informatica (CWI), Carnegie Mellon University [Pittsburgh] (CMU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands, and Mapscape b.v., Eindhoven
Subjects: Linear programming, Computer science, Applied Mathematics, Local search, Performance guarantee, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Path packing, Management Science and Operations Research, 01 natural sciences, Industrial and Manufacturing Engineering, Packing problems, 010201 computation theory & mathematics, Greedy algorithm, 0202 electrical engineering, electronic engineering, information engineering, Graph (abstract data type), [INFO]Computer Science [cs], Algorithm, Software, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; Given a graph, we wish to find a maximum number of vertex-disjoint paths of length 2. We propose a series of local improvement algorithms for this problem, and present a linear-programming based method for analyzing their performance.
Published: 2021
Full Text: View/download PDF

23. Variable-order reference-free variant discovery with the Burrows-Wheeler Transform

Author: Nadia Pisanti, Nicola Prezza, Marinella Sciortino, Giovanna Rosone, University of Pisa - Università di Pisa, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Università degli studi di Palermo - University of Palermo, Prezza N., Pisanti N., Sciortino M., and Rosone G.
Subjects: Burrows–Wheeler transform, Computer science, [SDV]Life Sciences [q-bio], Value (computer science), SNP, Assembly-free, 0102 computer and information sciences, lcsh:Computer applications to medicine. Medical informatics, 01 natural sciences, Biochemistry, Polymorphism, Single Nucleotide, 03 medical and health sciences, BWT, Chromosome (genetic algorithm), Structural Biology, Humans, Sensitivity (control systems), Molecular Biology, lcsh:QH301-705.5, Alignment-free, INDEL, 030304 developmental biology, De Bruijn sequence, 0303 health sciences, Settore INF/01 - Informatica, Applied Mathematics, Research, Genomics, Sequence Analysis, DNA, Data structure, Graph, Computer Science Applications, Variable (computer science), lcsh:Biology (General), 010201 computation theory & mathematics, Adjacency list, lcsh:R858-859.7, Suffix, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Algorithm, Algorithms
Abstract: Background In [Prezza et al., AMB 2019], a new reference-free and alignment-free framework for the detection of SNPs was suggested and tested. The framework, based on the Burrows-Wheeler Transform (BWT), significantly improves sensitivity and precision of previous de Bruijn graphs based tools by overcoming several of their limitations, namely: (i) the need to establish a fixed value, usually small, for the order k, (ii) the loss of important information such as k-mer coverage and adjacency of k-mers within the same read, and (iii) bad performance in repeated regions longer than k bases. The preliminary tool, however, was able to identify only SNPs and it was too slow and memory consuming due to the use of additional heavy data structures (namely, the Suffix and LCP arrays), besides the BWT. Results In this paper, we introduce a new algorithm and the corresponding tool ebwt2InDel that (i) extend the framework of [Prezza et al., AMB 2019] to detect also INDELs, and (ii) implements recent algorithmic findings that allow to perform the whole analysis using just the BWT, thus reducing the working space by one order of magnitude and allowing the analysis of full genomes. Finally, we describe a simple strategy for effectively parallelizing our tool for SNP detection only. On a 24-cores machine, the parallel version of our tool is one order of magnitude faster than the sequential one. The tool ebwt2InDel is available at github.com/nicolaprezza/ebwt2InDel. Conclusions Results on a synthetic dataset covered at 30x (Human chromosome 1) show that our tool is indeed able to find up to 83% of the SNPs and 72% of the existing INDELs. These percentages considerably improve the 71% of SNPs and 51% of INDELs found by the state-of-the art tool based on de Bruijn graphs. We furthermore report results on larger (real) Human whole-genome sequencing experiments. Also in these cases, our tool exhibits a much higher sensitivity than the state-of-the art tool.
Published: 2020
Full Text: View/download PDF

24. Mycoplasma hyopneumoniae J elicits an antioxidant response and decreases the expression of ciliary genes in infected swine epithelial cells

Author: Scheila G. Mucha, Sophie Rome, Marie-France Sagot, Laurent Guyon, Mariana Galvão Ferrarini, Carol Moraga, Florence Tardy, Alex Di Genova, Arnaldo Zaha, Centro de Biotecnologia [Porto Alegre] (CBiot), Universidade Federal do Rio Grande do Sul [Porto Alegre] (UFRGS), Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Recherche Interdisciplinaire de Grenoble (IRIG), Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Mycoplasmoses des Ruminants - UMR (MYCO), Université de Lyon-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS), Cardiovasculaire, métabolisme, diabétologie et nutrition (CarMeN), Université de Lyon-Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Hospices Civils de Lyon (HCL)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), CAPES782/13European Research Council (ERC)[247073]10CAPES CAPES-Cofecub doctoral fellowship CAPES post-doctoral fellowship (CAPES-Biologia Computacional) 611 23038.010043/2013-02CONICYT BECAS CHILE DOCTORADO 2016/FOLIO 72170320, Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Hospices Civils de Lyon (HCL)
Subjects: 0301 basic medicine, Swine, [SDV]Life Sciences [q-bio], lcsh:Medicine, Article, Antioxidants, 03 medical and health sciences, 0302 clinical medicine, Mycoplasma hyopneumoniae, Bacterial Proteins, Gene expression, microRNA, Animals, Cilia, RNA, Messenger, Transcriptomics, lcsh:Science, Gene, Pathogen, Transcription factor, Cells, Cultured, Regulation of gene expression, Multidisciplinary, biology, Gene Expression Profiling, lcsh:R, Bacteriology, Epithelial Cells, Pneumonia of Swine, Mycoplasmal, biology.organism_classification, 3. Good health, Cell biology, Gene expression profiling, MicroRNAs, 030104 developmental biology, Gene Expression Regulation, miRNAs, lcsh:Q, Pathogens, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], 030217 neurology & neurosurgery, Biomarkers
Abstract: Mycoplasma hyopneumoniae is the most costly pathogen for swine production. Although several studies have focused on the host-bacterium association, little is known about the changes in gene expression of swine cells upon infection. To improve our understanding of this interaction, we infected swine epithelial NPTr cells with M. hyopneumoniae strain J to identify differentially expressed mRNAs and miRNAs. The levels of 1,268 genes and 170 miRNAs were significantly modified post-infection. Up-regulated mRNAs were enriched in genes related to redox homeostasis and antioxidant defense, known to be regulated by the transcription factor NRF2 in related species. Down-regulated mRNAs were enriched in genes associated with cytoskeleton and ciliary functions. Bioinformatic analyses suggested a correlation between changes in miRNA and mRNA levels, since we detected down-regulation of miRNAs predicted to target antioxidant genes and up-regulation of miRNAs targeting ciliary and cytoskeleton genes. Interestingly, most down-regulated miRNAs were detected in exosome-like vesicles suggesting that M. hyopneumoniae infection induced a modification of the composition of NPTr-released vesicles. Taken together, our data indicate that M. hyopneumoniae elicits an antioxidant response induced by NRF2 in infected cells. In addition, we propose that ciliostasis caused by this pathogen is partially explained by the down-regulation of ciliary genes.
Published: 2020
Full Text: View/download PDF

25. A Family of Tree-Based Generators for Bubbles in Directed Graphs

Author: Leandro Lima, Giuseppe F. Italiano, Luca Pepè Sciarria, Marie-France Sagot, Blerina Sinaimeri, Vicente Acuña, Center for Mathematical Modelling - Centro de Modelamiento Matematico [Santiago] (CMM), Universidad de Chile = University of Chile [Santiago] (UCHILE)-Centre National de la Recherche Scientifique (CNRS), European Bioinformatics Institute [Hinxton] (EMBL-EBI), EMBL Heidelberg, Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Università degli Studi di Roma Tor Vergata [Roma], Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Center for Mathematical Modeling (CMM), Universidad de Chile = University of Chile [Santiago] (UCHILE), European Bioinformatics Institute [Cambridge, UK], and University of Rome TorVergata
Subjects: Theoretical computer science, General Computer Science, Computer science, 0206 medical engineering, Context (language use), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Bottleneck, De Bruijn graph, Article, Theoretical Computer Science, Set (abstract data type), Physics::Fluid Dynamics, 03 medical and health sciences, symbols.namesake, Bubble generator, [INFO]Computer Science [cs], Tree based, Representation (mathematics), 030304 developmental biology, De Bruijn sequence, 0303 health sciences, [SDV.GEN]Life Sciences [q-bio]/Genetics, Directed graph, Graph, Computer Science Applications, Computational Theory and Mathematics, Bubble generator, directed graphs, alternative splicing, 010201 computation theory & mathematics, symbols, Geometry and Topology, 020602 bioinformatics, Generator (mathematics), Directed graphs, Alternative splicing
Abstract: International audience; Bubbles are pairs of internally vertex-disjoint (s, t)-paths in a directed graph. In de Bruijn graphs built from reads of RNA and DNA data, bubbles represent interesting biological events, such as alternative splicing (AS) and allelic differences (SNPs and indels). However, the set of all bubbles in a de Bruijn graph built from real data is usually too large to be efficiently enumerated and analysed in practice. In particular, despite significant research done in this area, listing bubbles still remains the main bottleneck for tools that detect AS events in a reference-free context. Recently, in [1] the concept of a bubble generator was introduced as a way for obtaining a compact representation of the bubble space of a graph. Although this bubble generator was quite effective in finding AS events, preliminary experiments showed that it is about 5 times slower than state-of-art methods. In this paper we propose a new family of bubble generators which improve substantially on previous work: bubble generators in this new family are about two orders of magnitude faster and are still able to achieve similar precision in identifying AS events. To highlight the practical value of our new bubble generators, we also report some experimental results on real datasets.
Published: 2020
Full Text: View/download PDF

26. Genetic analysis of lung cancer and the germline impact on somatic mutation burden

Author: Gabriel, AAG, Atkins, JR, Penha, RCC, Smith-Byrne, K, Gaborieau, V, Voegele, C, Abedi-Ardekani, B, Milojevic, M, Olaso, R, Meyer, V, Boland, A, Deleuze, JF, Zaridze, D, Mukeriya, A, Swiatkowska, B, Janout, V, Schejbalová, M, Mates, D, Stojšić, J, Ognjanovic, M, consortium, ILCCO, Witte, JS, Rashkin, SR, Kachuri, L, Hung, RJ, Kar, S, Brennan, P, Sertier, A-S, Ferrari, A, Viari, A, Johansson, M, Amos, CI, Foll, M, McKay, JD, Centre International de Recherche contre le Cancer - International Agency for Research on Cancer (CIRC - IARC), Organisation Mondiale de la Santé / World Health Organization Office (OMS / WHO), University of Oxford, Université Paris-Saclay, N.N. Blokhin Russian Cancer Research Center, Nofer Institute of Occupational Medicine (NIOM), Palacky University Olomouc, Charles University [Prague] (CU), National Institute of Public Health [Romania] (INSP), University Clinical Centre of Serbia, International Organisation for Cancer Prevention and Research, University of California [San Francisco] (UC San Francisco), University of California (UC), St Jude Children's Research Hospital, Centre for Systems Biology, Lunenfeld Tanenbaum Research Institute, Sinai Health System, Toronto, ON, Canada, University of Bristol [Bristol], Fondation Synergie Lyon Cancer [Lyon], Centre Léon Bérard [Lyon], Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Baylor College of Medicine (BCM), and Baylor University
Subjects: Cancer Research, Germ Cells, Lung Neoplasms, Oncology, [SDV]Life Sciences [q-bio], Mutation, Humans, Genetic Predisposition to Disease, ICEP, Polymorphism, Single Nucleotide, Genome-Wide Association Study
Abstract: Background Germline genetic variation contributes to lung cancer (LC) susceptibility. Previous genome-wide association studies (GWAS) have implicated susceptibility loci involved in smoking behaviors and DNA repair genes, but further work is required to identify susceptibility variants. Methods To identify LC susceptibility loci, a family history-based genome-wide association by proxy (GWAx) of LC (48 843 European proxy LC patients, 195 387 controls) was combined with a previous LC GWAS (29 266 patients, 56 450 controls) by meta-analysis. Colocalization was used to explore candidate genes and overlap with existing traits at discovered susceptibility loci. Polygenic risk scores (PRS) were tested within an independent validation cohort (1 666 LC patients vs 6 664 controls) using variants selected from the LC susceptibility loci and a novel selection approach using published GWAS summary statistics. Finally, the effects of the LC PRS on somatic mutational burden were explored in patients whose tumor resections have been profiled by exome (n = 685) and genome sequencing (n = 61). Statistical tests were 2-sided. Results The GWAx–GWAS meta-analysis identified 8 novel LC loci. Colocalization implicated DNA repair genes (CHEK1), metabolic genes (CYP1A1), and smoking propensity genes (CHRNA4 and CHRNB2). PRS analysis demonstrated that these variants, as well as subgenome-wide significant variants related to expression quantitative trait loci and/or smoking propensity, assisted in LC genetic risk prediction (odds ratio = 1.37, 95% confidence interval = 1.29 to 1.45; P Conclusions This study has expanded the number of LC susceptibility loci and provided insights into the molecular mechanisms by which these susceptibility variants contribute to LC development.
Published: 2022
Full Text: View/download PDF

27. All-pairs suffix/prefix in optimal time using Aho-Corasick space

Author: Solon Pissis, Grigorios Loukides, Bioinformatics, AIMMS, Bio Informatics (IBIVU), Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands, Department of Informatics [King's College London], King‘s College London, Centrum Wiskunde & Informatica (CWI), Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), European Project: 872539,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions, H2020-EU.1.3.3. - Stimulating innovation by means of cross-fertilisation of knowledge,H2020-MSCA-RISE-2019,PANGAIA(2020), and European Project: 956229,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions,ALPACA(2021)
Subjects: String algorithms, Data structures, Failure transition tree, Signal Processing, [INFO]Computer Science [cs], Aho-Corasick machine, Algorithms, Computer Science Applications, Information Systems, Theoretical Computer Science
Abstract: The all-pairs suffix/prefix (APSP) problem is a classic problem in computer science with many applications in bioinformatics. Given a set {S1,…,Sk} of k strings of total length n, we are asked to find, for each string Si, i∈[1,k], its longest suffix that is a prefix of string Sj, for all j≠i, j∈[1,k]. Several algorithms running in the optimal O(n+k2) time for solving APSP are known. All of these algorithms are based on suffix sorting and thus require space Ω(n) in any case. We consider the parameterized version of the APSP problem, denoted by ℓ-APSP, in which we are asked to output only the pairs whose suffix/prefix overlap is of length at least ℓ. We give an algorithm for solving ℓ-APSP that runs in the optimal O(n+|OUTPUTℓ|) time using O(n) space, where OUTPUTℓ is the set of output pairs. Our algorithm is thus optimal for the APSP problem as well by setting ℓ=0. Notably, our algorithm is fundamentally different from all optimal algorithms solving the APSP problem: it does not rely on sorting the suffixes of all input strings but on a novel traversal of the Aho-Corasick machine, and it thus requires space linear in the size of the machine.
Published: 2022
Full Text: View/download PDF

28. Clustering sequence graphs

Author: Haodi Zhong, Grigorios Loukides, Solon P. Pissis, Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands, Department of Informatics [King's College London], King‘s College London, Centrum Wiskunde & Informatica (CWI), Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), European Project: 956229,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions,ALPACA(2021), European Project: 872539,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions, and H2020-EU.1.3.3. - Stimulating innovation by means of cross-fertilisation of knowledge,H2020-MSCA-RISE-2019,PANGAIA(2020)
Subjects: Information Systems and Management, Graph clustering, Sequence clustering, [INFO]Computer Science [cs], Sequential data
Abstract: International audience; In application domains ranging from social networks to e-commerce, it is important to cluster users with respect to both their relationships (e.g., friendship or trust) and their actions (e.g., visited locations or rated products). Motivated by these applications, we introduce here the task of clustering the nodes of a sequence graph, i.e., a graph whose nodes are labeled with strings (e.g., sequences of users' visited locations or rated products). Both string clustering algorithms and graph clustering algorithms are inappropriate to deal with this task, as they do not consider the structure of strings and graph simultaneously. Moreover, attributed graph clustering algorithms generally construct poor solutions because they need to represent a string as a vector of attributes, which inevitably loses information and may harm clustering quality. We thus introduce the problem of clustering a sequence graph. We first propose two pairwise distance measures for sequence graphs, one based on edit distance and shortest path distance and another one based on SimRank. We then formalize the problem under each measure, showing also that it is NP-hard. In addition, we design a polynomial-time 2-approximation algorithm, as well as a heuristic for the problem. Experiments using real datasets and a case study demonstrate the effectiveness and efficiency of our methods.
Published: 2022
Full Text: View/download PDF

29. Totoro: Identifying Active Reactions During the Transient State for Metabolic Perturbations

Author: Mariana Galvão Ferrarini, Irene Ziska, Ricardo Andrade, Alice Julien-Laferrière, Louis Duchemin, Roberto Marcondes César, Arnaud Mary, Susana Vinga, Marie-France Sagot, Biologie Fonctionnelle, Insectes et Interactions (BF2I), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Baobab, Département PEGASE [LBBE] (PEGASE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Instituto de Matemática e Estatística (IME), Universidade de São Paulo = University of São Paulo (USP), Soladis GmBH [Basel], Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa (INESC-ID), and Instituto Superior Técnico, Universidade Técnica de Lisboa (IST)-Instituto de Engenharia de Sistemas e Computadores (INESC)
Subjects: transient state, omics integration, METABOLÔMICA, [SDV]Life Sciences [q-bio], Genetics, metabolic networks, Molecular Medicine, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], metabolomics, Genetics (clinical), metabolic perturbation
Abstract: Motivation: The increasing availability of metabolomic data and their analysis are improving the understanding of cellular mechanisms and how biological systems respond to different perturbations. Currently, there is a need for novel computational methods that facilitate the analysis and integration of increasing volume of available data.Results: In this paper, we present Totoro a new constraint-based approach that integrates quantitative non-targeted metabolomic data of two different metabolic states into genome-wide metabolic models and predicts reactions that were most likely active during the transient state. We applied Totoro to real data of three different growth experiments (pulses of glucose, pyruvate, succinate) from Escherichia coli and we were able to predict known active pathways and gather new insights on the different metabolisms related to each substrate. We used both the E. coli core and the iJO1366 models to demonstrate that our approach is applicable to both smaller and larger networks.Availability:Totoro is an open source method (available at https://gitlab.inria.fr/erable/totoro) suitable for any organism with an available metabolic model. It is implemented in C++ and depends on IBM CPLEX which is freely available for academic purposes.
Published: 2022
Full Text: View/download PDF

30. High Stability of the Epigenome in Drosophila Interspecific Hybrids

Author: Alejandra Bodelón, Marie Fablet, Philippe Veber, Cristina Vieira, Maria Pilar García Guerreiro, Universitat Autònoma de Barcelona (UAB), Eléments transposables, évolution, populations, Département génétique, interactions et évolution des génomes [LBBE] (GINSENG), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: deregulation, [SDV.BID.EVO]Life Sciences [q-bio]/Biodiversity/Populations and Evolution [q-bio.PE], Ovary, interspecific hybrids, Interspecific hybrids, epigenome, Histone methylation, Deregulation, Epigenome, [SDV.BBM.GTP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN], DNA Transposable Elements, Genetics, Animals, Humans, Hybridization, Genetic, Female, Drosophila, histone methylation, transposable elements, Transposable elements, Ecology, Evolution, Behavior and Systematics
Abstract: Interspecific hybridization is often seen as a genomic stress that may lead to new gene expression patterns and deregulation of transposable elements (TEs). The understanding of expression changes in hybrids compared with parental species is essential to disentangle their putative role in speciation processes. However, to date we ignore the detailed mechanisms involved in genomic deregulation in hybrids. We studied the ovarian transcriptome and epigenome of the Drosophila buzzatii and Drosophila koepferae species together with their F1 hybrid females. We found a trend toward underexpression of genes and TE families in hybrids. The epigenome in hybrids was highly similar to the parental epigenomes and showed intermediate histone enrichments between parental species in most cases. Differential gene expression in hybrids was often associated only with changes in H3K4me3 enrichments, whereas differential TE family expression in hybrids may be associated with changes in H3K4me3, H3K9me3, or H3K27me3 enrichments. We identified specific genes and TE families, which their differential expression in comparison with the parental species was explained by their differential chromatin mark combination enrichment. Finally, cis–trans compensatory regulation could also contribute in some way to the hybrid deregulation. This work provides the first study of histone content in Drosophila interspecific hybrids and their effect on gene and TE expression deregulation.
Published: 2022
Full Text: View/download PDF

31. Elastic-Degenerate String Matching with 1 Error

Author: Bernardini, Giulia, Gabory, Esteban, Pissis, Solon P., Stougie, Leen, Sweering, Michelle, Zuba, Wiktor, Castañeda, Armando, Rodríguez-Henríquez, Francisco, Università degli studi di Trieste = University of Trieste, Centrum Wiskunde & Informatica (CWI), Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Netherlands Organisation for Scientific Research (NWO), project OCENW.GROOT.2019.015 and 024.002.003, MUR - FSE REACT EU - PON R&I 2014-2020, European Project: 872539,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions, H2020-EU.1.3.3. - Stimulating innovation by means of cross-fertilisation of knowledge,H2020-MSCA-RISE-2019,PANGAIA(2020), European Project: 956229,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions,ALPACA(2021), Bioinformatics, AIMMS, Bio Informatics (IBIVU), Operations Analytics, Tinbergen Institute, Amsterdam Business Research Institute, Castañeda, Armando, Rodríguez-Henríquez, Francisco, Bernardini, Giulia, Gabory, Esteban, Pissis, Solon P., Stougie, Leen, Sweering, Michelle, and Zuba, Wiktor
Subjects: FOS: Computer and information sciences, String algorithms, Elastic-degenerate strings, SDG 16 - Peace, Approximate string matching, Degenerate strings, Edit distance, SDG 16 - Peace, Justice and Strong Institutions, Justice and Strong Institutions, String algorithm, Degenerate string, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs]
Abstract: An elastic-degenerate string is a sequence of $n$ finite sets of strings of total length $N$, introduced to represent a set of related DNA sequences, also known as a pangenome. The ED string matching (EDSM) problem consists in reporting all occurrences of a pattern of length $m$ in an ED text. This problem has recently received some attention by the combinatorial pattern matching community, culminating in an $\tilde{\mathcal{O}}(nm^{\omega-1})+\mathcal{O}(N)$-time algorithm [Bernardini et al., SIAM J. Comput. 2022], where $\omega$ denotes the matrix multiplication exponent and the $\tilde{\mathcal{O}}(\cdot)$ notation suppresses polylog factors. In the $k$-EDSM problem, the approximate version of EDSM, we are asked to report all pattern occurrences with at most $k$ errors. $k$-EDSM can be solved in $\mathcal{O}(k^2mG+kN)$ time, under edit distance, or $\mathcal{O}(kmG+kN)$ time, under Hamming distance, where $G$ denotes the total number of strings in the ED text [Bernardini et al., Theor. Comput. Sci. 2020]. Unfortunately, $G$ is only bounded by $N$, and so even for $k=1$, the existing algorithms run in $\Omega(mN)$ time in the worst case. In this paper we show that $1$-EDSM can be solved in $\mathcal{O}((nm^2 + N)\log m)$ or $\mathcal{O}(nm^3 + N)$ time under edit distance. For the decision version, we present a faster $\mathcal{O}(nm^2\sqrt{\log m} + N\log\log m)$-time algorithm. We also show that $1$-EDSM can be solved in $\mathcal{O}(nm^2 + N\log m)$ time under Hamming distance. Our algorithms for edit distance rely on non-trivial reductions from $1$-EDSM to special instances of classic computational geometry problems (2d rectangle stabbing or 2d range emptiness), which we show how to solve efficiently. In order to obtain an even faster algorithm for Hamming distance, we rely on employing and adapting the $k$-errata trees for indexing with errors [Cole et al., STOC 2004]., Comment: This is an extended version of a paper accepted at LATIN 2022
Published: 2022
Full Text: View/download PDF

32. Making de Bruijn Graphs Eulerian

Author: Bernardini, Giulia, Chen, Huiping, Loukides, Grigorios, Pissis, Solon P., Stougie, Leen, Sweering, Michelle, Bannai, Hideo, Holub, Jan, Bernardini, Giulia, Chen, Huiping, Loukides, Grigorio, Pissis, Solon P., Stougie, Leen, Sweering, Michelle, Università degli studi di Trieste = University of Trieste, Centrum Wiskunde & Informatica (CWI), King‘s College London, Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), The work in this paper is supported in part by: the Netherlands Organisation for Scientific Research (NWO) through project OCENW.GROOT.2019.015 'Optimization for and with Machine Learning (OPTIMAL)' and Gravitation-grant NETWORKS-024.002.003, a CSC scholarship, the Leverhulme Trust RPG-2019-399 project, European Project: 872539,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions, H2020-EU.1.3.3. - Stimulating innovation by means of cross-fertilisation of knowledge,H2020-MSCA-RISE-2019,PANGAIA(2020), European Project: 956229,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions,ALPACA(2021), Bannai, Hideo, Holub, Jan, Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands, Bioinformatics, AIMMS, Bio Informatics (IBIVU), Operations Analytics, Tinbergen Institute, and Amsterdam Business Research Institute
Subjects: graph algorithms, 2012 ACM Subject Classification Theory of computation → Pattern matching phrases string algorithms, [SDV]Life Sciences [q-bio], graph algorithm, [INFO]Computer Science [cs], Theory of computation → Pattern matching, string algorithm, string algorithms, Eulerian graph, de Bruijn graph
Abstract: A directed multigraph is called Eulerian if it has a circuit which uses each edge exactly once. Euler’s theorem tells us that a weakly connected directed multigraph is Eulerian if and only if every node is balanced. Given a collection S of strings over an alphabet Σ, the de Bruijn graph (dBG) of order k of S is a directed multigraph G_{S,k}(V,E), where V is the set of length-(k-1) substrings of the strings in S, and G_{S,k} contains an edge (u,v) with multiplicity m_{u,v}, if and only if the string u[0]⋅ v is equal to the string u⋅ v[k-2] and this string occurs exactly m_{u,v} times in total in strings in S. Let G_{Σ,k}(V_{Σ,k},E_{Σ,k}) be the complete dBG of Σ^k. The Eulerian Extension (EE) problem on G_{S,k} asks to extend G_{S,k} with a set ℬ of nodes from V_{Σ,k} and a smallest multiset 𝒜 of edges from E_{Σ,k} to make it Eulerian. Note that extending dBGs is algorithmically much more challenging than extending general directed multigraphs because some edges in dBGs are by definition forbidden. Extending dBGs lies at the heart of sequence assembly [Medvedev et al., WABI 2007], one of the most important tasks in bioinformatics. The novelty of our work with respect to existing works is that we allow not only to duplicate existing edges of G_{S,k} but to also add novel edges and nodes, in an effort to (i) connect multiple components and (ii) reduce the total EE cost. It is easy to show that EE on G_{S,k} is NP-hard via a reduction from shortest common superstring. We further show that EE remains NP-hard, even when we are not allowed to add new nodes, via a highly non-trivial reduction from 3-SAT. We thus investigate the following two problems underlying EE in dBGs: 1) When G_{S,k} is not weakly connected, we are asked to connect its d > 1 components using a minimum-weight spanning tree, whose edges are paths on the underlying G_{Σ,k} and weights are the corresponding path lengths. This way of connecting guarantees that no new unbalanced node is added. We show that this problem can be solved in 𝒪(|V|klog d+|E|) time, which is nearly optimal, since the size of G_{S,k} is Θ(|V|k+|E|). 2) When G_{S,k} is not balanced, we are asked to extend G_{S,k} to H_{S,k}(V∪ℬ,E∪𝒜) such that every node of H_{S,k} is balanced and the total number |𝒜| of added edges is minimized. We show that this problem can be solved in the optimal 𝒪(k|V| + |E|+ |𝒜|) time. Let us stress that, although our main contributions are theoretical, the algorithms we design for the above two problems are practical. We combine the two algorithms in one method that makes any dBG Eulerian; and show experimentally that the cost of the obtained feasible solutions on real-world dBGs is substantially smaller than the corresponding cost obtained by existing greedy approaches., LIPIcs, Vol. 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), pages 12:1-12:18
Published: 2022
Full Text: View/download PDF

33. Cophylogeny Reconstruction Allowing for Multiple Associations Through Approximate Bayesian Computation

Author: Sinaimeri, Blerina, Urbini, Laura, Sagot, Marie-France, Matias, Catherine, Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Probabilités, Statistique et Modélisation (LPSM (UMR_8001)), and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)
Subjects: reconciliation, FOS: Biological sciences, Populations and Evolution (q-bio.PE), spread, ABC method, Quantitative Biology - Populations and Evolution, cophylogeny, Quantitative Biology - Quantitative Methods, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Quantitative Methods (q-bio.QM)
Abstract: Phylogenetic tree reconciliation is extensively employed for the examination of coevolution between host and symbiont species. An important concern is the requirement for dependable cost values when selecting event-based parsimonious reconciliation. Although certain approaches deduce event probabilities unique to each pair of host and symbiont trees, which can subsequently be converted into cost values, a significant limitation lies in their inability to model the \emph{invasion} of diverse host species by the same symbiont species (termed as a spread event), which is believed to occur in symbiotic relationships. Invasions lead to the observation of multiple associations between symbionts and their hosts (indicating that a symbiont is no longer exclusive to a single host), which are incompatible with the existing methods of coevolution. Here, we present a method called AmoCoala (an enhanced version of the tool Coala) that provides a more realistic estimation of cophylogeny event probabilities for a given pair of host and symbiont trees, even in the presence of spread events. We expand the classical 4-event coevolutionary model to include 2 additional spread events (vertical and horizontal spreads) that lead to multiple associations. In the initial step, we estimate the probabilities of spread events using heuristic frequencies. Subsequently, in the second step, we employ an approximate Bayesian computation (ABC) approach to infer the probabilities of the remaining 4 classical events (cospeciation, duplication, host switch, and loss) based on these values. By incorporating spread events, our reconciliation model enables a more accurate consideration of multiple associations. This improvement enhances the precision of estimated cost sets, paving the way to a more reliable reconciliation of host and symbiont trees. To validate our method, we conducted experiments on synthetic datasets and demonstrated its efficacy using real-world examples. Our results showcase that AmoCoala produces biologically plausible reconciliation scenarios, further emphasizing its effectiveness.The software is accessible at \url{https://github.com/sinaimeri/AmoCoala} and supplementary material on a Dryad repository at \url{https://datadryad.org/stash/share/SHDH-seLRIznGHCRdQRUNuWE01TnmD5BipocuFrdNUg} with an associated DOI of doi:10.5061/dryad.5x69p8d6v (this last link will only be active upon publication).
Published: 2022
Full Text: View/download PDF

34. Computing the 4-Edge-Connected Components of a Graph: An Experimental Study

Author: Georgiadis, Loukas, Italiano, Giuseppe F., Kosinas, Evangelos, University of Ioannina, Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Theory of computation → Graph algorithms analysis, Connectivity Cuts, Mathematics of computing → Graph algorithms, [INFO]Computer Science [cs], Edge Connectivity, Graph algorithms
Abstract: The notions of edge-cuts and k-edge-connected components are fundamental in graph theory with numerous practical applications. Very recently, the first linear-time algorithms for computing all the 3-edge cuts and the 4-edge-connected components of a graph have been introduced. In this paper we present carefully engineered implementations of these algorithms and evaluate their efficiency in practice, by performing a thorough empirical study using both real-world graphs taken from a variety of application areas, as well as artificial graphs. To the best of our knowledge, this is the first experimental study for these problems, which highlights the merits and weaknesses of each technique. Furthermore, we present an improved algorithm for computing the 4-edge-connected components of an undirected graph in linear time. The new algorithm uses only elementary data structures, and is implementable in the pointer machine model of computation., LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 60:1-60:16
Published: 2022
Full Text: View/download PDF

35. Longest Palindromic Substring in Sublinear Time

Author: Charalampopoulos, Panagiotis, Pissis, Solon P., Radoszewski, Jakub, Bannai, Hideo, Holub, Jan, Bioinformatics, AIMMS, Bio Informatics (IBIVU), Bannai, Hideo, Holub, Jan, Reichman University [Herzliya], Centrum Wiskunde & Informatica (CWI), Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), University of Warsaw (UW), and Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands
Subjects: TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, [INFO]Computer Science [cs], Theory of computation → Pattern matching, longest common extension, longest palindromic substring, string algorithms, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: We revisit the classic algorithmic problem of computing a longest palidromic substring. This problem is solvable by a celebrated 𝒪(n)-time algorithm [Manacher, J. ACM 1975], where n is the length of the input string. For small alphabets, 𝒪(n) is not necessarily optimal in the word RAM model of computation: a string of length n over alphabet [0,σ) can be stored in 𝒪(n log σ/log n) space and read in 𝒪(n log σ/log n) time. We devise a simple 𝒪(n log σ/log n)-time algorithm for computing a longest palindromic substring. In particular, our algorithm works in sublinear time if σ = 2^{o(log n)}. Our technique relies on periodicity and on the 𝒪(n log σ/log n)-time constructible data structure of Kempa and Kociumaka [STOC 2019] that answers longest common extension queries in 𝒪(1) time., LIPIcs, Vol. 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), pages 20:1-20:9
Published: 2022
Full Text: View/download PDF

36. High-throughput genomics and transcriptomics to decipher host-symbiont molecular dialogue in the cereal weevil Sitophilus oryzae andSodalis pierantonius endosymbiotic association

Author: Parisot, Nicolas, Ferrarini, Mariana, Goubert, Clément, Vargas-Chávez, Carlos, Vallier, Agnès, Gillet, Benjamin, Hughes, Sandrine, Baa-Puyoulet, Patrice, Charles, Hubert, Calevro, Federica, Gil, Rosario, Latorre, Amparo, Vieira, Cristina, Rebollo, R., Heddi, Abdelaziz, Charles, Hubert, Biologie Fonctionnelle, Insectes et Interactions (BF2I), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Centro de Biotecnologia [Porto Alegre] (CBiot), Universidade Federal do Rio Grande do Sul [Porto Alegre] (UFRGS), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Eléments transposables, évolution, populations, Département génétique, interactions et évolution des génomes [LBBE] (GINSENG), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Plateforme nationale de Paléogénétique (Palgene), École normale supérieure de Lyon (ENS de Lyon), Institut de Génomique Fonctionnelle de Lyon (IGFL), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), and Universitat de València (UV)
Subjects: [SDV] Life Sciences [q-bio], [SDV.BIBS] Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], [SDV]Life Sciences [q-bio], [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Réseaux métaboliques réseaux génétiques
Abstract: International audience
Published: 2022

37. Reconstructing Phylogenetic Networks via Cherry Picking and Machine Learning

Author: Bernardini, Giulia, van Iersel, Leo, Julien, Esther, Stougie, Leen, Boucher, Christina, Rahmann, Sven, Operations Analytics, Tinbergen Institute, Amsterdam Business Research Institute, Boucher, Christina, Rahmann, Sven, Università degli studi di Trieste = University of Trieste, Centrum Wiskunde & Informatica (CWI), Delft University of Technology (TU Delft), Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), This paper received funding from the Netherlands Organisation for Scientific Research (NWO) under project OCENW.GROOT.2019.015 'Optimization for and with Machine Learning (OPTIMAL)'. Giulia Bernardini: MUR-FSE REACT EU – PON R&I 2014-2020 Leen Stougie: The Netherlands Organisation for Scientific Research (NWO) under Gravitation-grant NETWORKS-024.002.003, Bernardini, Giulia, van Iersel, Leo, Julien, Esther, Stougie, Leen, and Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands
Subjects: Machine Learning, Phylogenetics, Phylogenetic, Cherry Picking, Machine Learning, Heuristic, [SDV]Life Sciences [q-bio], Heuristic, Hybridization, Applied computing → Computational biology, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Cherry Picking
Abstract: Combining a set of phylogenetic trees into a single phylogenetic network that explains all of them is a fundamental challenge in evolutionary studies. In this paper, we apply the recently-introduced theoretical framework of cherry picking to design a class of heuristics that are guaranteed to produce a network containing each of the input trees, for practical-size datasets. The main contribution of this paper is the design and training of a machine learning model that captures essential information on the structure of the input trees and guides the algorithms towards better solutions. This is one of the first applications of machine learning to phylogenetic studies, and we show its promise with a proof-of-concept experimental study conducted on both simulated and real data consisting of binary trees with no missing taxa., LIPIcs, Vol. 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022), pages 16:1-16:22
Published: 2022
Full Text: View/download PDF

38. Polynomial Delay Algorithm for Minimal Chordal Completions

Author: Brosse, Caroline, Limouzy, Vincent, Mary, Arnaud, Université Clermont Auvergne (UCA), Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Algorithmic Enumeration, Graph Algorithm, Discrete Mathematics (cs.DM), Mathematics of computing → Enumeration, Mathematics of computing → Graph algorithms, Minimal chordal completions, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: Motivated by the problem of enumerating all tree decompositions of a graph, we consider in this article the problem of listing all the minimal chordal completions of a graph. In [Carmeli et al., 2020] (Pods 2017) Carmeli et al. proved that all minimal chordal completions or equivalently all proper tree decompositions of a graph can be listed in incremental polynomial time using exponential space. The total running time of their algorithm is quadratic in the number of solutions and the existence of an algorithm whose complexity depends only linearly on the number of solutions remained open. We close this question by providing a polynomial delay algorithm to solve this problem which, moreover, uses polynomial space. Our algorithm relies on Proximity Search, a framework recently introduced by Conte and Uno [Conte and Uno, 2019] (Stoc 2019) which has been shown powerful to obtain polynomial delay algorithms, but generally requires exponential space. In order to obtain a polynomial space algorithm for our problem, we introduce a new general method called canonical path reconstruction to design polynomial delay and polynomial space algorithms based on proximity search., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 33:1-33:16
Published: 2022
Full Text: View/download PDF

39. Succinct Representation for (Non)Deterministic Finite Automata

Author: Roberto Grossi, Kunihiko Sadakane, Srinivasa Rao Satti, Sankardeep Chakraborty, RIKEN Center for Advanced Intelligence Project [Tokyo] (RIKEN AIP), RIKEN - Institute of Physical and Chemical Research [Japon] (RIKEN), Dipartimento di Informatica, Università di Pisa, Italy (UNIPI), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), The University of Tokyo, Japan, Seoul National University [Seoul] (SNU), Dipartimento di Informatica [Pisa] (DI), University of Pisa - Università di Pisa, The University of Tokyo (UTokyo), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and Norwegian University of Science and Technology (NTNU)
Subjects: FOS: Computer and information sciences, 050101 languages & linguistics, History, General Computer Science, Discrete Mathematics (cs.DM), Polymers and Plastics, Computer Networks and Communications, Formal Languages and Automata Theory (cs.FL), Finite Automata, Computer Science - Formal Languages and Automata Theory, 02 engineering and technology, Industrial and Manufacturing Engineering, Theoretical Computer Science, Succinct data structure, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, 0501 psychology and cognitive sciences, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Nondeterministic finite automaton, Encoding Schemes, Business and International Management, Mathematics, Complement (set theory), Discrete mathematics, Applied Mathematics, 05 social sciences, String (computer science), Sigma, Succinct data structures Deterministic finite automata Encoding Time-space tradeoff, Binary logarithm, Deterministic finite automaton, phrases Succinct Data Structures, Computational Theory and Mathematics, Automata theory, 020201 artificial intelligence & image processing, Computer Science - Discrete Mathematics
Abstract: Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information-theoretically optimal number of bits along with supporting queries on them efficiently. Towards this goal, we first design a succinct data structure for representing any deterministic finite automaton $\mathcal{D}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $(\sigma-1) n\log n + O(n \log \sigma)$ bits of space, which can determine, given an input string $x$ over $\Sigma$, whether $\mathcal{D}$ accepts $x$ in $O(|x| \log \sigma)$ time, using constant words of working space. When the input deterministic finite automaton is acyclic, not only we can improve the above space-bound significantly to $(\sigma -1) (n-1)\log n+ 3n + O(\log^2 \sigma) + o(n)$ bits, we also obtain optimal query time for string acceptance checking. More specifically, using our succinct representation, we can check if a given input string $x$ can be accepted by the acyclic deterministic finite automaton using time proportional to the length of $x$, hence, the optimal query time. We also exhibit a succinct data structure for representing a non-deterministic finite automaton $\mathcal{N}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $\sigma n^2+n$ bits of space, such that given an input string $x$, we can decide whether $\mathcal{N}$ accepts $x$ efficiently in $O(n^2|x|)$ time. Finally, we also provide time and space-efficient algorithms for performing several standard operations such as union, intersection, and complement on the languages accepted by deterministic finite automata.
Published: 2022
Full Text: View/download PDF

40. phyBWT: Alignment-Free Phylogeny via eBWT Positional Clustering

Author: Guerrini, Veronica, Conte, Alessio, Grossi, Roberto, Liti, Gianni, Rosone, Giovanna, Tattini, Lorenzo, University of Pisa - Università di Pisa, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and CNRS UMR 7284, Inserm U 1081, Université Côte d'Azur
Subjects: positional cluster, BWT, Bioinformatics, [SDV]Life Sciences [q-bio], partition tree, assembly-free, [INFO]Computer Science [cs], Mathematics of computing → Combinatorial algorithms, alignment-free, reference-free, referencefree, Phylogeny, Applied computing → Bioinformatics
Abstract: Molecular phylogenetics is a fundamental branch of biology. It studies the evolutionary relationships among the individuals of a population through their biological sequences, and may provide insights about the origin and the evolution of viral diseases, or highlight complex evolutionary trajectories. In this paper we develop a method called phyBWT, describing how to use the extended Burrows-Wheeler Transform (eBWT) for a collection of DNA sequences to directly reconstruct phylogeny, bypassing the alignment against a reference genome or de novo assembly. Our phyBWT hinges on the combinatorial properties of the eBWT positional clustering framework. We employ eBWT to detect relevant blocks of the longest shared substrings of varying length (unlike the k-mer-based approaches that need to fix the length k a priori), and build a suitable decomposition leading to a phylogenetic tree, step by step. As a result, phyBWT is a new alignment-, assembly-, and reference-free method that builds a partition tree without relying on the pairwise comparison of sequences, thus avoiding to use a distance matrix to infer phylogeny. The preliminary experimental results on sequencing data show that our method can handle datasets of different types (short reads, contigs, or entire genomes), producing trees of quality comparable to that found in the benchmark phylogeny., LIPIcs, Vol. 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022), pages 23:1-23:19
Published: 2022
Full Text: View/download PDF

41. Applicability of several rooted phylogenetic network algorithms for representing the evolutionary history of SARS-CoV-2

Author: Wallin, Rosanne, van Iersel, Leo, Kelk, Steven, Stougie, Leen, Operations Analytics, Tinbergen Institute, Amsterdam Business Research Institute, Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands, Centrum Wiskunde & Informatica (CWI), Delft Institute of Applied Mathematics (DIAM), Delft University of Technology (TU Delft), Maastricht University [Maastricht], Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Data Science and Knowledge Engineering (DKE), Maastricht University, Dept. of Advanced Computing Sciences, RS: FSE DACS, and RS: FSE DACS Mathematics Centre Maastricht
Subjects: 0106 biological sciences, Evolution, [SDV]Life Sciences [q-bio], RECOMBINATION, 010603 evolutionary biology, 01 natural sciences, 03 medical and health sciences, SDG 3 - Good Health and Well-being, Reticulate evolution, QH359-425, Humans, TOOL, QH540-549.5, Phylogeny, 030304 developmental biology, Phylogenetic network, 0303 health sciences, Ecology, IDENTIFICATION, SARS-CoV-2, Research, COVID-19, General Medicine, Algorithm, Coronavirus, TREES, MOSAIC STRUCTURE, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Algorithms
Abstract: Background Rooted phylogenetic networks are used to display complex evolutionary history involving so-called reticulation events, such as genetic recombination. Various methods have been developed to construct such networks, using for example a multiple sequence alignment or multiple phylogenetic trees as input data. Coronaviruses are known to recombine frequently, but rooted phylogenetic networks have not yet been used extensively to describe their evolutionary history. Here, we created a workflow to compare the evolutionary history of SARS-CoV-2 with other SARS-like viruses using several rooted phylogenetic network inference algorithms. This workflow includes filtering noise from sets of phylogenetic trees by contracting edges based on branch length and bootstrap support, followed by resolution of multifurcations. We explored the running times of the network inference algorithms, the impact of filtering on the properties of the produced networks, and attempted to derive biological insights regarding the evolution of SARS-CoV-2 from them. Results The network inference algorithms are capable of constructing rooted phylogenetic networks for coronavirus data, although running-time limitations require restricting such datasets to a relatively small number of taxa. Filtering generally reduces the number of reticulations in the produced networks and increases their temporal consistency. Taxon bat-SL-CoVZC45 emerges as a major and structural source of discordance in the dataset. The tested algorithms often indicate that SARS-CoV-2/RaTG13 is a tree-like clade, with possibly some reticulate activity further back in their history. A smaller number of constructed networks posit SARS-CoV-2 as a possible recombinant, although this might be a methodological artefact arising from the interaction of bat-SL-CoVZC45 discordance and the optimization criteria used. Conclusion Our results demonstrate that as part of a wider workflow and with careful attention paid to running time, rooted phylogenetic network algorithms are capable of producing plausible networks from coronavirus data. These networks partly corroborate existing theories about SARS-CoV-2, and partly produce new avenues for exploration regarding the location and significance of reticulate activity within the wider group of SARS-like viruses. Our workflow may serve as a model for pipelines in which phylogenetic network algorithms can be used to analyse different datasets and test different hypotheses.
Published: 2021
Full Text: View/download PDF

42. CALDERA: Finding all significant de Bruijn subgraphs for bacterial GWAS

Author: Laurent Jacob, Fanny Perraudeau, Leandro Lima, Sandrine Dudoit, Hector Roux de Bézieux, Arnaud Mary, Pendulum Therapeutics [San Francisco], European Bioinformatics Institute [Hinxton] (EMBL-EBI), EMBL Heidelberg, Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of California [Berkeley], University of California, Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), University of California [Berkeley] (UC Berkeley), University of California (UC), and ANR-17-CE23-0011,FAST-BIG,Tests Statistiques efficaces pour les données de grande dimension: application à l'imagerie cérébrale et la génétique(2017)
Subjects: Statistics and Probability, Theoretical computer science, Computer science, Bioinformatics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Genome-wide association study, 0102 computer and information sciences, Biochemistry, 01 natural sciences, De Bruijn graph, Mathematical Sciences, 03 medical and health sciences, symbols.namesake, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Information and Computing Sciences, Genetics, Pruning (decision trees), Molecular Biology, Testability, 030304 developmental biology, Interpretability, De Bruijn sequence, 0303 health sciences, Bacteria, Human Genome, Sequence Analysis, DNA, DNA, Biological Sciences, [SDV.MP.BAC]Life Sciences [q-bio]/Microbiology and Parasitology/Bacteriology, Computer Science Applications, Computational Mathematics, Computational Theory and Mathematics, 010201 computation theory & mathematics, Multiple comparisons problem, symbols, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Sequence Analysis, Algorithms, Software, Reference genome, Genome-Wide Association Study, Biotechnology
Abstract: Genome wide association studies (GWAS), aiming to find genetic variants associated with a trait, have widely been used on bacteria to identify genetic determinants of drug resistance or hypervirulence. Recent bacterial GWAS methods usually rely on k-mers, whose presence in a genome can denote variants ranging from single nucleotide polymorphisms to mobile genetic elements. Since many bacterial species include genes that are not shared among all strains, this approach avoids the reliance on a common reference genome. However, the same gene can exist in slightly different versions across different strains, leading to diluted effects when trying to detect its association to a phenotype through k-mer based GWAS. Here we propose to overcome this by testing covariates built from closed connected subgraphs of the De Bruijn graph defined over genomic k-mers. These covariates are able to capture polymorphic genes as a single entity, improving k-mer based GWAS in terms of power and interpretability. As the number of subgraphs is exponential in the number of nodes in the DBG, a method naively testing all possible subgraphs would result in very low statistical power due to multiple testing corrections, and the mere exploration of these subgraphs would quickly become computationally intractable. The concept of testable hypothesis has successfully been used to address both problems in similar contexts. We leverage this concept to test all closed connected subgraphs by proposing a novel enumeration scheme for these objects which fully exploits the pruning opportunity offered by testability, resulting in drastic improvements in computational efficiency. We illustrate this on both real and simulated datasets and also demonstrate how considering subgraphs leads to a more powerful and interpretable method. Our method integrates with existing visual tools to facilitate interpretation. We also provide an implementation of our method, as well as code to reproduce all results at https://github.com/HectorRDB/Caldera_Recomb.
Published: 2021
Full Text: View/download PDF

43. Within-host genetic micro-diversity of Mycobacterium tuberculosis and the link with tuberculosis disease features

Author: Oana Dumitrescu, Stéphane Dray, Emilie Westeel, Jean-Luc Berland, Alexia Barbry, Gerard Lina, Laurent Jacob, Elisabeth Hodille, Samuel Venner, Charlotte Genestet, Florence Ader, François Massol, Guislaine Refrégier, Centre International de Recherche en Infectiologie (CIRI), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Université Jean Monnet - Saint-Étienne (UJM)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Bactériologie de l'Hôpital de la Croix-Rousse, Hospices Civils de Lyon (HCL), Évolution, Écologie et Paléontologie (Evo-Eco-Paleo) - UMR 8198 (Evo-Eco-Paléo (EEP)), Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre d’Infection et d’Immunité de Lille - INSERM U 1019 - UMR 9017 - UMR 8204 (CIIL), Institut Pasteur de Lille, Réseau International des Instituts Pasteur (RIIP)-Réseau International des Instituts Pasteur (RIIP)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Centre National de la Recherche Scientifique (CNRS), Institut de Biologie Intégrative de la Cellule (I2BC), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Ecologie Systématique et Evolution (ESE), AgroParisTech-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Fondation Mérieux, Service des Maladies Infectieuses et Tropicales [Lyon], Hôpital de la Croix-Rousse [CHU - HCL], Hospices Civils de Lyon (HCL)-Hospices Civils de Lyon (HCL), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Département PEGASE [LBBE] (PEGASE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Baobab, Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre International de Recherche en Infectiologie - UMR (CIRI), Institut National de la Santé et de la Recherche Médicale (INSERM)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Évolution, Écologie et Paléontologie (Evo-Eco-Paleo) - UMR 8198 (Evo-Eco-Paléo), Centre National de la Recherche Scientifique (CNRS)-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut Pasteur de Lille, Réseau International des Instituts Pasteur (RIIP)-Réseau International des Instituts Pasteur (RIIP), and Institute for Integrative Biology of the Cell [Gif-sur-Yvette] (I2BC)
Subjects: 0303 health sciences, Tuberculosis, biology, 030306 microbiology, Severity symptoms, business.industry, Host (biology), media_common.quotation_subject, respiratory system, medicine.disease, biology.organism_classification, [SDV.MP.BAC]Life Sciences [q-bio]/Microbiology and Parasitology/Bacteriology, 3. Good health, Contagious disease, Mycobacterium tuberculosis, 03 medical and health sciences, Immunology, Medicine, Tuberculosis Disease, business, 030304 developmental biology, Diversity (politics), media_common
Abstract: Tuberculosis (TB), caused by Mycobacterium tuberculosis (Mtb) complex, is still the number one deadly contagious disease. Mtb infection results in a wide spectrum of clinical presentations and severity symptoms, but without proven Mtb genetic determinants. Thanks to a collection of 355 clinical isolates with associated patient’s clinical data, we showed that Mtb micro-diversity within patient isolates is strongly correlated with TB-associated severity scores. Interestingly, this diversity is driven by a selection pressure to adapt to different lifestyles related to the infection site. Taken together, these results provide a new insight to better understand TB pathophysiology. Furthermore, Mtb micro-diversity could be envisioned as a new prognostic tool to improve the management of TB patients.
Published: 2021

44. Efficiently sparse listing of classes of optimal cophylogeny reconciliations

Author: Marie-France Sagot, Yishu Wang, Blerina Sinaimeri, Arnaud Mary, Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS)
Subjects: Cophylogeny, Dynamic programming, Enumeration, Equivalence relation, Information retrieval, Computer science, Enumeration, Cophylogeny, Applied Mathematics, Listing (computer), [SDV.BID.SPT]Life Sciences [q-bio]/Biodiversity/Systematics, Phylogenetics and taxonomy, Dynamic programming, Computational Theory and Mathematics, Structural Biology, Equivalence relation, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Molecular Biology
Abstract: Background Cophylogeny reconciliation is a powerful method for analyzing host-parasite (or host-symbiont) co-evolution. It models co-evolution as an optimization problem where the set of all optimal solutions may represent different biological scenarios which thus need to be analyzed separately. Despite the significant research done in the area, few approaches have addressed the problem of helping the biologist deal with the often huge space of optimal solutions. Results In this paper, we propose a new approach to tackle this problem. We introduce three different criteria under which two solutions may be considered biologically equivalent, and then we propose polynomial-delay algorithms that enumerate only one representative per equivalence class (without listing all the solutions). Conclusions Our results are of both theoretical and practical importance. Indeed, as shown by the experiments, we are able to significantly reduce the space of optimal solutions while still maintaining important biological information about the whole space.
Published: 2021
Full Text: View/download PDF

45. The transposable element-rich genome of the cereal pest Sitophilus oryzae

Author: Arian F.A. Smit, Séverine Balmand, Stefano Colella, Nicolas Montagné, Amparo Latorre, Jessica M. Storer, Nelly Burlet, Jeb Rosen, Caroline Blanc, Federica Calevro, Marina Marcet-Houben, Marie-France Sagot, Patrick Callaerts, Waël Zamoum, Patrice Baa-Puyoulet, Anna Zaidman-Rémy, Clément Goubert, Rita Rebollo, Louis Beranger, Carlos Vargas-Chávez, Gautier Richard, Ana Tereza Ribeiro de Vasconcelos, Justin Maire, Agnès Vallier, Elisa Dell’Aglio, Florent Masson, Robert Hubley, Sandrine Hughes, Camille Meslin, Gérard Febvay, Aurélien Vigneron, Nicolas Parisot, Théo Chancy, Cristina Vieira, Abdelaziz Heddi, Alex Di Genova, Benjamin Gillet, André Da Silva Barbosa, Carole Vincent-Monégat, Emmanuelle Jacquin-Joly, Hubert Charles, Mariana Galvão Ferrarini, Matthieu Boulesteix, Toni Gabaldón, Alexandra L. Gerber, Andrés Moya, Aymeric Bonnamour, Biologie Fonctionnelle, Insectes et Interactions (BF2I), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Laboratorio Nacional de Computação Cientifica [Rio de Janeiro] (LNCC / MCT), Institut de Génomique Fonctionnelle de Lyon (IGFL), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Institute for Systems Biology [Seattle] (ISB), Barcelona Supercomputing Center - Centro Nacional de Supercomputacion (BSC - CNS), Fundación para el Fomento de la Investigación Sanitaria y Biomédica de la Comunitat Valenciana [Espagne] (FISABIO), Institut de Génétique, Environnement et Protection des Plantes (IGEPP), Université de Rennes (UR)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Eléments transposables, évolution, populations, Département génétique, interactions et évolution des génomes [LBBE] (GINSENG), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Institut d'écologie et des sciences de l'environnement de Paris (iEES Paris ), Institut de Recherche pour le Développement (IRD)-Sorbonne Université (SU)-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Rennes (UR)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Institut Agro Rennes Angers, Institut National de Recherche pour l'Agriculture, l'Alimentation et l'Environnement, Région Auvergne-Rhône-Alpes, European Regional Development Fund, PGC2018-099344-B-I00, Ministerio de Ciencia, Innovación y Universidades, PROMETEO/2018/133, Conselleria d’Educació, Generalitat Valenciana, Institut National des Sciences Appliquées de Lyon, ANR-10-BLAN-1701, Agence Nationale de la Recherche, IDEX-Lyon PALSE IMPULSION, Ministerio de Economía y Competitividad, ANR-17-CE20-0031,GREEN,Comprendre les mécanismes de régulation et la fonction des gènes de la réponse immunitaire de l'hôte pour perturber la symbiose et le contrôle des endosymbiotes chez les insectes nuisibles(2017), ANR-17-CE20-0015,Unleash,Découverte de la relation entre épigénétique et symbiose chez l'insecte(2017), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Barcelona Supercomputing Center, Agence Nationale de la Recherche (France), European Commission, Agencia Estatal de Investigación (España), Ministerio de Ciencia, Innovación y Universidades (España), Generalitat Valenciana, and Ministerio de Economía y Competitividad (España)
Subjects: Life Sciences & Biomedicine - Other Topics, Weevil, ALPHA-AMYLASE INHIBITORS, Physiology, Cell Communication, Plant Science, drosophila immune-response, Genome, HORIZONTAL GENE-TRANSFER, MULTIPLE SEQUENCE ALIGNMENT, 0302 clinical medicine, Structural Biology, Biology (General), Sitophilus oryzae Genome, 2. Zero hunger, Genetics, 0303 health sciences, Endosymbiosis Immunity, biology, Endosymbiosis, horizontal gene-transfer, Sitophilus, Sitophilus oryzae, food and beverages, wide analysis, Coleoptera, RED FLOUR BEETLE, Horizontal gene transfer, multiple sequence alignment, Agricultural pests, stored-product insects, phosphine resistance, General Agricultural and Biological Sciences, Life Sciences & Biomedicine, Research Article, DIGESTIVE PROTEINASES, Biotechnology, Informàtica::Aplicacions de la informàtica::Bioinformàtica [Àrees temàtiques de la UPC], Transposable element, Sodalis, food.ingredient, QH301-705.5, PRIMARY ENDOSYMBIONT, Evolution, alpha-amylase inhibitors, General Biochemistry, Genetics and Molecular Biology, 03 medical and health sciences, Rice weevil, food, STORED-PRODUCT INSECTS, [SDV.BBM.GTP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN], PHOSPHINE RESISTANCE, Animals, Humans, DROSOPHILA IMMUNE-RESPONSE, Red flour beetle, Biology, Ecology, Evolution, Behavior and Systematics, 030304 developmental biology, [SDV.GEN.GPO]Life Sciences [q-bio]/Genetics/Populations and Evolution [q-bio.PE], Science & Technology, Immunity, Cell Biology, primary endosymbiont, biology.organism_classification, digestive proteinases, Genòmica, [SDV.GEN.GA]Life Sciences [q-bio]/Genetics/Animal genetics, red flour beetle, DNA Transposable Elements, Weevils, Edible Grain, WIDE ANALYSIS, Transposable elements, 030217 neurology & neurosurgery, [SDV.EE.IEO]Life Sciences [q-bio]/Ecology, environment/Symbiosis, Developmental Biology
Abstract: Parisot et al., [Background]: The rice weevil Sitophilus oryzae is one of the most important agricultural pests, causing extensive damage to cereal in fields and to stored grains. S. oryzae has an intracellular symbiotic relationship (endosymbiosis) with the Gram-negative bacterium Sodalis pierantonius and is a valuable model to decipher host-symbiont molecular interactions., [Results]: We sequenced the Sitophilus oryzae genome using a combination of short and long reads to produce the best assembly for a Curculionidae species to date. We show that S. oryzae has undergone successive bursts of transposable element (TE) amplification, representing 72% of the genome. In addition, we show that many TE families are transcriptionally active, and changes in their expression are associated with insect endosymbiotic state. S. oryzae has undergone a high gene expansion rate, when compared to other beetles. Reconstruction of host-symbiont metabolic networks revealed that, despite its recent association with cereal weevils (30 kyear), S. pierantonius relies on the host for several amino acids and nucleotides to survive and to produce vitamins and essential amino acids required for insect development and cuticle biosynthesis., [Conclusions]: Here we present the genome of an agricultural pest beetle, which may act as a foundation for pest control. In addition, S. oryzae may be a useful model for endosymbiosis, and studying TE evolution and regulation, along with the impact of TEs on eukaryotic genomes., Funding for this project was provided by the Fondation de l’Institut National des Sciences Appliquées-Lyon (INSA-Lyon), the research direction of INSA-Lyon, the Santé des Plantes et Environnement (SPE) department at the Institut National de Recherche pour l'Agriculture, l'Alimentation et l'Environnement (INRAE), the French ANR-10-BLAN-1701 (ImmunSymbArt), the French ANR-13-BSV7-0016-01 (IMetSym), the French ANR-17_CE20_0031_01 (GREEN), and a grant from la Région Rhône-Alpes (France) to AH. RR received funding from the French ANR-17-CE20-0015 (UNLEASH) and the IDEX-Lyon PALSE IMPULSION initiative. The project was also funded by European Regional Development Fund (ERDF) and Ministerio de Ciencia, Innovación y Universidades (Spain) PGC2018-099344-B-I00 to AL, and PID2019-105969GB-I00 to AM and Conselleria d’Educació, Generalitat Valenciana (Spain), grant number PROMETEO/2018/133 to AM. CV-C was a recipient of a fellowship from the Ministerio de Economía y Competitividad (Spain) and a grant from la Région Rhône-Alpes (France).
Published: 2021
Full Text: View/download PDF

46. Molecular profile to guide personalized medicine in adult patients with primary brain tumors: results from the ProfiLER trial

Author: V. Corset, Sandrine Paindavoine, David Meyronet, Marie Blonski, Emilie Lavergne, Sylvie Chabaud, Valéry Attignon, Jean-Yves Blay, Luc Taillandier, Sylvie Lantuejoul, François Ducray, Olivier Tredan, Didier Frappaz, Emilie Sohier, Christian Baudet, V. Agrapart, David Pérol, Christine Rodriguez, Daniel Pissaloux, Alice Bonneville-Levard, Qing Wang, Isabelle Treilleux, Alain Viari, Laure Thomas-Maisonneuve, Jérôme Honnorat, Stéphanie Cartalat, Centre Léon Bérard [Lyon], Hospices Civils de Lyon (HCL), Centre Hospitalier Régional Universitaire de Nancy (CHRU Nancy), Synergie Lyon Cancer-Platform of Bioinformatics-Gilles Thomas, Centre de Recherche en Cancérologie de Lyon (UNICANCER/CRCL), Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Adult, Male, Sorafenib, Oncology, Cancer Research, medicine.medical_specialty, [SDV]Life Sciences [q-bio], Clinical Decision-Making, Brain tumor, PDGFRA, Primary brain tumor, Primary brain tumor Molecular profiling Precision medicine Targeted therapy Decision-making, Targeted therapy, Molecular profiling, Young Adult, CDKN2A, Internal medicine, Glioma, Biomarkers, Tumor, medicine, Humans, Prospective Studies, Precision Medicine, Aged, Comparative Genomic Hybridization, Everolimus, Brain Neoplasms, business.industry, Genomics, Hematology, General Medicine, Middle Aged, medicine.disease, Clinical trial, Female, Erlotinib, business, Decision-making, medicine.drug
Abstract: International audience; Immunohistochemistry and recent molecular technologies progressively guided access to personalized anti-tumoral therapies. We explored the feasibility, efficacy, and the impact of molecular profiling in patients with advanced brain tumors. This multicentric prospective trial ProfiLER enrolled patients with primary brain tumors, who have been pre-treated with at least one line of anti-cancer treatment, and for whom molecular profiles had been achieved using next-generation sequencing and/or comparative genomic hybridization on fresh or archived samples from tumor, relapse, or biopsies. A molecular tumor board weekly analyzed results and proposed molecular-based recommended therapy (MBRT). From February 2013 to December 2015, we enrolled 141 patients with primary brain tumor and analyzed 105 patients for whom tumor genomic profiles had been achieved. Histology mainly identified glioblastoma (N = 46, 44%), low-grade glioma (N = 26, 25%), highgrade glioma (N = 12, 11%), and atypical and anaplastic meningioma (N = 8, 8%). Forty-three (41%) patients presented at least one actionable molecular alteration. Out of 61 alterations identified, the most frequent alterations occurred in CDKN2A (N = 18), EGFR (N = 12), PDGFRa (N = 8), PTEN (N = 8), CDK4 (N = 7), KIT (N = 6), PIK3CA (N = 5), and MDM2 (N = 3). Sixteen (15%) patients could not be proposed for a MBRT due to early death (N = 5), lack of available clinical trials (N = 9), or inappropriate results (N = 2). Only six (6%) of the 27 (26%) patients for whom a MBRT had been proposed finally initiated MBRT (everolimus (N = 3), erlotinib (N = 1), ruxolitinib (N = 1), and sorafenib (N = 1)), but discontinued treatment for toxicity (N = 4) or clinical progression (N = 2). High-throughput sequencing in patients with brain tumors may be routinely performed, especially when macroscopic surgery samples are available; nevertheless delays should be reduced. Criteria for clinical trial enrollment should be reconsidered in patients with brain tumors, and a panel of genes specifically dedicated to neurologic tumors should be developed to help decision-making in clinical practice.
Published: 2021
Full Text: View/download PDF

47. Identification of driver genes for critical forms of COVID-19 in a deeply phenotyped young patient cohort

Author: Qian Zhang, Paul Bastard, Haiguo Wu, Adrian Gervais, Seiamak Bahram, Sylvain Mayeur, Sharvari Gujja, Anne Thomas, Alexandre Lederle, Julie Helms, Christiane Moog, Xavier Mariette, Alain Viari, Tristan Stemmelen, Christine Carapito, Olivier Hermine, Richard Li, Daniel A. Lidar, Cécile Macquin, Jean Sibilia, Géraldine Laumond, Shweta Kailasan, Leslie Muller, Sabrina Bibi-Triki, Sylvie Schmidt, Aurélie Hirschler, Raony Guimaraes, Michael Simons, Anne Molitor, Francis Schneider, Damien Sanlaville, Thiên-Nga Chamaraux-Tran, Samira Fafi-Kremer, Pierre-Louis Tharaux, Thomas Chittenden, Angélique Pichot, A. Hanauer, Raphael Carapito, Mirjana Radosavljevic, Véronique Rolli, Bernard Goichot, Yvon Ruch, Olivier Collange, Ouria Tahar, Julien Pottecher, Khaldoun Kuteifan, Razieh Mohseninia, Perrine Spinnhirny, Alice Bernard, Bernard Drenou, Jean-Laurent Casanova, Elisa Pin, Jeffrey R. Gulcher, Paul-Michel Mertes, M. Javad Aman, Peter Nilsson, Jose Malagon-Lopez, François Danion, Yves Hansmann, Ferhat Meziani, Maleka Schenck, Nicodème Paul, Annabel Larnicol, Julia Frappier, Immuno-Rhumatologie Moléculaire, Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM), GENOMAX [plateforme], Fédération Hospitalo-Universitaire OMICARE, Université de Strasbourg (UNISTRA), Nouvel Hôpital Civil de Strasbourg, Fédération de Médecine Translationnelle de Strasbourg (FMTS), Genuity Science [Boston], Département Sciences Analytiques et Interactions Ioniques et Biomoléculaires (DSA-IPHC), Institut Pluridisciplinaire Hubert Curien (IPHC), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), University of Southern California (USC), Rockefeller University [New York], CHU Necker - Enfants Malades [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP), Imagine - Institut des maladies génétiques (IHU) (Imagine - U1163), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Paris Cité (UPCité), Les Hôpitaux Universitaires de Strasbourg (HUS), Hôpital de Hautepierre [Strasbourg], Yale School of Medicine [New Haven, Connecticut] (YSM), Hôpital Bicêtre, Immunologie des maladies virales, auto-immunes, hématologiques et bactériennes (IMVA-HB), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Paris-Saclay, Centre de Recherche Épidémiologie et Statistique Sorbonne Paris Cité (CRESS (U1153 / UMR_A_1125 / UMR_S_1153)), Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Université Sorbonne Paris Cité (USPC)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Paris Cité (UPCité)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Groupe hospitalier de la région de Mulhouse et Sud-Alsace, Integrated biotherapeutics [Rockville], Royal Institute of Technology [Stockholm] (KTH ), Auragen [Lyon], Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Synergie Lyon Cancer-Platform of Bioinformatics-Gilles Thomas, Centre de Recherche en Cancérologie de Lyon (UNICANCER/CRCL), Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Centre Léon Bérard [Lyon]-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Paris-Centre de Recherche Cardiovasculaire (PARCC (UMR_S 970/ U970)), Hôpital Européen Georges Pompidou [APHP] (HEGP), Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Hôpitaux Universitaires Paris Ouest - Hôpitaux Universitaires Île de France Ouest (HUPO)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Hôpitaux Universitaires Paris Ouest - Hôpitaux Universitaires Île de France Ouest (HUPO)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Paris Cité (UPCité), Harvard Medical School [Boston] (HMS), ANR-10-IDEX-0002,UNISTRA,Par-delà les frontières, l'Université de Strasbourg(2010), ANR-20-SFRI-0012,STRAT'US,Façonner les talents en formation et en recherche à l'Université de Strasbourg(2020), ANR-10-INBS-0008,ProFI,Infrastructure Française de Protéomique(2010), CARAPITO, Christine, Université de Strasbourg (UNISTRA)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), LabEx Transplantex [Strasbourg], Fédération Hospitalo-Universitaire (OMICARE), Centre de Recherche d’Immunologie et d’Hématologie [Strasbourg], Laboratoire de Spectrométrie de Masse BioOrganique [Strasbourg] (LSMBO), Université de Strasbourg (UNISTRA)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS)-Institut Pluridisciplinaire Hubert Curien (IPHC), Université de Strasbourg (UNISTRA)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), Département Ecologie, Physiologie et Ethologie (DEPE-IPHC), Génétique Humaine des Maladies Infectieuses (Inserm U980), Université Paris Descartes - Paris 5 (UPD5)-Institut National de la Santé et de la Recherche Médicale (INSERM), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Paris (UP), Yale University School of Medicine, Immunologie des Maladies Virales et Autoimmunes (IMVA - U1184), Université Paris-Sud - Paris 11 (UP11)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Université Sorbonne Paris Cité (USPC)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Paris (UP)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Hôpitaux Universitaires Paris Ouest - Hôpitaux Universitaires Île de France Ouest (HUPO)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Hôpitaux Universitaires Paris Ouest - Hôpitaux Universitaires Île de France Ouest (HUPO)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Paris (UP), Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Institut Pluridisciplinaire Hubert Curien (IPHC), Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), and Université Paris-Sud - Paris 11 (UP11)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut National de la Santé et de la Recherche Médicale (INSERM)
Subjects: 2019-20 coronavirus outbreak, Coronavirus disease 2019 (COVID-19), Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2), Aucun, MEDLINE, Bioinformatics, 03 medical and health sciences, 0302 clinical medicine, Artificial Intelligence, [SDV.BBM.GTP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN], Medicine, Humans, Gene, ComputingMilieux_MISCELLANEOUS, 030304 developmental biology, 0303 health sciences, business.industry, SARS-CoV-2, Confounding, COVID-19, Membrane Proteins, General Medicine, Respiration, Artificial, 3. Good health, ADAM Proteins, Intensive Care Units, 030220 oncology & carcinogenesis, Cohort, [SDV.BBM.GTP] Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN], Identification (biology), business
Abstract: International audience; The etiopathogenesis of critical COVID-19 remains unknown. Indeed given major confounding factors (age and comorbidities), true drivers of this condition have remained elusive. Here, we employ an unprecedented multi-omics analysis, combined with artificial intelligence, in a young patient cohort where major comorbidities have been excluded at the onset. Here, we established a three-tier cohort of individuals younger than 50 years without major comorbidities. These included 47 “critical” (in the ICU under mechanical ventilation) and 25 “non-critical” (in a non-critical care ward) COVID-19 patients as well as 22 healthy individuals. The analyses included whole-genome sequencing, whole-blood RNA sequencing, plasma and blood mononuclear cells proteomics, cytokine profiling and high-throughput immunophenotyping. An ensemble of machine learning, deep learning, quantum annealing and structural causal modeling led to key findings. Critical patients were characterized by exacerbated inflammation, perturbed lymphoid/myeloid compartments, coagulation and viral cell biology. Within a unique gene signature that differentiated critical from non-critical patients, several driver genes promoted critical COVID-19 among which the upregulated metalloprotease ADAM9 was key. This gene signature was supported in a second independent cohort of 81 critical and 73 recovered COVID-19 patients, as were ADAM9 transcripts, soluble form and proteolytic activity. Ex vivo ADAM9 inhibition affected SARS-CoV-2 uptake and replication in human lung epithelial cells. In conclusion, within a young, otherwise healthy, COVID-19 cohort, we provide the landscape of biological perturbations in vivo where a unique gene signature differentiated critical from non-critical patients. The key driver, ADAM9, interfered with SARS-CoV-2 biology. A repositioning strategy for anti-ADAM9 therapeutic is feasible.
Published: 2021
Full Text: View/download PDF

48. Développement de méthodes bio-informatiques pour l’étude de l’épissage chez les espèces non modèles : Épissage complexe et apport des technologies de séquençage de 3eme génération

Author: Sessegolo, Camille, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558, Univ Lyon, Université Claude-Bernard Lyon 1, Vincent Lacroix, and Arnaud Mary
Subjects: non-model species, espèce non modèle, bioinformatic, long reads, transcriptomique, lectures longues, transcriptomic, RNAseq, Épissage alternatif, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], bioinformatique, Alternative splicing
Abstract: Eukaryotic genes are composed of exons and introns. Introns are spliced out during the maturation of pre-mRNA to mRNA. Splice site usage may vary from one transcript to another for a same gene. Alternative splicing is a source of diversity in eucaryotic transcriptomes and one gene can sometimes lead to several proteins. We can study alternative splicing using RNAseq data. Nowadays second (2GS) and third generation sequencing (3GS) technologies coexist. 2GS produce short (from 100 to 250 pb) high quality reads whereas 3GS produce long reads (up to several kilobases) but with a lot of errors. In the first part of my PhD, I analysed Nanopore long reads datasets to understand how this technology can help us to study eucaryotic transcriptomes. Particularly, I wondered if transcripts and genes quantifications obtained with Nanopore data were reliable. We used Spike-in (artificial transcripts from which we know the real quantification) and we showed that the most precise quantifications were obtained with the RNA direct protocol. Furthermore, we observed that only a fraction of the long reads covered full length transcripts. Then, I worked on a new model for complex alternative splicing events in non-model species. KisSplice, the local RNAseq assembler developped in the team, always considers parwise event even when there are more than two transcripts locally. I propose here a new scale to study alternative splicing : we consider all the splicing variations observed between two constitutive exons of a gene.; Les gènes des organismes eucaryotes sont structurés en exons et en introns. Lors de l'épissage, les introns sont retirés et les exons reliés entre eux. L'utilisation des sites d'épissage par la machinerie cellulaire peut varier d'un transcrit à l'autre pour un même gène. L'épissage alternatif permet alors à un seul gène de produire plusieurs transcrits et parfois plusieurs protéines. L'étude des données issues du séquençage des transcrits (RNAseq) nous permet d'étudier l'épissage. Actuellement deux technologies de séquençage coexistent : les technologies de seconde génération, permettant de produire des lectures courtes (100 à 250pb) avec un taux d'erreur faible et les technologies de 3ème génération permettant de produire des lectures longues (plusieurs kb) avec des taux d'erreur plus élevés. Dans un premier temps, j'ai analysé des jeux de données Nanopore (lectures longues) afin de comprendre comment ces technologies, récentes et en constante évolution, peuvent nous aider à étudier les transcriptomes eucaryotes. Plus particulièrement, je me suis demandée si les quantifications des gènes et des transcrits obtenues étaient fiables. L'utilisation de spike-in -transcrits artificiels dont on connaît la quantification- nous a permis de montrer que, parmi les différents protocoles testés, les quantifications obtenues avec le protocole RNA direct sont les plus fiables. De plus, contrairement à ce à quoi l'on s'attendait, les lectures ne couvrent pas systématiquement des transcrits complets. Ensuite, je me suis intéressée à la modélisation des évènements d'épissage alternatif complexes chez les espèces non modèles. L'assembleur local de transcriptome, KisSplice, développé dans l'équipe, compare deux à deux les transcrits, même lorsqu'il y a plus de deux transcrits localement. Je propose ici une nouvelle échelle d'étude de l'épissage qui permet de considérer toutes les variations d'épissages observées entre deux exons constitutifs à tous les transcrits d'un gène.
Published: 2021

49. Algorithmic investigations of the dynamics of species interactions

Author: Wang, Yishu, Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558, Univ Lyon, Université Claude-Bernard Lyon 1, Marie-France Sagot, Mário Figueiredo, and Blerina Sinaimeri
Subjects: Cophylogénie, Cophylogeny, Equivalence relation, [SDV]Life Sciences [q-bio], [INFO]Computer Science [cs], Algorithmes d'énumération, Relation d'équivalence, Enumeration algorithms, Dynamic programming, Programmation dynamique
Abstract: To understand the dynamics of interaction between groups of species, for example, in a hosts/parasites (or hosts/symbionts) system, it is essential to consider the process of coevolution. The cophylogeny reconciliation model formulates the coevolution question as an optimization problem. The set of optimal solutions represents different scenarios of coevolution which need to be analyzed separately. The main result of this thesis is a novel approach that addresses the issue of the often huge number of optimal solutions which makes it difficult to analyze the results. We introduce several biologically motivated equivalence relations, each one splitting the solution space into equivalence classes. We propose polynomial-delay algorithms that enumerate the equivalence classes, and the representative solutions, i.e., the solutions taken from each equivalence class. Experimental results are then presented to illustrate the practical benefits of considering equivalence classes as a means of efficiently exploring the solution space of cophylogeny reconciliation. Based on the algorithmic results, a software called Capybara has been developed as a practical tool for analyzing cophylogeny datasets. More generally, in the area of enumeration algorithms, the problem of efficiently enumerating representative solutions is of theoretical importance. In the second part of this thesis, we provide a general framework for the enumeration of the equivalence classes of solutions for a family of optimization problems. We show that this framework can be applied to various dynamic programming problems, of which the cophylogeny problem is a special case.; Pour comprendre la dynamique d'interactions entre des groupes d'espèces, par exemple, dans un contexte hôtes-parasites, il est primordial d'étudier le processus de coévolution. La réconciliation cophylogénétique est un modèle qui traduit la reconstruction de l'histoire coévolutive en un problème d'optimisation combinatoire. L'ensemble des solutions optimales, qui représentent des scénarios coévolutifs différents, peut avoir une taille considérable, rendant l'analyse des résultats difficile. Le résultat principal de cette thèse porte sur une nouvelle méthode qui permet d'explorer l'espace de solutions de manière efficace. D'abord, je définis des relations d'équivalence et propose des algorithmes d'énumération qui produisent la liste des solutions représentatives, c'est-à-dire des solutions appartenant à chacune des classes d'équivalence. Ensuite, je présente des résultats expérimentaux et montre que l'analyse des classes d'équivalence aide à mieux étudier des jeux de données biologiques. Basé sur nos résultats algorithmiques, un logiciel appelé Capybara a été développé comme un nouvel outil pratique pour l'analyse cophylogénétique. Plus généralement, l'énumération des classes d'équivalence des solutions est un problème théorique important. Dans la seconde partie de la thèse, je présente un cadre général au sein duquel l'énumération efficace des classes d'équivalence est possible. Je propose un algorithme qui énumère les classes d'équivalence des solutions pour une famille de problèmes, en particulier, des problèmes où s'applique la technique de programmation dynamique.
Published: 2021

50. Investigations algorithmiques des interactions inter-espèces

Author: Wang, Yishu, Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Marie-France Sagot, Mario Figueiredo, Blerina Sinaimeri, ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558, Univ Lyon, Université Claude-Bernard Lyon 1, and Mário Figueiredo
Subjects: Cophylogénie, [SDV]Life Sciences [q-bio], Cophylogeny, Equivalence relation, [INFO]Computer Science [cs], Algorithmes d'énumération, Relation d'équivalence, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Enumeration algorithms, Dynamic programming, Algorithmes d’énumération, Relation d’équivalence, Programmation dynamique
Abstract: To understand the dynamics of interaction between groups of species, for example, in a hosts/parasites (or hosts/symbionts) system, it is essential to consider the process of coevolution. The cophylogeny reconciliation model formulates the coevolution question as an optimization problem. The set of optimal solutions represents different scenarios of coevolution which need to be analyzed separately. The main result of this thesis is a novel approach that addresses the issue of the often huge number of optimal solutions which makes it difficult to analyze the results. We introduce several biologically motivated equivalence relations, each one splitting the solution space into equivalence classes. We propose polynomial-delay algorithms that enumerate the equivalence classes, and the representative solutions, i.e., the solutions taken from each equivalence class. Experimental results are then presented to illustrate the practical benefits of considering equivalence classes as a means of efficiently exploring the solution space of cophylogeny reconciliation. Based on the algorithmic results, a software called Capybara has been developed as a practical tool for analyzing cophylogeny datasets. More generally, in the area of enumeration algorithms, the problem of efficiently enumerating representative solutions is of theoretical importance. In the second part of this thesis, we provide a general framework for the enumeration of the equivalence classes of solutions for a family of optimization problems. We show that this framework can be applied to various dynamic programming problems, of which the cophylogeny problem is a special case.; Pour comprendre la dynamique d'interactions entre des groupes d'espèces, par exemple, dans un contexte hôtes-parasites, il est primordial d'étudier le processus de coévolution. La réconciliation cophylogénétique est un modèle qui traduit la reconstruction de l'histoire coévolutive en un problème d'optimisation combinatoire. L'ensemble des solutions optimales, qui représentent des scénarios coévolutifs différents, peut avoir une taille considérable, rendant l'analyse des résultats difficile. Le résultat principal de cette thèse porte sur une nouvelle méthode qui permet d'explorer l'espace de solutions de manière efficace. D'abord, je définis des relations d'équivalence et propose des algorithmes d'énumération qui produisent la liste des solutions représentatives, c'est-à-dire des solutions appartenant à chacune des classes d'équivalence. Ensuite, je présente des résultats expérimentaux et montre que l'analyse des classes d'équivalence aide à mieux étudier des jeux de données biologiques. Basé sur nos résultats algorithmiques, un logiciel appelé Capybara a été développé comme un nouvel outil pratique pour l'analyse cophylogénétique. Plus généralement, l'énumération des classes d'équivalence des solutions est un problème théorique important. Dans la seconde partie de la thèse, je présente un cadre général au sein duquel l'énumération efficace des classes d'équivalence est possible. Je propose un algorithme qui énumère les classes d'équivalence des solutions pour une famille de problèmes, en particulier, des problèmes où s'applique la technique de programmation dynamique.
Published: 2021

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

330 results on '"Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources