Segmentation algorithm for DNA sequences

Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Oct;72(4 Pt 1):041917. doi: 10.1103/PhysRevE.72.041917. Epub 2005 Oct 17.

Abstract

A new measure, to quantify the difference between two probability distributions, called the quadratic divergence, has been proposed. Based on the quadratic divergence, a new segmentation algorithm to partition a given genome or DNA sequence into compositionally distinct domains is put forward. The new algorithm has been applied to segment the 24 human chromosome sequences, and the boundaries of isochores for each chromosome were obtained. Compared with the results obtained by using the entropic segmentation algorithm based on the Jensen-Shannon divergence, both algorithms resulted in all identical coordinates of segmentation points. An explanation of the equivalence of the two segmentation algorithms is presented. The new algorithm has a number of advantages. Particularly, it is much simpler and faster than the entropy-based method. Therefore, the new algorithm is more suitable for analyzing long genome sequences, such as human and other newly sequenced eukaryotic genome sequences.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms*
  • Base Sequence
  • Chromosome Mapping / methods*
  • DNA / chemistry*
  • Models, Genetic*
  • Models, Statistical
  • Molecular Sequence Data
  • Pattern Recognition, Automated / methods*
  • Sequence Alignment / methods*
  • Sequence Analysis, DNA / methods*

Substances

  • DNA