Mapping ancestral genomes with massive gene loss: a matrix sandwich problem.
2011
Gavranović, Haris | Chauve, Cedric | Salse, Jérôme | Tannier, Eric | UNIVERSITY OF SARAJEVO - UNIVERZITET U SARAJEVU | Department of Mathematics [Burnaby] (SFU) ; Simon Fraser University = Université Simon Fraser (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-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)-Centre Inria de l'Université Grenoble 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-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 [LBBE] (BPGE) ; 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-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-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é Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-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)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-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)-Centre National de la Recherche Scientifique (CNRS)
International audience
اظهر المزيد [+] اقل [-]إنجليزي. 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: [email protected]; [email protected].
اظهر المزيد [+] اقل [-]الكلمات المفتاحية الخاصة بالمكنز الزراعي (أجروفوك)
المعلومات البيبليوغرافية
تم تزويد هذا السجل من قبل Institut national de la recherche agronomique