Reinforcement Learning for Improving Gene Identification Accuracy by Combination of Gene-Finding Programs

Reinforcement Learning for Improving Gene Identification Accuracy by Combination of Gene-Finding Programs

Peng-Yeng Yin (National Chi Nan University, Taiwan), Shyong Jian Shyu (Ming Chuan University, Taiwan), Shih-Ren Yang (Ming Chuan University, Taiwan) and Yu-Chung Chang (Ming Chuan University, Taiwan)
Copyright: © 2012 |Pages: 14
DOI: 10.4018/jamc.2012010104
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Due to the explosive and growing size of the genome database, the discovery of gene has become one of the most computationally intensive tasks in bioinformatics. Many such systems have been developed to find genes; however, there is still some room to improve the prediction accuracy. This paper proposes a reinforcement learning model for a combination of gene predictions from existing gene-finding programs. The model learns the optimal policy for accepting the best predictions. The fitness of a policy is reinforced if the selected prediction at a nucleotide site correctly corresponds to the true annotation. The model searches for the optimal policy which maximizes the expected prediction accuracy over all nucleotide sites in the sequences. The experimental results demonstrate that the proposed model yields higher prediction accuracy than that obtained by the single best program.
Article Preview

1. Introduction

There is an explosive growth in the amount of sequenced nucleotides from a number of genome projects. Several million bases of genomic DNA are sequenced daily and made available to the public. The genome annotation, one of the most important works of genome project, is to find all existing genes on the genomic DNA sequences. Conventionally, the genome annotation can be divided into three steps, namely automatic annotation, manual annotation and experimental verification. The automatic annotation is the main task of bioinformatics. This is because manually annotating the coding regions of genes on all genomic sequences from scratch is impractical; instead, the sequences should be pre-analyzed in a high-throughput computational way.

To date, many gene-finding programs have been developed to annotate the newly sequenced genomes. These programs can be broadly classified into two classes. Homology-based methods discover genes using a systematic database search. They are based on the fact that homologous genes may have similar gene structure (Kulp et al., 1997; Korf et al., 2001), such as AAT (Huang, 1997), GeneBuilder (Milanesi et al., 1999) and CRASA (Chuang et al., 2003). However, researchers have found that only about 50% of the annotated genes have similar homologues in the database (Uberbacher et al., 1996; Dunham et al., 1999). This is due to the amount of known proteins are currently limited.

The second class of gene-finding programs consists of ab initio methods which are based on machine learning techniques such as artificial neural networks (GRAIL) (Xu et al., 1997), GeneParser (Snyder & Stormo, 1995), discriminant analysis (GeneFinder) (Solovyev et al., 1994), MZEF (Zhang, 1997), hidden Markov models (Genie) (Kulp et al., 1996), GENSCAN (Burge & Karlin, 1997), and HMMgene (Krogh, 1997). Although these gene-finding programs have been demonstrated with high prediction accuracy in certain species, we still lack a universal program that can report satisfactory accuracy in general cases. Most researchers attempted to develop a new gene-finding program that can attain better prediction accuracy than existing ones; however, they overlook the fact that different gene-finding methods may be considerably complementary to one another. The fusion of multiple experts has been empirically shown to be superior to using single expert alone in many machine learning applications (Richardson & Domingos, 2003; Yin et al., 2005). We argue that even a worse gene-finding program can correct part of the predictions produced by a novel gene predictor. For instance, a 47,338 bp of human DNA is annotated for determining the gene structures (that is to point out where is exon or intron), GENSCAN can correctly identify 47,083 bp. For the remaining 255 bp that are not well annotated, all of them can be identified either via AAT (128/255 bp) or using HMMgene (156/255 bp). It reveals a chance for synergy among variable programs. Therefore, the combination of multiple gene-finding programs may get better gene annotation rather than using any single best program.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing