Presentazione di PowerPoint

Presentazione di PowerPoint

Introduzione alla teoria dellinformazione misura dellinformazione ridondanza codifica di sorgente robustezza codifica di canale decodifica dellinformazione biologica Francesco Piva Istituto di Biologia e Genetica Universit Politecnica delle Marche [email protected] Struttura di comunicazione attraverso un canale trasmissivo Ci occupiamo della misura dellinformazione emessa da una sorgente la sorgente tanto pi efficiente quanto pi risulta imprevedibile da parte del destinatario linformazione che sar emessa supponiamo che la sorgente di informazione sia un testo, se il destinatario gi conosce quel testo, linformazione emessa dalla sorgente nulla se il destinatario non ha mai letto quel testo, la sorgente emette la massima informazione se il destinatario non conosce il testo ma conosce in modo generico linformazione che si aspetta, allora linformazione risulter minore di quella massima con il termine linguaggio intendiamo una serie di regole su cui sorgenete e destinatario concordano per consentire il trasferimento di informazione

dalluno allaltro Linformazione contenuta in un messaggio ha leffetto di cambiare lo stato di incertezza nei riguardi di una certa situazione. Dopo la ricezione del messaggio lincertezza diminuisce o decade. Pi il messaggio toglie incertezza pi questo ha valore Linformazione lincertezza che si ha prima di ricevere il messaggio. Immaginiamo che io stia aspettando di sapere se una persona (Pippo) o meno nel suo ufficio. Immaginiamo che ci sia il 70% delle probabilit di trovarlo nel suo ufficio e il 30% di trovarlo in altre stanze. Se mi informano che nel suo ufficio, ho eliminato la mia incertezza, ma gi la mia incertezza era bassa perch mi sarei aspettato di trovarlo in ufficio. Quindi questa informazione non ha un valore molto alto. Se mi informano che non nel suo ufficio, ho risolto una maggiore incertezza perch cerano meno probabilit che questo accadesse, cio era una situazione pi inaspettata, quindi avevo unincertezza maggiore. Questa informazione ha pi valore perch mi ha tolto una maggiore incertezza Se ho identiche probabilit di trovare Pippo nel suo ufficio, allora le due informazioni hanno lo stesso valore. Supponiamo che Pippo possa essere in 5 stanze diverse, e in ogni stanza con la stessa probabilit. Ho la probabilit del 20% che esso sia in una stanza. Uninformazione che mi risolve questo stato di incertezza ha molto valore perch molte erano le

possibilit. Altro esempio: supponiamo di essere ad un esame e dover dare la risposta ad un quesito barrando una casella. Supponiamo di non conoscere la risposta alla domanda. Se le caselle, cio le possibili risposte sono due, ho maggiori probabilit di barrare la risposta esatta. Se le caselle fossero 10 ho minore probabilit di barrare quella esatta. Da questo momento consideriamo lequiprobabilit che si verifichi un certo stato tra N aspettati Consideriamo che linformazione elementare viene portata da un simbolo che pu assumere due soli stati: 0 e 1 N=2M Quindi la formula rappresenta il numero di stati che posso risolvere (discriminare) con una sequenza di M simboli di due stati Esempi di parole Lincertezza tanto maggiore quanto maggiore N Allarrivo del messaggio ho uninformazione tanto maggiore quanto pi alta era lincertezza, cio quanto maggiore era N La quantit di informazione portata da un solo simbolo i=log2N N=2 perch un simbolo a due stati mi permette di discriminare tra due eventi i=log22 = 1 bit La quantit di informazione portata da una sequenza di M simboli binari i=log2(2M) = M log22 = log2N = M bit

