CS662b

CS 662b/462b: 

CS 662b/462b Noman Shihadeh Supervisor: Dr. Lila Kari

What is the content?: 

What is the content? You may not know me, but I know everything about you. Psalm 139:1 I know when you sit down and when you rise up. Psalm 139:2I am familiar with all your ways. Psalm 139:3Even the very hairs on your head are numbered. Matthew 10:29-31For you were made in my image. Genesis 1:27In me you live and move and have your being. Acts 17:28 For you are my offspring. Acts 17:28 I knew you even before you were conceived. Jeremiah 1:4-5 I chose you when I planned creation. Ephesians 1:11-12 You were not a mistake, for all your days are written in my book. Psalm 139:15-16I determined the exact time of your birth and where you would live. Acts 17:26 You are fearfully and wonderfully made. Psalm 139:14 I knit you together in your mother's womb. Psalm 139:13 And brought you forth on the day you were born. Psalm 71:6I have been misrepresented by those who don't know me. John 8:41-44I am not distant and angry, but am the complete expression of love. 1 John 4:16 And it is my desire to lavish my love on you. 1 John 3:1 Simply because you are my child and I am your Father. 1 John 3:1I offer you more than your earthly father ever could. Matthew 7:11 For I am the perfect father. Matthew 5:48 Every good gift that you receive comes from my hand. James 1:17For I am your provider and I meet all your needs. Matthew 6:31-33My plan for your future has always been filled with hope. Jeremiah 29:11Because I love you with an everlasting love. Jeremiah 31:3 My thoughts toward you are countless as the sand on the seashore. Psalms 139:17-18And I rejoice over you with singing. Zephaniah 3:17I will never stop doing good to you. Jeremiah 32:40For you are my treasured possession. Exodus 19:5 I desire to establish you with all my heart and all my soul. Jeremiah 32:41 And I want to show you great and marvelous things. Jeremiah 33:3 If you seek me with all your heart, you will find me. Deuteronomy 4:29Delight in me and I will give you the desires of your heart. Psalm 37:4 For it is I who gave you those desires. Philippians 2:13 I am able to do more for you than you could possibly imagine. Ephesians 3:20 For I am your greatest encourager. 2 Thessalonians 2:16-17I am also the Father who comforts you in all your troubles. 2 Corinthians 1:3-4 When you are brokenhearted, I am close to you. Psalm 34:18 As a shepherd carries a lamb, I have carried you close to my heart. Isaiah 40:11 One day I will wipe away every tear from your eyes. Revelation 21:3-4 And I'll take away all the pain you have suffered on this earth. Revelation 21:3-4 I am your Father, and I love you even as I love my son, Jesus. John 17:23For in Jesus, my love for you is revealed. John 17:26He is the exact representation of my being. Hebrews 1:3He came to demonstrate that I am for you, not against you. Romans 8:31 And to tell you that I am not counting your sins. 2 Corinthians 5:18-19Jesus died so that you and I could be reconciled. 2 Corinthians 5:18-19 His death was the ultimate expression of my love for you. 1 John 4:10I gave up everything I loved that I might gain your love. Romans 8:31-32If you receive the gift of my son Jesus, you receive me. 1 John 2:23And nothing will ever separate you from my love again. Romans 8:38-39Come home and I'll throw the biggest party heaven has ever seen. Luke 15:7I have always been Father, and will always be Father. Ephesians 3:14-15My question is…Will you be. not against you. Romans 8:31 And to tell you that I am not counting your sins. 2 Corinthians 5:18-19Jesus died so that you and I could be reconciled. 2 Corinthians 5:18-19 His death was the ultimate expression of my love for you. 1 John 4:10I gave up everything I loved that I might gain your love. Romans 8:31-32If you receive the gift of my son Jesus, you receive me. 1 John 2:23And nothing will ever separate you from my love again. Romans 8:38-39Come home and I'll throw the biggest party heaven has ever seen. Luke 15:7I have always been Father, and will always be Father. Ephesians 3:14-15My question is…Will you be

Can you guess now?: 

Can you guess now? You may Irak not know me, but I know everything about you. Psalm 139:1 War know when you sit down and when you rise up. Psalm 139:2I am familiar with all your ways. Psalm 139:3Even the very hairs on your head are numbered. Matthew 10:29-31For you were made in my image. Genesis 1:27In Bush me you live and move and Terrorism have your being. Acts 17:28 For you are my offspring. Acts 17:28 I knew you even before you were conceived. Jeremiah 1:4-5 I chose you when I planned creation. Ephesians 1:11-12 You were not a mistake, for all your days are written in my book. Psalm 139:15-16I determined the exact time of your birth and where you would live. Acts 17:26 You are fearfully and wonderfully made. Psalm 139:14 I knit you together in your mother's womb. Psalm 139:13 And brought you forth on the day you were born. Psalm 71:6I have been Irak misrepresented by those who don't know me. John Irak 8:41-44I am not distant and angry, but am the Bush complete expression of love. 1 John 4:16 And it is my desire to lavish my love on you. 1 John 3:1 Simply because you are my child and I am your Father. 1 John 3:1I offer you more than your earthly father ever could. Matthew 7:11 For I am the perfect father. Matthew 5:48 Every good gift that you receive comes from my hand. James 1:17For I am your provider and I meet all your needs. Matthew 6:31-33My plan for your future has Terrorism always been filled with hope. Jeremiah 29:11Because I you with an everlasting love. Jeremiah 31:3 My thoughts toward you are countless as the sand on the seashore. Psalms 139:17-18And I rejoice over you with singing. Zephaniah 3:17I will never stop doing good to you. Jeremiah 32:40For you are my treasured possession. Irak Exodus 19:5 I desire to establish you with all War my heart and all my soul. Jeremiah 32:41 And I want to show you great and marvelous things. Jeremiah 33:3 If you seek me with all your heart, you will find me. Deuteronomy 4:29Delight in me and I will give you the desires of your heart. Psalm 37:4 For it is I who gave you those desires. Philippians 2:13 I am able to do more for you than you could possibly imagine. Ephesians 3:20 For I am your greatest encourager. 2 Thessalonians 2:16-17I am also the Father who comforts you in all your troubles. 2 Corinthians 1:3-4 When you are brokenhearted, I am close to you. War Psalm 34:18 As a shepherd carries a lamb, I have War carried you close to my heart. Isaiah 40:11 One day I will wipe away every tear from your eyes. Revelation 21:3-4 And I'll take away all the pain you have suffered on this earth. Revelation 21:3-4 I am your Father, and I love you even as I love my son, Jesus. John 17:23For in Jesus, my love for you is revealed. John 17:26He is the exact representation of my being. Hebrews 1:3He came to demonstrate that I am for you, not against you. Romans 8:31 And to tell you that I am not counting your sins. 2 Corinthians 5:18-19Jesus died so that you and I could be reconciled. 2 Corinthians 5:18-19 His death was the ultimate expression of my love for you. 1 John 4:10I gave up everything I loved that I might gain your love. Romans 8:31-32If you receive the gift of my son Jesus, you receive me. 1 John 2:23And nothing will ever separate you from my love again. Romans 8:38-39Come home and I'll throw the biggest party heaven has ever seen. Luke 15:7I Terrorism have always been Father, Bush and will always be Father. Ephesians 3:14-15My Bush question is…Will you be. not against you.

The topic of my presentation: 

The topic of my presentation Complexity Measures of DNA Computing

Complexity Measures of DNA Computing: 

Complexity Measures of DNA Computing Overview What is a string complexity? Why do we need to study DNA complexity? Complexity measure techniques for strings: Kolmogorov complexity Lempel-Ziv complexity Linguistic complexity n-subword complexity Implementation Results Summary

What is a string complexity?: 

What is a string complexity? Many Definitions General definition: Describing the difficulty of formulating the behavior of the whole in terms of the basic parts.

Simple: 

Simple

Complex: 

Complex

What is a string complexity?: 

Formal definition: The shortest program that can generate the string (Kolmogorov complexity). The shortest compressed form (Lempel-Ziv complexity) The number of repetitions The number of factors Etc. What is a string complexity?

Why do we need to study complexity?: 

General view Identify regular patterns Identify repetitions Compression Why do we need to study complexity?

Why do we need to study complexity?: 

Why do we need to study complexity? Biological view Is it possible to recognize the structure of genes only by an analysis of the ’complexity’ of the language of their subwords? Does there exists a difference between the structure of the language of the subwords of the given gene and the random word? Coding and non-coding sequences? Compare the structure of the same gene for different species, using the n-subword complexity measure?

Complexity measure for strings: 

Complexity measure for strings Kolmogorov complexity: Introduced in the sixties by Andrea Kolmogorov. Minimum length of a program that when run on a universal Turing machine output the string and halts (how many bits needed to encode the string). φ: a universal computer p: a program x: a string є {0,1}*

Kolmogorov Complexity: 

Kolmogorov Complexity Random strings have high kolmogorov complexity (kolmogorov complexity cannot be too much larger than the string itself). Regular strings (repetitions) have low complexity (string can be computed by a program that is shorter than the string itself).

