Maximum-scoring segment sets
Author:
- 1 October 2004
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 1 (4) , 139-150
Abstract
We examine the problem of finding maximum-scoring sets of disjoint segments in a sequence of scores. The problem arises in DNA and protein segmentation and in postprocessing of sequence alignments. Our key result states a simple recursive relationship between maximum-scoring segment sets. The statement leads to fast algorithms for finding such segment sets. We apply our methods to the identification of noncoding RNA genes in thermophilesKeywords
This publication has 38 references indexed in Scilit:
- The genome of Nanoarchaeum equitans: Insights into early archaeal evolution and derived parasitismProceedings of the National Academy of Sciences, 2003
- SRPDB: Signal Recognition Particle DatabaseNucleic Acids Research, 2003
- MAVG: locating non-overlapping maximum average segments in a given sequenceBioinformatics, 2003
- Complete Genome Sequence of an Aerobic Thermoacidophilic Crenarchaeon, Sulfolobus tokodaii strain7DNA Research, 2001
- The minimum description length principle in coding and modelingIEEE Transactions on Information Theory, 1998
- Algorithms for the optimal identification of segment neighborhoodsBulletin of Mathematical Biology, 1989
- A Universal Prior for Integers and Estimation by Minimum Description LengthThe Annals of Statistics, 1983
- Estimating the Dimension of a ModelThe Annals of Statistics, 1978
- Locating maximum variance segments in sequential dataMathematical Geology, 1977
- A new look at the statistical model identificationIEEE Transactions on Automatic Control, 1974