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 windo
Original language | English |
---|---|
DOIs | |
State | Published - Jun 3 2010 |