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

Gavranović H, Chauve C, Salse J, Tannier E - Bioinformatics (2011)

Bottom Line: 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.Upon request to the authors. haris.gavranovic@gmail.com; eric.tannier@inria.fr.

View Article: PubMed Central - PubMed

Affiliation: Faculty of Natural Sciences, University of Sarajevo, Bosnia and Herzegovina. haris.gavranovic@gmail.com

ABSTRACT

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.

Show MeSH
Representation of 950 good solutions for the A5 proto-chromosome.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3117370&req=5

Figure 9: Representation of 950 good solutions for the A5 proto-chromosome.

Mentions: Figures 8 and 9 represent a sample of locally optimal solutions obtained by repeatedly applying the program with a randomization (the local search is easily randomized for example, as well as the order in which rows are processed in the partition refinement heuristic). In these figures, the order of the columns we represent is the one of a best found solution, and a gray square at coordinates i,j represents the proportion of solutions in which column i is in position j: the darker the square is, the larger the proportion is.Fig. 8.


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

Gavranović H, Chauve C, Salse J, Tannier E - Bioinformatics (2011)

Representation of 950 good solutions for the A5 proto-chromosome.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3117370&req=5

Figure 9: Representation of 950 good solutions for the A5 proto-chromosome.
Mentions: Figures 8 and 9 represent a sample of locally optimal solutions obtained by repeatedly applying the program with a randomization (the local search is easily randomized for example, as well as the order in which rows are processed in the partition refinement heuristic). In these figures, the order of the columns we represent is the one of a best found solution, and a gray square at coordinates i,j represents the proportion of solutions in which column i is in position j: the darker the square is, the larger the proportion is.Fig. 8.

Bottom Line: 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.Upon request to the authors. haris.gavranovic@gmail.com; eric.tannier@inria.fr.

View Article: PubMed Central - PubMed

Affiliation: Faculty of Natural Sciences, University of Sarajevo, Bosnia and Herzegovina. haris.gavranovic@gmail.com

ABSTRACT

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.

Show MeSH