Se tutti gli N eventi che possono accadere (o gli N simboli che possono giungere) sono equiprobabili, poich N = 1/P, possiamo scrivere la formula precedente in funzione della probabilit. La quantit di informazione portata da un simbolo i = log2N = log2(1/P) = - log2(P) Se gli eventi o i simboli non si verificano con la stessa probabilit, ad esempio p(0) = 0.1 p(1) = 0.9 i0 = - log2(0.1) = 3.3 bit i1 = - log2(0.9) = 0.15 bit i simboli pi rari portano pi informazione Finora abbiamo visto linformazione portata da un preciso simbolo per in una conversazione, in una lettura, in una sequenza di dati di computer abbiamo a che fare con una lunga sequenza di simboli. Qual linformazione media per simbolo portata da una sequenza di simboli? imedio = P0 * i0 + P1 * i1 [bit per simbolo] Nel caso in cui 0 e 1 siano equiprobabili imedio = 0.5 * 1 + 0.5 * 1 = 1 bit Nel caso della non equiprobabilit precedente imedio = 0.1 * 3.3 + 0.9 * 0.15 = 0.46 bit Quindi una sorgente che emette simboli in modo equiprobabile ha la maggior efficienza informativa, cio ciascun simbolo ha il massimo contenuto informativo o a parit di informazione impiega meno simboli

La quantit imedio = P0 * i0 + P1 * i1 detta anche ENTROPIA (H) della sorgente di informazione Si nota che la massima entropia si ha per valori di P = 0.5 cio per lequiprobabilit degli stati 0 e 1. A questo punto si verifica il massimo trasferimento di informazione Estrazione di una sequenza consenso da dati sperimentali Frequenze delle singole lettere nella lingua italiana 0,15 0,12 0,09 0,06

0,03 0,00 a b c d e f g h i j k l m

n o p q r s t u v w x y z _

Frequenze delle singole lettere nella lingua inglese 0,18 0,15 0,12 0,09 0,06 0,03 0,00 a b c d e f g

h i j k l m n o p q r s t u v

w x y z _ Frequenze delle singole lettere 0,18 italiano 0,15 inglese 0,12 0,09 0,06 0,03 0,00

a b c d e f g h i j k l m n o

p q r s t u v w x y z _ RIDONDANZA Non equiprobabilit

correlazione La ridondanza indica quanto diminuisce la capacit di una sorgente di inviare informazioni, a causa della non equiprobabilit e della correlazione tra i simboli. La correlazione il legame tra i simboli che escono da una sorgente, come dire che osservando la sequenza appena uscita, si possono trarre indicazioni sui simboli che stanno per uscire. Esempio: se stiamo leggendo un testo e in particolare una parola, di solito dalle prime lettere si intuisce gi la parola intera. Questo perch c una correlazione tra le lettere di una parola. Le lettere pi importanti alla comprensione sono le prime, queste portano anche pi informazione. albergo albero alcool ali alimento allarme allegria allora alluvione alveolo alm aln alr als Parole proibite a

causa delle regole di semantica che introducono correlazione E la tecnica usata dai software per scrivere messaggi sms sui telefonini aa ak au bd bn bx cg cq c_ dj dt ec em ew ff fp fz gi gs hb hl

hv ie io iy jh jr ka kk ku ld ln lx mg mq m_ nj nt oc om ow pf pp pz qi qs rb rl rv se

so sy th tr ua uk uu vd vn vx wg wq w_ xj xt yc ym yw zf zp zz _i _s frequenze di coppie di lettere in italiano 0,04 0,03

0,03 0,02 0,02 0,01 0,01 0,00 Vantaggi della correlazione tra caratteri: Irrobustiscono linformazione quindi permettono di comprendere la parola anche se ci sfuggono alcuni caratteri, come nel caso di comunicazione disturbata da rumori di fondo Svantaggi Limitano il numero di parole diverse che possiamo comporre quindi abbiamo un linguaggio meno ricco di parole. Posso comporre la parola almnqq ma questa non una sequenza di simboli permessa dalle regole della semantica, cio non c la giusta correlazione tra i caratteri. Altri esempi di correlazione sono larticolo con il nome, il soggetto con il verbo. Codifica di sorgente Immaginiamo di dover trasmettere uno fra quattro possibili stati, possiamo utilizzare solo simboli binari A

B C D 00 01 10 11 A B C D 00 01 10 11 Questa operazione che permette di associare dei simboli agli stati si chiama codifica che richiama lidea di associare un codice Se i 4 stati sono equiprobabili la trasmissione ha gi la massima efficienza P=0.25 P=0.125 P=0.5 P=0.125

Supponiamo ora che sia pi probabile che dobbiamo trasmettere lo stato C e meno probabile di dover trasmettere B e D BCDACACCBACACCDC 01 10 11 00 10 00 10 10 01 00 10 00 10 10 11 10 i = 2 * 0.25 + 2 * 0.125 + 2 * 0,5 + 2 * 0.125 = 2 bit Per trasmettere uno stato uso in media due bit, per questa sequenza ne ho usati 32 A 01 P=0.25 Supponiamo ora di codificare in maniera diversa gli stati. B 001 P=0.125 Precisamente codifichiamo con sequenze pi corte i C 1 P=0.5 simboli pi probabili D 000 P=0.125 BCDACACCBACACCDC 001 1 000 01 1 01 1 1 001 01 1 01 1 1 000 1 i = 2 * 0.25 + 3 * 0.125 + 1 * 0,5 + 3 * 0.125 = 1.75 bit Per trasmettere uno stato uso in media 1.75 bit quindi trasmetto la stessa sequenza di prima ma con meno simboli, infatti ne ho usati 28. Ho attuato una compressione dellinformazione. Il primo ad usare questa tecnica fu Morse. I programmi di compressione tipo Winzip, Arj analizzano la sequenza dei bit del file da comprimere, ricodificano il file associando sequenze di minor lunghezza a quelle pi ricorrenti (codifica di Huffman) Se il file da comprimere ha molta ridondanza, cio correlazione e non equiprobabilit dei simboli, allora questo si comprimer molto. Questo tipo di compressione si basa sulleliminazione delle ridondanze senza perdita di informazioni, vale a dire che il file compresso pu essere riportato alla

forma originale senza che il messaggio si sia degradato. Un altro tipo di compressione quella con perdita di informazione. Questa oltre a sfruttare il principio precedente, elimina quelle informazioni ritenute poco importanti per la comprensione globale del messaggio. E il caso di compressioni di immagini in formato jpg o gif, queste comprimono molto ma provocano una certa perdita della qualit dellimmagine. La perdita irreversibile perch si scelto di memorizzare solo una certa parte delle informazioni. Uno svantaggio della compressione: un errore o unincomprensione di un simbolo rischiano di compromettere la comprensione dellintero messaggio. Esempio: se ci si perde qualche parola del discorso di una persona ridondante, quasi sicuramente si capir il significato del messaggio. Il rumore Modello di un canale di trasmissione P00 0 Simbolo trasmesso 1 P01, P10: probabilit di errore P01

0 Simbolo ricevuto P10 P11 1 Distanza 0110100001010111011 0110100011010111011 Per determinare la distanza tra due sequenze si deve allinearle e colonna per colonna contare il numero di simboli differenti. In questo caso la distanza 1 ovvero le due sequenze differiscono per un solo simbolo. 00 01 10 11 Le sequenze collegate dalle frecce distano fra loro 1 Le sequenze sulle diagonali distano 2 Concetto di distanza evoluzionistica e alberi

filogenetici: posso dire che 00 e 01 sono imparentati direttamente, 11 imparentato sia con 01 che con 10 ma non so da chi derivi. 000 001 010 011 100 101 110 111 011 001 010 000 111 110 101 Abbiamo disposto tutte le sequenze che si possono ottenere con tre bit, su un

