Bioinformatics Vol. 18 no. 5 2002
Pages 679-688
© 2002 Oxford University Press
Sequence complexity profiles of prokaryotic genomic sequences: A fast algorithm for calculating linguistic complexity
1 Genome Diversity Center, Institute of Evolution, University of Haifa,
Haifa, Israel
2 Department of Computer Science, University of Haifa,
Haifa, Israel
3 Department of Computer and Information Science, Polytechnic University,
NY, USA
Received on January 29, 2001
; revised on October 28, 2001
; accepted on November 2, 2001
Motivation: One of the major features of genomic DNA sequences, distinguishing them from texts in most spoken or artificial languages, is their high repetitiveness. Variation in the repetitiveness of genomic texts reflects the presence and density of different biologically important messages. Thus, deviation from an expected number of repeats in both directions indicates a possible presence of a biological signal. Linguistic complexity corresponds to repetitiveness of a genomic text, and potential regulatory sites may be discovered through construction of typical patterns of complexity distribution.
Results: We developed software for fast calculation of linguistic sequence complexity of DNA sequences. Our program utilizes suffix trees to compute the number of subwords present in genomic sequences, thereby allowing calculation of linguistic complexity in time linear in genome size. The measure of linguistic complexity was applied to the complete genome of Haemophilus influenzae. Maps of complexity along the entire genome were obtained using sliding windows of 40, 100, and 2000 nucleotides. This approach provided an efficient way to detect simple sequence repeats in this genome. In addition, local profiles of complexity distribution around the starts of translation were constructed for 21 complete prokaryotic genomes. We hypothesize that complexity profiles correspond to evolutionary relationships between organisms. We found principal differences in profiles of the GC-rich and other (non-GC-rich) genomes. We also found characteristic differences in profiles of AT genomes, which probably reflect individual species variations in translational regulation.
Availability: The program is available upon request from Alexander Bolshoy or at http://csweb.haifa.ac.il/library/#complex
Contact: bolshoy{at}research.haifa.ac.il
* To whom correspondence should be addressed.
4 O.T. was a summer student at Haifa University. Her present address is Stanford Medical Informatics, Stanford University, CA 94305, USA.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  S. Itzkovitz and U. Alon The genetic code is nearly optimal for allowing additional information within protein-coding sequences Genome Res., April 1, 2007; 17(4): 405 - 412. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 L. da Fontoura Costa Biological sequence analysis through the one-dimensional percolation transform and its enhanced version Bioinformatics, March 1, 2005; 21(5): 608 - 616. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. L. Orlov and V. N. Potapov Complexity: an internet resource for analysis of DNA sequence complexity Nucleic Acids Res., July 1, 2004; 32(suppl_2): W628 - W633. [Abstract] [Full Text] [PDF]
|
|