Username   Password       Forgot your password?  Forgot your username? 


Combining Stochastic Grammar and Semi-Supervised Learning Techniques to Extract RNA Structures with Pseudoknots

Volume 15, Number 7, July 2019, pp. 1939-1946
DOI: 10.23940/ijpe.19.07.p21.19391946

Sixin Tang

College of Computer Science and Technology, Hengyang Normal University, Hengyang, 421002, China


(Submitted on April 13, 2019; Revised on May 25, 2019; Accepted on June 25, 2019)


Retrieving differences between remote sets is widely used in set reconciliation and data deduplication. Set reconciliation and data deduplication between two nodes are widely used in various network applications. The basic idea of the difference retrieving problem is that each member of a node pair has an object set and seeks to find all differences between the two remote sets. There are many methods for retrieving difference sets, such as the standard Bloom filter (SBF), counting Bloom filter (CBF), and invertible Bloom filter (IBF). In these methods, based on the standard Bloom filter or its variants, each node represents its objects using a standard Bloom filter or other Bloom filter, which is then exchanged. A receiving node retrieves different objects between the two sets according to the received SBF, CBF, or IBF. We propose a new algorithm for retrieving differences that finds differences between remote sets using counting Bloom filters' deletion operation. The theoretical analyses and experimental results show that the differences can be retrieved efficiently. Only a very small number of differences are missing in the retrieving process, and this false negative rate can be decreased to 0% by adjusting the counting Bloom filter's parameters.


References: 14

  1. K. Kappel and R. Das, “Sampling Native-Like Structures of RNA-Protein Complexes through Rosetta Folding and Docking,” Structure, Vol. 31, No. 4, pp. 139-151, 2018
  2. D. D. Song and Z. D. Deng, “Fussy Model for RNA Secondary Prediction,” Science in China Vol E: Information Science, Vol. 37, No. 10, pp. 1285-1303, 2007
  3. J. H. Liu, J. T. L. Wang, and J. Hu, “A Method for Aligning RNA Secondary Structures and Its Application to RNA Motif Detection,” BMC Bioinfomatics, Vol. 6, pp. 88-107, 2005
  4. S. X. Tang, Y. B. Liu, and J. Yin, “Research Advances of Grammatical Inference of RNA Secondary Structure,” China Journal of Bioinformatics, Vol. 4, pp. 190-192, 2008
  5. M. Andronescu, A. Condon, and D. H. Mathews, “Computational Approaches for RNA Energy Parameter Estimation,” RNA, Vol. 16, pp. 2304-2318, 2010
  6. S. X. Tang, Y. Zhou, and Y. Yi, “The Application of Stochastic Grammars for RNA Secondary Structrue Prediction,” Journal of Biomathematics, Vol. 23, No. 4, pp. 735-742, 2008
  7. E. P. Nawrocki, “Structural RNA Homology Search and Alignment using Covariance Models,” Washington University School of Medicine, 2009
  8. R. D. Dowell and S. R. Eddy, “Evaluation of Several Lightweight Stochastic Context-Free Grammars for RNA Secondary Structure Prediction,” BMC Bioinformatics, Vol. 5, No. 1, pp. 71, 2004
  9. T. Jebara, “Discriminative, Generative and Imitative Learning,” Massachusetts Inst. of Technology, Media laboratory, 2001
  10. E, Come, L. Oukhellou, and T. Denoeux, “Learning from Partially Supervised Data using Mixture Models and Belief Functions,” Pattern Recognition, Vol. 42, No. 3, pp. 334-348, 2009
  11. A. Tanzera, I. L. Hofackerab, and R. Lorenz, “RNA Modifications in Structure Prediction – Status Quo and Future Challenges,” Methods, Vol. 39, No. 10. pp. 23-38, 2018
  12. G. Tur, D. D. Hakkani-Tur, and R. E. Schapire, “Combining Active and Semi-Supervised Learning for Spoken Language Understanding,” Speech Communication, Vol. 45, pp. 171-186, 2005
  13. S. X. Tang, Y. Zhou, and S. Zou, “The RNA Secondary Structure Prediction based on the Lexicalized Stochastic Grammar Model,” Computer Engineering & Science, Vol. 31, No. 3, pp. 128-131, 2009
  14. S. Griffiths-Jones, A. Bateman, M. Marshall, A. Khanna, and S. R. Eddy, “Rfam: An RNA Family Database,” Nucleic Acids Research, Vol. 31, No. 1, pp. 429-441, 2003


Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

This site uses encryption for transmitting your passwords.