Kolmogorov Complexity: 

Kolmogorov Complexity Example 1: W1= 100 w2= 1010101 K(w1) andlt; K(w2) Fewer steps to generate w1

Kolmogorov Complexity: 

Example 2: W1=11111 w2= 10101 K(w1) andlt; k(w2) W1 is a regular string Five repetitions of ‘1’ Kolmogorov Complexity

Kolmogorov Complexity: 

Kolmogorov Complexity Problems: Uncomputable ( halting problem ) there is no program which takes a string s as input and produces the integer K(s) as output Kolmogorov complexity is rarely used in practice. Not applicable to biological strings( good for strings of infinite length).

Complexity measure for strings: 

Lempel-ziv complexity: Was defined 1976 by Lempel and Ziv. Counts the different patterns in a sequence starting from short patterns to the longer ones. Complexity measure for strings

Lempel–ziv Complexity: 

Lempel–ziv Complexity Production parsing of a sequence: S= S(1,h1)S(h1+1,h2)……S(hm-1+1,hm) H(S)= H(1,h1),S(h1+1,h2),……,S(hm-1+1,hm) h1=1, hm=N Hi(S)= H(hi-1+1,hi) , i=1,2,…,m where H0=0 are called the components of H(S)

Lempel–ziv Complexity: 

The complexity of the string s=0010 The first digit has always to be inserted -andgt; 0. S=0, Q=0, SQ=00, SQ =0, Q in v(SQ )-andgt;0.0 S=0, Q=01, SQ=001, SQ =00, Q not in v(SQ )-andgt;0.01. S=001, Q=0, SQ=0010, SQ =001, Q in v(SQ )-andgt;0.01.0 c(s) = 3 Lempel–ziv Complexity

Lempel–ziv Complexity: 

Lempel–ziv Complexity At each step two operations are allowed: Copying the longest fragments that has been already synthesized. Generating an additional symbols

Lempel–ziv Complexity: 

Example: S = AAABBABAABAAABAB A.AAB.BA.BAA.BAAA.BAB C(S) = 6 Lempel–ziv Complexity

Lempel–ziv Complexity: 

W1 = 1101011010 W2 = 1010110100 1.10.101.1010 C(W1) = 4 1.0.10.11.01.00 C(W2) = 6 Lempel–ziv Complexity More examples:

Lempel–ziv Complexity: 

Lempel–ziv Complexity 1 1 1 0 0 1 1 1 0 0 0 1.10.101.1010 1.0.10.11.01.00

Lempel–ziv Complexity: 

Usage: Lempel-Ziv complexity is an important measure used in cryptography. Lempel-Ziv complexity used in many compression algorithms (Interested in Finding the regularities ). Lempel–ziv Complexity

Complexity measure for strings: 

Linguistic complexity Defined as the ratio of the number of subwords (substrings) to the maximum number of subwords. Introduced by Trifonov (1990) Used by Popov et al. (1996) to compare biological sequences with natural languages texts. Complexity measure for strings

Linguistic Complexity: 

Linguistic Complexity Example 1: S= ACGGTAC |S| = 7 |S1|= 4, |S2|= 5, |S3|= 5, |S4|=4,|S5|= 3, |S6|= 2, |S7|= 1 S contains: 4+5+5+4+3+2+1=24 LC(S)= 24/25= 0.96

Linguistic Complexity: 

Example 2: S= ACACACA |S| = 7 |S1|= 2, |S2|= 2, |S3|= 2, |S4|=2,|S5|= 2, |S6|= 2, |S7|= 1 S contains: 2+2+2+2+2+2+1=13 LC(S)= 13/25= 0.52 Linguistic Complexity

Complexity measure for strings: 

Complexity measure for strings Subword complexity: The subword complexity of a word w is the number of different factors (subwords) that occur in w and is denoted by Pw. The n-subword complexity of a word w is the number of different factors (subwords) of the length n that occur in w and is denoted by Pw(n).

Subword Complexity: 

Subword Complexity Basic notations and Definitions: A denotes a finite alphabet ( A,C,G,T). denotes the set of all finite sequences of letters. A* add the empty word to

Subword Complexity: 

Subword Complexity denotes a finite word є A, 1≤ i ≤ N. |w|=N q = card (A)=4

Subword Complexity: 

Subword Complexity w= puq, u is a subword or a factor Suffix q is є Prefix p is є

Subword Complexity: 

Subword Complexity Fact(w) Set of all factors of w. Pre(w) Set of all prefixes of w. Suf(w) Set of all suffixes of w.

