TY - JOUR
T1 - Sequence complexity profiles of prokaryotic genomic sequences
T2 - A fast algorithm for calculating linguistic complexity
AU - Troyanskaya, Olga G.
AU - Arbell, Ora
AU - Koren, Yair
AU - Landau, Gad M.
AU - Bolshoy, Alexander
N1 - Funding Information:
We wish to thank Ed Trifonov and Valery Kirzhner for helpful discussions. We are grateful to Dr Larsson who permitted to use his code in our software. A.B. is a Guastaella Fellow, and is partially supported by the Fondation Sacta-Rachi, the Ancell Teicher Research Foundation for Molecular Genetics and Evolution, and by the FIRST Foundation of the Israel Academy of Science and Humanities. O.G.T. and O.A. are partially supported by the Israel Science Foundation, founded by the Israeli Academy of Sciences and Humanities. G.L. is partially supported by NSF grants CCR-9610238 and CCR-0104307, by NATO Science Programme grant PST.CLG.977017, by the Israel Science Foundation grants 173/98 and 282/01, by the FIRST Foundation of the Israel
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0036083579&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0036083579&partnerID=8YFLogxK
U2 - 10.1093/bioinformatics/18.5.679
DO - 10.1093/bioinformatics/18.5.679
M3 - Article
C2 - 12050064
AN - SCOPUS:0036083579
SN - 1367-4803
VL - 18
SP - 679
EP - 688
JO - Bioinformatics
JF - Bioinformatics
IS - 5
ER -