An optimal DNA segmentation based on the MDL principle
International Journal of Bioinformatics Research and Applications · 2005
DOI: 10.1504/ijbra.2005.006899 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Bioinformatics Research and Applications, 2005. Verfasst von Wojciech Szpankowski und 2 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA. spa@cs.purdue.edu. Die Arbeit wurde bisher 10-mal zitiert (Crossref). Gefördert von: NIGMS NIH HHS.
Abstract (Originalsprache)
The biological world is highly stochastic and inhomogeneous in its behaviour. There are regions in DNA with a high concentration of G or C bases; stretches of sequences with an abundance of CG dinucleotide (CpG islands); coding regions with strong periodicity-of-three pattern, and so forth. Transitions between these regions of DNA, known also as change points, carry important biological information. Computational methods used to identify these homogeneous regions are called segmentations. Viewing a DNA sequence as a non-stationary process, we apply recent novel techniques of universal source coding to discover stationary (possibly recurrent) segments. In particular, the Stein-Ziv lemma is adopted to find an asymptotically optimal discriminant function that determines whether two DNA segments are generated by the same source assuring exponentially small false positives. Next, we use the Minimum Description Length (MDL) principle to select parameters that lead to a linear-time segmentation algorithm. We apply our algorithm to human chromosome 9 and chromosome 20 to discover coding and noncoding regions, starting positions of genes, as well as the beginning of CpG islands.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Substanzen
Autor:innen und Institutionen
- Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA. spa@cs.purdue.edu
Förderung
- NIGMS NIH HHS
Zitieren
APA
Szpankowski, W., Ren, W., & Szpankowski, L. (2005). An optimal DNA segmentation based on the MDL principle. International Journal of Bioinformatics Research and Applications. https://doi.org/10.1504/ijbra.2005.006899
Vancouver
Szpankowski W, Ren W, Szpankowski L. An optimal DNA segmentation based on the MDL principle. International Journal of Bioinformatics Research and Applications. 2005. doi:10.1504/ijbra.2005.006899
BibTeX
@article{Szpankowski2005,
author = {Szpankowski, Wojciech and Ren, Wenhui and Szpankowski, Lukasz},
title = {An optimal DNA segmentation based on the MDL principle},
journal = {International Journal of Bioinformatics Research and Applications},
year = {2005},
doi = {10.1504/ijbra.2005.006899}
}
EUVIMED