cubo in modo che le sequenze collegate direttamente avessero distanza 1. Si nota che per andare da 000 a 111 si devono verificare tre mutazioni ma si possono seguire molti percorsi diversi. 100 Distanza come robustezza: pi facile confondere 000 e 010 perch distano solo 1, una mutazione pu far passare dalluno allaltro, pi difficile confondere 000 e 111 perch ci vogliono tre mutazioni. Analogamente in un discorso pi probabile confondere albero e alberi piuttosto che albero e alluvione. Ancora sulla robustezza Immaginiamo di dover trasmettere uno fra quattro possibili stati, possiamo utilizzare solo simboli binari A B C D 00 01

10 11 Questa operazione che permette di associare dei simboli agli stati si chiama codifica che richiama lidea di associare un codice sorgente 01 11 destinatario disturbo Se avviene un errore durante la trasmissione, il destinatario riceve un messaggio sbagliato e non ha modo di accorgersi che c stato un errore A B C D 000 011 101 110

sorgente 011 001 destinatario disturbo In questo caso il destinatario riceve una sequenza non permessa perch 001 non corrisponde a nulla di valido, quindi si accorge che c stato un errore di trasmissione. Ho ottenuto questo risultato codificando i 4 stati con sequenze a distanza 2 anzich 1, cio ho distanziato gli stati in modo che un errore singolo non mi portasse direttamente a uno stato permesso 101 001 000 010 110 C non permesso

A non permesso D A B C D 0000 1101 0111 1110 Fra gli stati A,C e A,D c distanza 3 Se trasmetto 0000 e al destinatario arriva 0001, questultimo capisce che c stato un errore perch 0001 uno stato non permesso. Inoltre pu anche ipotizzare che era stato trasmesso A perch lo stato pi vicino al simbolo ricevuto. Nel caso di canali non fortemente disturbati ovvero dove ogni 4 simboli si pu avere al massimo un errore, il destinatario in grado di correggere lerrore. 0111

1110 C D 0011 non permesso 0001 non permesso 0000 A 0010 0110 non permesso non permesso Altro modo di aumentare la robustezza di una codifica: Definire delle parole sinonime Codifico A con 000, ogni errore singolo produce delle parole a distanza 1 dala parola 000 Codifico A anche con 001, 010, 100. In questo modo tutte le parole a distanza 1 da 000 sono ancora dei sinonimi di A 100

A 101 001 000 010 011 C A A A D Questa tecnica si chiama codifica di canale Consiste nel codificare gli stati con pi simboli del necessario cos da poter distanziare le parole. In questo modo ho una trasmissione pi robusta, cio pi immune agli errori. Pago questa robustezza con una diminuzione di efficienza perch

trasmetto molti pi simboli a parit di informazione. Dal punto di vista dei simboli impiegati per trasmettere (nello spazio) o memorizzare (nel tempo) un messaggio, la codifica di sorgente ha leffetto contrario cella codifica di canale. La prima comprime, la seconda espande. Sequenze di DNA interpretate secondo la Teoria dellInformazione il codice genetico degenere, che cosa significa in termini numerici? . . . Ala Val Arg . . . GCA GTA CGA C C C G G G T T T AGA G 4 * 4 * 6 = 96 Combinazioni o parole sinonime GCAGTACGA GCAGTACGC GCAGTACGG

GCAGTACGT GCAGTAAGA GCAGTAAGG GCAGTCCGA GCAGTCCGC GCAGTCCGG GCAGTCCGT GCAGTCAGA GCAGTCAGG GCAGTGCGA GCAGTGCGC GCAGTGCGG GCAGTGCGT GCAGTGAGA GCAGTGAGG GCAGTTCGA GCAGTTCGC GCAGTTCGG GCAGTTCGT GCAGTTAGA GCAGTTAGG GCCGTACGA GCCGTACGC GCCGTACGG GCCGTACGT GCCGTAAGA GCCGTAAGG GCCGTCCGA

GCCGTCCGC GCCGTCCGG GCCGTCCGT GCCGTCAGA GCCGTCAGG GCCGTGCGA GCCGTGCGC GCCGTGCGG GCCGTGCGT GCCGTGAGA GCCGTGAGG GCCGTTCGA GCCGTTCGC GCCGTTCGG GCCGTTCGT GCCGTTAGA GCCGTTAGG GCGGTACGA GCGGTACGC GCGGTACGG GCGGTACGT GCGGTAAGA GCGGTAAGG GCGGTCCGA GCGGTCCGC GCGGTCCGG GCGGTCCGT GCGGTCAGA

