Mapping ancestral genomes with massive gene loss: a matrix sandwich problem

Autor: Eric Tannier, Haris Gavranović, Jérôme Salse, Cedric Chauve
Přispěvatelé: UNIVERSITY OF SARAJEVO - UNIVERZITET U SARAJEVU, Department of Mathematics [Burnaby] (SFU), Simon Fraser University (SFU.ca), Génétique Diversité et Ecophysiologie des Céréales (GDEC), Institut National de la Recherche Agronomique (INRA)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Artificial Evolution and Computational Biology (BEAGLE), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), 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)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-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)-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), Bioinformatique, phylogénie et génomique évolutive (BPGE), Département PEGASE [LBBE] (PEGASE), 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é 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), University of Sarajevo, UNIVERZITET U SARAJEVU, Department of Mathematics [Burnaby], Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Institut National de la Recherche Agronomique (INRA), 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 Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-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)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Inria Grenoble - Rhône-Alpes
Jazyk: angličtina
Rok vydání: 2011
Předmět:
Whole genome duplication
02 engineering and technology
Biochemistry
Genome
INTERVALS
Extant taxon
MESH: Animals
MESH: Angiosperms
MESH: Evolution
Molecular
Mammals
Genetics
0303 health sciences
Heuristic
Combinatorial optimization problem
Solver
Biological Evolution
Original Papers
[SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM]
Computer Science Applications
Computational Mathematics
Computational Theory and Mathematics
CONTIGUOUS REGIONS
Statistics and Probability
0206 medical engineering
MESH: Biological Evolution
Biology
MESH: Mammals
Evolution
Molecular
Magnoliopsida
03 medical and health sciences
Animals
Humans
Ismb/Eccb 2011 Proceedings Papers Committee July 17 to July 19
2011
Vienna
Austria
RECONSTRUCTION
MESH: Genome
Molecular Biology
Gene
030304 developmental biology
Synteny
COMPLEXITY
MESH: Humans
EVOLUTION
SYNTENY
Evolutionary biology
COMPUTATIONAL METHODS
Evolution and Comparative Genomics
PROPERTY
[INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM]
020602 bioinformatics
Zdroj: Bioinformatics
Bioinformatics, 2011, 27 (13), pp.i257-65. ⟨10.1093/bioinformatics/btr224⟩
Bioinformatics, Oxford University Press (OUP), 2011, 27 (13), pp.i257-65. ⟨10.1093/bioinformatics/btr224⟩
ISSN: 1367-4803
1367-4811
1460-2059
DOI: 10.1093/bioinformatics/btr224⟩
Popis: Motivation: Ancestral genomes provide a better way to understand the structural evolution of genomes than the simple comparison of extant genomes. Most ancestral genome reconstruction methods rely on universal markers, that is, homologous families of DNA segments present in exactly one exemplar in every considered species. Complex histories of genes or other markers, undergoing duplications and losses, are rarely taken into account. It follows that some ancestors are inaccessible by these methods, such as the proto–monocotyledon whose evolution involved massive gene loss following a whole genome duplication. Results: We propose a mapping approach based on the combinatorial notion of ‘sandwich consecutive ones matrix’, which explicitly takes gene losses into account. We introduce combinatorial optimization problems related to this concept, and propose a heuristic solver and a lower bound on the optimal solution. We use these results to propose a configuration for the proto-chromosomes of the monocot ancestor, and study the accuracy of this configuration. We also use our method to reconstruct the ancestral boreoeutherian genomes, which illustrates that the framework we propose is not specific to plant paleogenomics but is adapted to reconstruct any ancestral genome from extant genomes with heterogeneous marker content. Availability: Upon request to the authors. Contact: haris.gavranovic@gmail.com; eric.tannier@inria.fr
Databáze: OpenAIRE
Externí odkaz: