Fast phased small RNA cycle counting algorithms

Forrest Sheng Bao, Zhixin Xie, Yuanlin Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

Counting phased small RNA cycles (PSRC) from mapped small RNA positions is a repeatedly invoked subproblem in the computation of identifying TRANS-ACTING siRNA (TAS) loci and loci of other small RNAs forming through mechanisms similar to that of transacting small interfering RNAs (ta-siRNAs). The efficiency of counting PSRC has a clear impact on the efficiency of the algorithms predicting these loci. There are two closely related variants on counting PSRC in real applications: WPSRC, which counts the number of distinct small RNAs falling onto the phased positions in a sliding window, and MPSRC, which counts the maximum consecutive PSRC from mapped small RNA positions. In this paper, we develop fast algorithms for both WPSRC and MPSRC. Our algorithms have O(max(S)) time complexity, while the existing algorithm and its variant have O(\S\·max(S)) and O(\S\·L) time complexity for MPSRC and WPSRC respectively, where S is a set of mapped small RNA positions and L the length of sliding window for WPSRC. Experimental results on two real-life datasets show that our algorithms are significantly faster than the existing algorithm and its variant. The proposed algorithms are applicable to TAS-like clusters with any PSRC length including 21-nt.

Original languageEnglish
Title of host publication10th IEEE International Conference on Bioinformatics and Bioengineering 2010, BIBE 2010
Pages130-135
Number of pages6
DOIs
StatePublished - 2010
Event10th IEEE International Conference on Bioinformatics and Bioengineering, BIBE-2010 - Philadelphia, PA, United States
Duration: May 31 2010Jun 3 2010

Publication series

Name10th IEEE International Conference on Bioinformatics and Bioengineering 2010, BIBE 2010

Conference

Conference10th IEEE International Conference on Bioinformatics and Bioengineering, BIBE-2010
CountryUnited States
CityPhiladelphia, PA
Period05/31/1006/3/10

Fingerprint Dive into the research topics of 'Fast phased small RNA cycle counting algorithms'. Together they form a unique fingerprint.

Cite this