Linguistic sequence complexity: Difference between revisions

Revision as of 10:03, 14 March 2012

Revision as of 10:21, 14 March 2012

Line 3:

When a [[nucleotide]] sequence is studied as a text written in the four-letter alphabet, the repetitiveness of such a text, that is, the repetition of its [[N-gram|N-grams (words)]], can be calculated and serves as a measure of sequence complexity. Thus, the more complex a [[DNA_sequence|DNA sequence]], the richer its [[oligonucleotide]] vocabulary, whereas repetitious sequences have relatively lower complexities. We have recently improved the original algorithm described in (Trifonov 1990)<ref name=Trifonov1990/> without changing the essence of the linguistic complexity approach.{{Or|date=March 2012}}<ref name=Gabrielian1999>{{cite doi|10.1016/S0097-8485(99)00007-8|noedit}}}</ref><ref name=Orlov2004>{{cite doi|10.1093/nar/gkh466|noedit}}}</ref><ref name=Janson2004>{{cite doi|10.1016/j.tcs.2004.06.023|noedit}}}</ref>

The meaning of LC may be better understood by regarding the presentation of a sequence as a tree of all subsequences of the given sequence. The most complex sequences have maximally balanced trees, while the measure of imbalance or tree asymmetry serves as a complexity measure. The number of nodes at the tree level {{math|<var>i</var>}} is equal to the actual vocabulary size of words with the length {{math|<var>i</var>}} in a given sequence; the number of nodes in the most balanced tree, which corresponds to the most complex sequence of length N, at the tree level {{math|<var>i</var>}} is either 4ⁱ or N-j+1, whichever is smaller. Complexity ({{math|<var>C</var>}}) of a sequence fragment (with a length RW) can be directly calculated as the product of vocabulary-usage measures (U_i):{{CnCitation needed|date=March 2012}}

<math>C = U_1 U_2...U_i....U_w </math>

Vocabulary usage for oligomers of a given size {{math|<var>i</var>}} can be defined as the ratio of the actual vocabulary size of a given sequence to the maximal possible vocabulary size for a sequence of that length. For example, U₂ for the sequence ACGGGAAGCTGATTCCA = 14/16, as it contains 14 of 16 possible different dinucleotides; U₃ for the same sequence = 15/15, and U₄=14/14. For the sequence ACACACACACACACACA, U₁=1/2; U₂=2/16=0.125, as it has a simple vocabulary of only two dinucleotides; U₃ for this sequence = 2/15. k-tuples with k from two to W considered, while W depends on RW. For RW values less than 18, W is equal to 3; for RW less than 67, W is equal to 4; for RW<260, W=5; for RW<1029, W=6, and so on.{{clarifyClarify|post-text=W looks like a logarithmic measure, but the numbers don't check out very well on a calculator.|date=March 2012}} The value of {{math|<var>C</var>}} provides a measure of sequence complexity in the convenient range 0<C<1 for various DNA sequence fragments of a given length.{{CnCitation needed|date=March 2012}} This novel formula is different from the previous LC measure in two respects: in the way vocabulary usage U_i is calculated, and because {{math|<var>i</var>}} is not in the range of 2 to N-1 but only up to W. This new limitation on the range of U_i makes the algorithm substantially more effective without loss of power.{{Or|date=March 2012}}

This sequence analysis complexity calculation method can be used to search for conserved regions between compared sequences for the detection of low-complexity regions including simple sequence repeats, imperfect [[Direct_repeat|direct]] or [[Inverted_repeat|inverted repeats]], polypurine and polypyrimidine [[Triple-stranded_DNA|triple-stranded DNA structures]], and four-stranded structures (such as [[G-quadruplex|G-quadruplexes]]).<ref name=Kalendar2011>{{cite doi|10.1016/j.ygeno.2011.04.009|noedit}}}</ref>