Limits...
RNAslider: a faster engine for consecutive windows folding and its application to the analysis of genomic folding asymmetry.

Horesh Y, Wexler Y, Lebenthal I, Ziv-Ukelson M, Unger R - BMC Bioinformatics (2009)

Bottom Line: Recently an O(NL2) solution for this problem has been described.Here, we describe and implement an O(NLpsi(L)) engine for the consecutive windows folding problem, where psi(L) is shown to converge to O(1) under the assumption of a standard probabilistic polymer folding model, yielding an O(L) speedup which is experimentally confirmed.This is implemented here as a software tool, called RNAslider, and applied to the scanning of long chromosomes, leading to the observation of features that are visible only on a large scale.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Physics of Complex Systems, The Weizmann Institute of Science, Rehovot, Israel. yair.horesh@weizmann.ac.il

ABSTRACT

Background: Scanning large genomes with a sliding window in search of locally stable RNA structures is a well motivated problem in bioinformatics. Given a predefined window size L and an RNA sequence S of size N (L < N), the consecutive windows folding problem is to compute the minimal free energy (MFE) for the folding of each of the L-sized substrings of S. The consecutive windows folding problem can be naively solved in O(NL3) by applying any of the classical cubic-time RNA folding algorithms to each of the N-L windows of size L. Recently an O(NL2) solution for this problem has been described.

Results: Here, we describe and implement an O(NLpsi(L)) engine for the consecutive windows folding problem, where psi(L) is shown to converge to O(1) under the assumption of a standard probabilistic polymer folding model, yielding an O(L) speedup which is experimentally confirmed. Using this tool, we note an intriguing directionality (5'-3' vs. 3'-5') folding bias, i.e. that the minimal free energy (MFE) of folding is higher in the native direction of the DNA than in the reverse direction of various genomic regions in several organisms including regions of the genomes that do not encode proteins or ncRNA. This bias largely emerges from the genomic dinucleotide bias which affects the MFE, however we see some variations in the folding bias in the different genomic regions when normalized to the dinucleotide bias. We also present results from calculating the MFE landscape of a mouse chromosome 1, characterizing the MFE of the long ncRNA molecules that reside in this chromosome.

Conclusion: The efficient consecutive windows folding engine described in this paper allows for genome wide scans for ncRNA molecules as well as large-scale statistics. This is implemented here as a software tool, called RNAslider, and applied to the scanning of long chromosomes, leading to the observation of features that are visible only on a large scale.

Show MeSH

Related in: MedlinePlus

DB ratio in different genomic regions. DB ratios (real to shuffled) in different regions of the Drosophila annotated genome, grouped by lengths. We note that in general the coding regions (CDs and introns) have a DB ratio greater than 1 for all windows lengths, while UTR regions (especially the 5' UTRs) have DB ratio less than 1. Intergenic regions seem to have a ratio that is closer to 1.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 4: DB ratio in different genomic regions. DB ratios (real to shuffled) in different regions of the Drosophila annotated genome, grouped by lengths. We note that in general the coding regions (CDs and introns) have a DB ratio greater than 1 for all windows lengths, while UTR regions (especially the 5' UTRs) have DB ratio less than 1. Intergenic regions seem to have a ratio that is closer to 1.

Mentions: Despite this fact, we noted that there are some variations in this normalized ratio along different regions in genomes. Figure 4 shows the DB real/DB random ratio over several types of genomic regions of the Drosophila annotated genome (Flybase, version 5.2, Feb 2007). It is interesting to note that in general the coding regions (CDs and introns) have a DB ratio greater than 1 for all windows lengths, while UTR regions (especially the 5' UTRs) have DB ratio less than 1. Intergenic regions seem to have ratio that is closer to 1. These results suggest that for functional regions of the genomes there are additional factors, in addition to the dinucleotide composition, that determine the DB values.


RNAslider: a faster engine for consecutive windows folding and its application to the analysis of genomic folding asymmetry.

Horesh Y, Wexler Y, Lebenthal I, Ziv-Ukelson M, Unger R - BMC Bioinformatics (2009)

DB ratio in different genomic regions. DB ratios (real to shuffled) in different regions of the Drosophila annotated genome, grouped by lengths. We note that in general the coding regions (CDs and introns) have a DB ratio greater than 1 for all windows lengths, while UTR regions (especially the 5' UTRs) have DB ratio less than 1. Intergenic regions seem to have a ratio that is closer to 1.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 4: DB ratio in different genomic regions. DB ratios (real to shuffled) in different regions of the Drosophila annotated genome, grouped by lengths. We note that in general the coding regions (CDs and introns) have a DB ratio greater than 1 for all windows lengths, while UTR regions (especially the 5' UTRs) have DB ratio less than 1. Intergenic regions seem to have a ratio that is closer to 1.
Mentions: Despite this fact, we noted that there are some variations in this normalized ratio along different regions in genomes. Figure 4 shows the DB real/DB random ratio over several types of genomic regions of the Drosophila annotated genome (Flybase, version 5.2, Feb 2007). It is interesting to note that in general the coding regions (CDs and introns) have a DB ratio greater than 1 for all windows lengths, while UTR regions (especially the 5' UTRs) have DB ratio less than 1. Intergenic regions seem to have ratio that is closer to 1. These results suggest that for functional regions of the genomes there are additional factors, in addition to the dinucleotide composition, that determine the DB values.

Bottom Line: Recently an O(NL2) solution for this problem has been described.Here, we describe and implement an O(NLpsi(L)) engine for the consecutive windows folding problem, where psi(L) is shown to converge to O(1) under the assumption of a standard probabilistic polymer folding model, yielding an O(L) speedup which is experimentally confirmed.This is implemented here as a software tool, called RNAslider, and applied to the scanning of long chromosomes, leading to the observation of features that are visible only on a large scale.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Physics of Complex Systems, The Weizmann Institute of Science, Rehovot, Israel. yair.horesh@weizmann.ac.il

ABSTRACT

Background: Scanning large genomes with a sliding window in search of locally stable RNA structures is a well motivated problem in bioinformatics. Given a predefined window size L and an RNA sequence S of size N (L < N), the consecutive windows folding problem is to compute the minimal free energy (MFE) for the folding of each of the L-sized substrings of S. The consecutive windows folding problem can be naively solved in O(NL3) by applying any of the classical cubic-time RNA folding algorithms to each of the N-L windows of size L. Recently an O(NL2) solution for this problem has been described.

Results: Here, we describe and implement an O(NLpsi(L)) engine for the consecutive windows folding problem, where psi(L) is shown to converge to O(1) under the assumption of a standard probabilistic polymer folding model, yielding an O(L) speedup which is experimentally confirmed. Using this tool, we note an intriguing directionality (5'-3' vs. 3'-5') folding bias, i.e. that the minimal free energy (MFE) of folding is higher in the native direction of the DNA than in the reverse direction of various genomic regions in several organisms including regions of the genomes that do not encode proteins or ncRNA. This bias largely emerges from the genomic dinucleotide bias which affects the MFE, however we see some variations in the folding bias in the different genomic regions when normalized to the dinucleotide bias. We also present results from calculating the MFE landscape of a mouse chromosome 1, characterizing the MFE of the long ncRNA molecules that reside in this chromosome.

Conclusion: The efficient consecutive windows folding engine described in this paper allows for genome wide scans for ncRNA molecules as well as large-scale statistics. This is implemented here as a software tool, called RNAslider, and applied to the scanning of long chromosomes, leading to the observation of features that are visible only on a large scale.

Show MeSH
Related in: MedlinePlus