GCGGTCAGG GCGGTGCGA GCGGTGCGC GCGGTGCGG GCGGTGCGT GCGGTGAGA GCGGTGAGG GCGGTTCGA GCGGTTCGC GCGGTTCGG GCGGTTCGT GCGGTTAGA GCGGTTAGG GCTGTACGA GCTGTACGC GCTGTACGG GCTGTACGT GCTGTAAGA GCTGTAAGG GCTGTCCGA GCTGTCCGC GCTGTCCGG GCTGTCCGT GCTGTCAGA GCTGTCAGG GCTGTGCGA GCTGTGCGC GCTGTGCGG

GCTGTGCGT GCTGTGAGA GCTGTGAGG GCTGTTCGA GCTGTTCGC GCTGTTCGG GCTGTTCGT GCTGTTAGA GCTGTTAGG Ma tutti questi sinonimi costituiscono veramente la robustezza? Si, dal punto di vista del codice genetico No, in assoluto, cio per il fenotipo. Esistono altri linguaggi che specificano alcune tra le parole sinonime al fine di trasmettere informazioni per: lo splicing il ripiegamento dellRNA il tempo di vita dellRNA il trasporto dellRNA la stabilit del DNA (organizzazione in cromatina) ? Messaggio: anche le mutazioni neutre vanno considerate come potenzialmente patogene

Recently Viewed Presentations

  • Illinois State Board of Education A New Vision

    Illinois State Board of Education A New Vision

    19 states + DC and US Virgin Islands. KY and PA are participating states. Developing common, high-quality . math . and. English language arts (ELA) tests. for . grades 3-11. Computer-based and linked to what students need to know for...
  • Introduction to Milestone - dqhg7aoeit2za.cloudfront.net

    Introduction to Milestone - dqhg7aoeit2za.cloudfront.net

    Milestone in brief. Founded in 1998. Standalone company in the Canon Group. Global leader in open platform video management software. Software sold through a network of authorized and certified partners
  • Folie 1

    Folie 1

    Wan xing tong pu juan shou . 萬姓統譜卷首 (明) Ling Dizhi凌迪知 ... Yiwen. leiju. 藝文類聚 (唐) Ouyang Xun 歐陽詢 ...
  • Scaffolds

    Scaffolds

    Pan. Reference 1926.1052(b)(1) Temporary Service Stairway - A stairway where permanent treads and/or landings are to be filled in at a later date. The pans are are just "concrete forms" that are filled with concrete after the stairs have been...
  • Introduction to Finance & Accounts - PBworks

    Introduction to Finance & Accounts - PBworks

    Introduction to Finance & Accounts BTEC Business Nationals Unit 5 - An Introduction to Accounting
  • www.alice.org

    www.alice.org

    Some of the common uses of relational expressions in Alice are: If score is greater than or equal to 10 win game. If textFromUser contains y then answer is correct. If keypress is up arrow move forward . If object...
  • 23 - Los Angeles Harbor College

    23 - Los Angeles Harbor College

    Classes of Teeth 2I, 1C, 2P, 3M Incisors Chisel shaped for cutting Canines Fanglike teeth that tear or pierce Premolars (bicuspids) and Molars Have broad crowns with rounded cusps for grinding or crushing Figure 22.10a Incisors Central (6-8 mo) Incisors...
  • Post Classical Era & The Rise and Spread of Islam

    Post Classical Era & The Rise and Spread of Islam

    Post Classical Era &The Rise and Spread of Islam. The First Global Civilization. I. Pre-Islamic Arabia. Clans. nomadic kinship clans. Shayks were leaders of tribes; warriors highly valued. ... Post Classical Era & The Rise and Spread of Islam Last...