Searching for discrimination rules in protease proteolytic cleavage activity using genetic programming with a min-max scoring function.
This paper presents an algorithm which is able to extract discriminant rules from oligopeptides for protease proteolytic cleavage activity prediction. The algorithm is developed using genetic programming. Three important components in the algorithm are a min-max scoring function, the reverse Polish notation (RPN) and the use of minimum description length. The min-max scoring function is developed using amino acid similarity matrices for measuring the similarity between an oligopeptide and a rule, which is a complex algebraic equation of amino acids rather than a simple pattern sequence. The Fisher ratio is then calculated on the scoring values using the class label associated with the oligopeptides. The discriminant ability of each rule can therefore be evaluated. The use of RPN makes the evolutionary operations simpler and therefore reduces the computational cost. To prevent overfitting, the concept of minimum description length is used to penalize over-complicated rules. A fitness function is therefore composed of the Fisher ratio and the use of minimum description length for an efficient evolutionary process. In the application to four protease datasets (Trypsin, Factor Xa, Hepatitis C Virus and HIV protease cleavage site prediction), our algorithm is superior to C5, a conventional method for deriving decision trees.
Yang
Zheng Rong
ZR
School of Engineering and Computer Science, Exeter University, Northcote House The Queen's Drive, Exeter EX4 4QJ, UK. z.r.yang@ex.ac.uk
Thomson
Rebecca
R
Hodgman
T Charles
TC
Dry
Jonathan
J
Doyle
Austin K
AK
Narayanan
Ajit
A
Wu
XiKun
X
D000465:Algorithms; D001185:Artificial Intelligence; D001665:Binding Sites; D002384:Catalysis; D010450:Endopeptidases / Q000737:chemistry*; D004789:Enzyme Activation; D006868:Hydrolysis; D016571:Neural Networks, Computer; D009842:Oligopeptides / Q000737:chemistry*; D010446:Peptide Fragments / Q000138:chemical synthesis*; D010447:Peptide Hydrolases / Q000737:chemistry; D011485:Protein Binding; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D013329:Structure-Activity Relationship
D009842:Oligopeptides; D010446:Peptide Fragments; D010450:Endopeptidases; D010447:Peptide Hydrolases