Limits...
A consolidation algorithm for genomes fractionated after higher order polyploidization.

Jahn K, Zheng C, Kováč J, Sankoff D - BMC Bioinformatics (2012)

Bottom Line: In this paper, we present a new consolidation algorithm that extends and improves previous work in several directions.Finally, this algorithm reduces the asymptotic time complexity of consolidation from quadratic to linear dependence on the genome size.The new algorithm is applied both to plant genomes and to simulated data to study the effect of fractionation in ancient hexaploids.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, Ottawa, Canada K1N 6N5. sankoff@uottawa.ca

ABSTRACT

Background: It has recently been shown that fractionation, the random loss of excess gene copies after a whole genome duplication event, is a major cause of gene order disruption. When estimating evolutionary distances between genomes based on chromosomal rearrangement, fractionation inevitably leads to significant overestimation of classic rearrangement distances. This bias can be largely avoided when genomes are preprocessed by "consolidation", a procedure that identifies and accounts for regions of fractionation.

Results: In this paper, we present a new consolidation algorithm that extends and improves previous work in several directions. We extend the notion of the fractionation region to use information provided by regions where this process is still ongoing. The new algorithm can optionally work with this new definition of fractionation region and is able to process not only tetraploids but also genomes that have undergone hexaploidization and polyploidization events of higher order. Finally, this algorithm reduces the asymptotic time complexity of consolidation from quadratic to linear dependence on the genome size. The new algorithm is applied both to plant genomes and to simulated data to study the effect of fractionation in ancient hexaploids.

Show MeSH

Related in: MedlinePlus

Change in apparent rearrangement after application of the consolidation algorithm. Change in apparent rearrangement in an ancient hexaploid compared to a diploid sister genome, as a function of actual rearrangements and number of deleted genes before (dashed lines) and after (solid lines) application of the consolidation algorithm.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 3: Change in apparent rearrangement after application of the consolidation algorithm. Change in apparent rearrangement in an ancient hexaploid compared to a diploid sister genome, as a function of actual rearrangements and number of deleted genes before (dashed lines) and after (solid lines) application of the consolidation algorithm.

Mentions: The dashed lines in Figure 3 represent the apparent amount of rearrangement in the simulated genomes as a function of actual amount of rearrangement and the number of deleted gene copies. After applying the consolidation algorithm (solid lines), the apparent amount of rearrangement drops strongly and becomes almost independent on the number of deleted genes. These findings suggest that fractionation has the potential to cause a strong bias in rearrangement studies of ancient polyploids and, most important, that the consolidation is able to minimize this distortion. We have recently shown the same effect on simulated tetraploid data using the stricter definition of fractionation intervals where no duplicate genes are allowed in the fractionation region [8].


A consolidation algorithm for genomes fractionated after higher order polyploidization.

Jahn K, Zheng C, Kováč J, Sankoff D - BMC Bioinformatics (2012)

Change in apparent rearrangement after application of the consolidation algorithm. Change in apparent rearrangement in an ancient hexaploid compared to a diploid sister genome, as a function of actual rearrangements and number of deleted genes before (dashed lines) and after (solid lines) application of the consolidation algorithm.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 3: Change in apparent rearrangement after application of the consolidation algorithm. Change in apparent rearrangement in an ancient hexaploid compared to a diploid sister genome, as a function of actual rearrangements and number of deleted genes before (dashed lines) and after (solid lines) application of the consolidation algorithm.
Mentions: The dashed lines in Figure 3 represent the apparent amount of rearrangement in the simulated genomes as a function of actual amount of rearrangement and the number of deleted gene copies. After applying the consolidation algorithm (solid lines), the apparent amount of rearrangement drops strongly and becomes almost independent on the number of deleted genes. These findings suggest that fractionation has the potential to cause a strong bias in rearrangement studies of ancient polyploids and, most important, that the consolidation is able to minimize this distortion. We have recently shown the same effect on simulated tetraploid data using the stricter definition of fractionation intervals where no duplicate genes are allowed in the fractionation region [8].

Bottom Line: In this paper, we present a new consolidation algorithm that extends and improves previous work in several directions.Finally, this algorithm reduces the asymptotic time complexity of consolidation from quadratic to linear dependence on the genome size.The new algorithm is applied both to plant genomes and to simulated data to study the effect of fractionation in ancient hexaploids.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, Ottawa, Canada K1N 6N5. sankoff@uottawa.ca

ABSTRACT

Background: It has recently been shown that fractionation, the random loss of excess gene copies after a whole genome duplication event, is a major cause of gene order disruption. When estimating evolutionary distances between genomes based on chromosomal rearrangement, fractionation inevitably leads to significant overestimation of classic rearrangement distances. This bias can be largely avoided when genomes are preprocessed by "consolidation", a procedure that identifies and accounts for regions of fractionation.

Results: In this paper, we present a new consolidation algorithm that extends and improves previous work in several directions. We extend the notion of the fractionation region to use information provided by regions where this process is still ongoing. The new algorithm can optionally work with this new definition of fractionation region and is able to process not only tetraploids but also genomes that have undergone hexaploidization and polyploidization events of higher order. Finally, this algorithm reduces the asymptotic time complexity of consolidation from quadratic to linear dependence on the genome size. The new algorithm is applied both to plant genomes and to simulated data to study the effect of fractionation in ancient hexaploids.

Show MeSH
Related in: MedlinePlus