Paper Summary

Title : A Two-Stage Evolutionary Approach for Effective Classiffication of Hypersensitive DNA Sequences

Authors: Uday Kamath, Amarda Shehu, and Kenneth A De Jong

Abstract: Hypersensitive (HS) sites in genomic sequences are reliable markers of DNA regulatory regions that control gene expression. Annotation of regulatory regions is important in understanding phenotypical differences among cells and diseases linked to pathologies in protein expression. Several computational techniques are devoted to mapping out regulatory regions in DNA by initially identifying HS sequences. Statistical learning techniques like Support Vector Machines (SVM), for instance, are employed to classify DNA sequences sequences as HS or non-HS. This paper proposes a method to automate the basic steps in designing an SVM that improves the accuracy of such classification. The method proceeds in two stages and makes use of evolutionary algorithms. An evolutionary algorithm first designs optimal sequence motifs to associate explicit discriminating feature vectors with input DNA sequences. A second evolutionary algorithm then designs SVM kernel functions and parameters that optimally separate the HS and non-HS classes. Results show that this two-stage method significantly improves SVM classification accuracy. The method promises to be generally useful in automating the analysis of biological sequences.

Software Details

The evolutionary algorithm described in the paper can generally be applied to finding optimal kernels for a given problem at hand. The implementation of this algorithm is made available under the Open Source License. The description below consists of two sections. The first provides basic information on how to evolve kernels and provides a link to the code. The second provides development details.

  1. Basics

 2. Developer Details

This is a more detailed description for developers who want to either tune our code for other problems or need more information.

1.  SVMEvaluator (GPProblem implementation for Fitness):

This class does many things like creating a ThreadEvaluator, passing all the information needed like Kernel Individuals, Kernel static parameters, and Kernel dynamic parameters to it, and waiting in a loop for 15 minutes (can be changed) for kernel evaluation. If kernel returns, the accuracy is obtained as Koza fitness. Otherwise, the kernel is judged to be bad and is associated a small fitness value.

2.LibSVM Changes:

3. Ephemeral Random Constants (ERCs)

The paper explains that the ERCs maintaned in our GP trees keep track of the SVM cost parameter C and various kernel parameters. These constants have different roles and range of values. Mutation of ERCs employs the following techniques:

  1. Real ERCs (for C, gamma, sigma, etc.)
  2. Integer ERCs (for order, etc)


Cite this paper
U. Kamath, A. Shehu, and K. De Jong, “A two-stage evolutionary approach for effective classification of hypersensitive DNA sequences,” J. Bioinf. & Comp. Biol., 2011.

Copy Rights and Trade marks

1. LIbSVM : Copy Rights of LIBSVM  2000-2010 Chih-Chung Chang and Chih-Jen Lin
All rights reserved are in LibSVM source code.

2. ECJ:  ECJ is licensed under the Academic Free License, version 3.0, included in the package.

3.Java: Java is registered trademark of Oracle.