Las Vegas algorithms for gene recognition: suboptimal and error-tolerant spliced alignment.
Recently, Gelfand, Mironov and Pevzner (1996) proposed a spliced alignment approach to gene recognition that provides 99% accurate recognition of human genes if a related mammalian protein is available. However, even 99% accurate gene predictions are insufficient for automated sequence annotation in large-scale sequencing projects and therefore have to be complemented by experimental gene verification. One hundred percent accurate gene predictions would lead to a substantial reduction of experimental work on gene identification. Our goal is to develop an algorithm that either predicts an exon assembly with accuracy sufficient for sequence annotation or warns a biologist that the accuracy of a prediction is insufficient and further experimental work is required. We study suboptimal and error-tolerant spliced alignment problems as the first steps towards such an algorithm, and report an algorithm which provides 100% accurate recognition of human genes in 37% of cases (if a related mammalian protein is available). In 52% of genes, the algorithm predicts at least one exon with 100% accuracy.
Sze
S H
SH
Department of Computer Science, University of Southern California, Los Angeles 90089-1113, USA. ssze@hto.usc.edu
Pevzner
P A
PA
D000465:Algorithms; D000595:Amino Acid Sequence; D000818:Animals; D001665:Binding Sites; D005796:Genes; D006801:Humans; D009690:Nucleic Acid Conformation; D012326:RNA Splicing; D016415:Sequence Alignment / Q000379:methods