Subword Complexity: 

Subword Complexity Pw is the subword complexity of w. Pw(n) counts the number of distinct factors of length n occurring in w. Pw(n)=0 if n andgt; |w| for a finite word w. the total complexity

Slide34: 

Special factors u є Fact(w) is a right special factor if there exist two distinct letters a, b such that ua, ub є Fact(w). u є Fact(w) is a left special factor if there exist two distinct letters a, b such that au, bu є Fact(w). u is bispecial factor if it is both. Subword Complexity

Slide35: 

Rw =min { n є N | there is no right special factor of w of length n}. Kw =min { n є N | there is no left special factor of w of length n}. |Repetitions| = Max{ Rw, Kw } -1 m = min {Rw, Kw} M = max {Rw, Kw} Subword Complexity

Subword Complexity: 

Subword Complexity Example 1: w = abab Fact(w) = {є, a, b, ab, ba, aba, bab, abab} Pre(w) = {є, a, ab, aba, abab} Suf(w) = {є, b, ab, bab, abab}

Subword Complexity: 

Example 2: w = TAGACTGTAAGGATCAGG TA is right special factor (G, A) GA is right special factor (C, T) Subword Complexity

Subword Complexity: 

w = TAGACTGTAAGGATCAGG AGG is left special factor (A, C) GA is left special factor (A, G) Subword Complexity

Subword Complexity: 

w = TAGACTGTAAGGATCAGG GA is bispecial factor (A, G), (C, T) Subword Complexity

Subword Complexity: 

Example 3: w = ATAGCAATGCA N=11 Kw = 4; Rw = 3; m =3; M = 4. |Repetitions| = 4 -1 = 3 GCA Pw(1) = 4. Pw(2) = 7, (AT, AG, AA, CA, GC, TA, TG) Subword Complexity

Subword Complexity: 

Pw(3) = 8; Pw(4) = 8; Pw(5) = 7; Pw(6) = 6; . . Pw(11) = 1. c(w) = Pw(1)+Pw(2)+…….+Pw(11) = 56 Subword Complexity

Subword Complexity: 

Subword Complexity m M

Subword Complexity: 

1. It is strictly increasing when n є [0,m] 2. It is nondecreasing when n є [m,M]. (If Rw andlt; Kw then it is constant) 3. It is decreasing when n є [M,N]. Moreover Pw(n + 1) = Pw(n) - 1 when n є [M,N]. Subword Complexity

Implementation: 

Implementation W= TAGATATCG Suffix Tree O( n² ) Complete suffix tree O( n )

Implementationsuffix tree W= TAGATATCG: 

Implementation suffix tree W= TAGATATCG A C G T G G A T A C G T G C G A T A T C G T A T C G C G T A A T G A T C G C c(w) =38

Implementationcomplete suffix tree(McCright algorithm): 

A CG G T GATATCG ATATCG T A CG TCG GATATCG Implementation complete suffix tree(McCright algorithm) W= TAGATATCG CG ATCG

Results: 

Results

ResultsN= 700: 

Results N= 700

ResultsN= 2100: 

Results N= 2100

Results: 

Results

Summary: 

Summary 1965 Kolmogorov complexity ( text ) 1976 Lemplel-Ziv complexity ( Compression of finite text ) 1994 Grumbach and Tahi ( compression of DNA Sequences) 1990 Trifonov (Linguistic complexity) 2002 Troyanskaya (Linguistic compleixty) 1997 De Luca and Colosimo(Subword complexity)

Reference: 

Reference [1] A. Colosimo and A. De Luca. Special factors in biological strings. J. Theor. Biol., 204:29{46, 2000. [2] A. de Luca. On the combinatorics of finite words. Theoretical Computer Science, 218:13{39, 1999. [3] M. Li and P. Vitanyi. An introduction to Kolmogorov complexity and its application. Springer, Berlin, 1997. [4] E. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM, 23:262{272, 1976.

Reference: 

[5] G. Troyanskaya, O. Arbell, Y. Koren, G. Landau, and A. Bolshoy. Sequence complexity pro¯les of prokaryotic genomic sequences: A fast algorithm for calculation linguistic complexity. Bioinformatics, 18:679{688, 2002. [6] ABRAHAM LEMPEL, MEMBER, IEEE, AND JACOB ZIV, FELLOW, IEEE On the Complexity of Finite Sequences [7] L. Allison a,*, L. Stern b, T. Edgoose a, T.I. Dix a Sequence complexity for biological sequence analysis [8] Honghui Wan *, John C. Wootton, A global compositional complexity measure for biological sequences: Reference

Questions: 

Questions