Gene recognition via spliced sequence alignment.
Mikhail Sergeevich Gelfand, Andrey A. Mironov, Pavel A. Pevzner · Proceedings of the National Academy of Sciences · 1996
Gene recognition is one of the most important problems in computational molecular biology. Previous attempts to solve this problem were based on statistics, and applications of combinatorial methods for gene recognition were almost unexplored. Recent advances in large-scale cDNA sequencing open a way toward a new approach to gene recognition that uses previously sequenced genes as a clue for recognition of newly sequenced genes. This paper describes a spliced alignment algorithm and software tool that explores all possible exon assemblies in polynomial time and finds the multiexon structure with the best fit to a related protein. Unlike other existing methods, the algorithm successfully recognizes genes even in the case of short exons or exons with unusual codon usage; we also report correct assemblies for genes with more than 10 exons. On a test sample of human genes with known mammalian relatives, the average correlation between the predicted and actual proteins was 99%. The algorithm correctly reconstructed 87% of genes and the rare discrepancies between the predicted and real exon-intron structures were caused either by short (less than 5 amino acids) initial/terminal exons or by alternative splicing. Moreover, the algorithm predicts human genes reasonably well when the homologous protein is nonvertebrate or even prokaryotic. The surprisingly good performance of the method was confirmed by extensive simulations: in particular, with target proteins at 160 accepted point mutations (PAM) (25% similarity), the correlation between the predicted and actual genes was still as high as 95%.
Cited by 307 works. doi:10.1073/pnas.93.17.9061
Authors
References
- Basic Local Alignment Search Tool
- Rapid similarity searches of nucleic acid and protein data banks.
- Recognition of protein coding regions in DNA sequences
- Amino acid substitution matrices from an information theoretic perspective
- Identification of protein coding regions by database similarity search
- Locating protein-coding regions in human DNA sequences by a multiple sensor-neural network approach.
- Analysis of insertions/deletions in protein structures
- 3,400 new expressed sequence tags identify diversity of transcripts in human brain
- Prediction of gene structure
- Introduction to Computational Biology