Exhaustive RT-RICO algorithm for mining association rules in protein secondary structure

Prediction of a protein´s secondary structure from its amino acid sequence is a well studied computational problem in bioinformatics, and has significant practical research value. Although the secondary structure prediction problem was first defined almost fifty years ago, the accuracy of most modern methods still hovers around 80%. In [1] this research team presented a promising protein secondary structure prediction method, BLAST-RT-RICO (Relaxed Threshold Rule Induction from Coverings), that employs a modified association rule learning approach, utilizing multiple sequence alignment information. BLAST-RT-RICO achieved Q₃ scores of 89.93% and 87.71% on the standard test datasets RS126 and CB396, respectively. However, there were some areas of the algorithm that were in need of improvement; most importantly, the time complexity for the rule generation step needed to be reduced. Recently, we developed a modified rule generation algorithm, ERT-RICO (Exhaustive Relaxed Threshold Rule Induction from Coverings), that addresses this issue. The research team now is able to run much larger test datasets with different choices of segment length and threshold value; preliminary test results achieved a Q₃ score of 92.19% on the standard test dataset RS126. The modified algorithm, its mathematical definitions, and the improved time/space complexity are discussed in this paper.