(1)Statistica Algebrica Alberi Filogenetici Simulazioni

Testo completo

(1)Statistica Algebrica Alberi Filogenetici Simulazioni. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi. 20 Luglio 2011. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(2) Statistica Algebrica Alberi Filogenetici Simulazioni. Specie Specie Specie Specie Specie. 1: 2: 3: 4: 5:. ACGTACTACTGCAGTCCTAGCTGATCGT ... ACTGTCGATCATGCTAATCGATGCATCG ... GTCATCTACGACTACGACGCGATCGTAC ... AGATCTGCTATCAGTCATCGACGTATAA ... ACTGCACTCGGGACTCTCGCTACGACT .... Allineamento di DNA. Variabili aleatorie a valori in {A, C , G , T }.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(3) Statistica Algebrica Alberi Filogenetici Simulazioni. Specie 1. Specie 3. Specie 5. J. J J J. J J. Specie 2. J J. Specie 4 Abero Filogenetico. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(4) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Un modello statistico discreto M è un sottoinsieme del simplesso di probabilità : M ⊆ ∆n = {x ∈ Rn :. X. xi = 1, xi ≥ 0}.. i. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(5) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Un modello statistico discreto M è un sottoinsieme del simplesso di probabilità : M ⊆ ∆n = {x ∈ Rn :. X. xi = 1, xi ≥ 0}.. i. Ad esempio, se X1 , . . . , Xn sono variabili aleatorie a valori rispettivamente in [k1 ], . . . , [kn ], possiamo definire un tensore p ∈ Rk1 ⊗ · · · ⊗ Rkn ponendo pi1 ...in = P[X1 = i1 , . . . , Xn = in ], detto tensore di probabilit` a.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(6) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Un modello statistico discreto M è un sottoinsieme del simplesso di probabilità : M ⊆ ∆n = {x ∈ Rn :. X. xi = 1, xi ≥ 0}.. i. Ad esempio, se X1 , . . . , Xn sono variabili aleatorie a valori rispettivamente in [k1 ], . . . , [kn ], possiamo definire un tensore p ∈ Rk1 ⊗ · · · ⊗ Rkn ponendo pi1 ...in = P[X1 = i1 , . . . , Xn = in ], detto tensore di probabilit` a. Dato che X pi1 ...in = 1 e. pi1 ...in ≥ 0. i1 ,...,in. Q p ∈ ∆K con K = ki : ogni sottoinsieme di ∆K può rappresentare una collezione di distribuzioni per X1 , . . . , Xn . Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(7) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. X1 , . . . , Xn variabili aleatorie si dicono mutuamente indipendenti se P[X1 = i1 , . . . , Xn = in ] =. n Y. P[Xk = ik ]. ∀i1 , . . . in .. k=1. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(8) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. X1 , . . . , Xn variabili aleatorie si dicono mutuamente indipendenti se P[X1 = i1 , . . . , Xn = in ] =. n Y. P[Xk = ik ]. ∀i1 , . . . in .. k=1. Se p è il tensore di probabilit` a associato a queste variabili, questa condizione si può scrivere come p = p1 ⊗ · · · ⊗ pn, dove p k è il vettore delle probabilit` a marginali di Xk : pjk = P[Xk = j].. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(9) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. ϕ ∈ V1 ⊗ · · · ⊗ Vm si dice decomponibile se esistono vi ∈ Vi tali che ϕ = v1 ⊗ · · · ⊗ vn .. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(10) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. ϕ ∈ V1 ⊗ · · · ⊗ Vm si dice decomponibile se esistono vi ∈ Vi tali che ϕ = v1 ⊗ · · · ⊗ vn . Definizione M⊥⊥ = {p ∈ ∆K : p decomponibile} è detto modello di indipendenza.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(11) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. ϕ ∈ V1 ⊗ · · · ⊗ Vm si dice decomponibile se esistono vi ∈ Vi tali che ϕ = v1 ⊗ · · · ⊗ vn . Definizione M⊥⊥ = {p ∈ ∆K : p decomponibile} è detto modello di indipendenza. I tensori 2-dimensionali decomponibili sono le matrici di rango 1.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(12) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. ϕ ∈ V1 ⊗ · · · ⊗ Vm si dice decomponibile se esistono vi ∈ Vi tali che ϕ = v1 ⊗ · · · ⊗ vn . Definizione M⊥⊥ = {p ∈ ∆K : p decomponibile} è detto modello di indipendenza. I tensori 2-dimensionali decomponibili sono le matrici di rango 1. Definizione Sia ϕ ∈ V1 ⊗ · · · ⊗ Vn e sia {A, B} una partizione di [n] = {1, . . . , n}. Il flattening di ϕ rispetto ad {A, B} è l’immagine di ϕ (denotata con FlatA (ϕ)) tramite l’isomorfismo naturale ! O O ψ : V1 ⊗ · · · ⊗ Vn −→ Hom Va∗ , Vb . a∈A. b∈B. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(13) Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Statistica Algebrica Alberi Filogenetici Simulazioni. In pratica, un flattening è una matrice ottenuta grazie ad un ”appiattimento” del tensore. Esempio:. ϕ. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(14) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Flat1 (ϕ) Corrisponde alla partizione {1}, {2, 3}. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(15) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Flat3 (ϕ) Corrisponde alla partizione {3}, {1, 2}. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(16) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Teorema ϕ ∈ V1 ⊗ · · · ⊗ Vn è decomponibile se e soltanto se rk Flati (ϕ) ≤ 1 per ogni i = 1 . . . n.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(17) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Teorema ϕ ∈ V1 ⊗ · · · ⊗ Vn è decomponibile se e soltanto se rk Flati (ϕ) ≤ 1 per ogni i = 1 . . . n. Seguono le equazioni per il modello di indipendenza nel caso generale: M⊥⊥ = ∆K ∩ V (F ), dove F = {minori 2 × 2 dei flattening di p rispetto alle coordinate}.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(18) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Teorema ϕ ∈ V1 ⊗ · · · ⊗ Vn è decomponibile se e soltanto se rk Flati (ϕ) ≤ 1 per ogni i = 1 . . . n. Seguono le equazioni per il modello di indipendenza nel caso generale: M⊥⊥ = ∆K ∩ V (F ), dove F = {minori 2 × 2 dei flattening di p rispetto alle coordinate}. Il modello è descritto parametricamente dalla seguente applicazione: φ : ∆k1 × · · · × ∆kn −→∆K (p 1 , . . . , p n ) 7−→p 1 ⊗ · · · ⊗ p n .. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(19) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Teorema ϕ ∈ V1 ⊗ · · · ⊗ Vn è decomponibile se e soltanto se rk Flati (ϕ) ≤ 1 per ogni i = 1 . . . n. Seguono le equazioni per il modello di indipendenza nel caso generale: M⊥⊥ = ∆K ∩ V (F ), dove F = {minori 2 × 2 dei flattening di p rispetto alle coordinate}. Il modello è descritto parametricamente dalla seguente applicazione: φ : ∆k1 × · · · × ∆kn −→∆K (p 1 , . . . , p n ) 7−→p 1 ⊗ · · · ⊗ p n . i Il rango di un tensore P i ϕ è il minimo numero di tensori decomponibili ϕ per i quali ϕ = i ϕ : M⊥⊥ = {p ∈ ∆K : rk p = 1} .. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(20) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Definizione Sia M ⊆ ∆n un modello statistico. L’s-esimo modello mistura di M è ) ( s X πi p i : π ∈ ∆ s , p ∈ M . Mixts (M) = i =1. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(21) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Definizione Sia M ⊆ ∆n un modello statistico. L’s-esimo modello mistura di M è ) ( s X πi p i : π ∈ ∆ s , p ∈ M . Mixts (M) = i =1. Se M = M⊥⊥ il modello prende il nome di modello a classi latenti: corrisponde alla situazione in cui esistono delle variabili indipendenti se condizionate ad un’unica variabile nascosta.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(22) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Definizione Sia M ⊆ ∆n un modello statistico. L’s-esimo modello mistura di M è ) ( s X πi p i : π ∈ ∆ s , p ∈ M . Mixts (M) = i =1. Se M = M⊥⊥ il modello prende il nome di modello a classi latenti: corrisponde alla situazione in cui esistono delle variabili indipendenti se condizionate ad un’unica variabile nascosta. Proposizione p ∈ Mixts (M⊥⊥ ) allora rk(p) ≤ s.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(23) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Per definire modelli statistici pi` u complessi useremo i grafi: sia G = (V , E ) un grafo orientato aciclico (DAG ) e per ogni v ∈ V consideriamo una variabile aleatoria Xv . Definizione Una distribuzione di probabilit` a per {Xv }v ∈V soddisfa la proprietà locale di Markov per G se Xv ⊥⊥ Xnd(v ) |Xpa(v ). ∀v ∈ V .. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(24) Statistica Algebrica Alberi Filogenetici Simulazioni. r. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. r. r. r r. r. Grafo per il modello di indipendenza.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(25) Statistica Algebrica Alberi Filogenetici Simulazioni. r ]J J. r. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. r . J J. J. J. J. J JJ r. . ^r. -r. Grafo a stella.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(26) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Per poter sfruttare i risultati di geometria algebrica noti, cerchiamo la chiusura di Zariski dei modelli statistici.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(27) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Per poter sfruttare i risultati di geometria algebrica noti, cerchiamo la chiusura di Zariski dei modelli statistici. M⊥⊥ = Pk1 −1 × · · · × Pkn −1 ⊆ PK −1 . (Variet` a di Segre.). Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(28) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Per poter sfruttare i risultati di geometria algebrica noti, cerchiamo la chiusura di Zariski dei modelli statistici. M⊥⊥ = Pk1 −1 × · · · × Pkn −1 ⊆ PK −1 . (Variet` a di Segre.) Mixts (M⊥⊥ ) = σs (Pk1 −1 × · · · × Pkn −1 ) ⊆ PK −1 .. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(29) Statistica Algebrica Alberi Filogenetici Simulazioni. Modelli statistici discreti Modelli di indipendenza Modelli Grafici Variet` a dei Modelli Statistici. Per poter sfruttare i risultati di geometria algebrica noti, cerchiamo la chiusura di Zariski dei modelli statistici. M⊥⊥ = Pk1 −1 × · · · × Pkn −1 ⊆ PK −1 . (Variet` a di Segre.) Mixts (M⊥⊥ ) = σs (Pk1 −1 × · · · × Pkn −1 ) ⊆ PK −1 . In generale, Mixts (M) = σs (M).. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(30) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Possiamo dare un’orientazione ad un albero fissando un suo vertice r (radice) e direzionando gli archi in senso uscente. q a1 ] J J J Jq r. q a . 2. q a3. . -q v1 J J J J ^q a. 4. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(31) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Possiamo dare un’orientazione ad un albero fissando un suo vertice r (radice) e direzionando gli archi in senso uscente. q a1 ] J J J Jq r. q a . 2. q a3. . -q v1 J J J J ^q a. 4. Un modello grafico definito da un albero cos`ı orientato è determinato interamente da una distribuzione sulla radice e dalle probabilità di passaggio fra gli stati delle variabili associate ai vertici di uno stesso arco.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(32) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Possiamo dare un’orientazione ad un albero fissando un suo vertice r (radice) e direzionando gli archi in senso uscente. q a1 ] J J JA Jq r. B q a . 2. q a3. D. C -q v 1 J EJ J J ^q a 4. Un modello grafico definito da un albero cos`ı orientato è determinato interamente da una distribuzione sulla radice e dalle probabilità di passaggio fra gli stati delle variabili associate ai vertici di uno stesso arco.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(33) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Vogliamo studiare i modelli MT definiti da un albero T sotto le seguenti ipotesi:. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(34) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Vogliamo studiare i modelli MT definiti da un albero T sotto le seguenti ipotesi: T albero binario (vertici interni con valenza 3) con n foglie;. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(35) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Vogliamo studiare i modelli MT definiti da un albero T sotto le seguenti ipotesi: T albero binario (vertici interni con valenza 3) con n foglie; Variabili relative ai vertici a valori sempre nello stesso insieme [q] = {1 . . . q};. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(36) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Vogliamo studiare i modelli MT definiti da un albero T sotto le seguenti ipotesi: T albero binario (vertici interni con valenza 3) con n foglie; Variabili relative ai vertici a valori sempre nello stesso insieme [q] = {1 . . . q}; Variabili relative ai vertici interni latenti: MT ⊆ ∆qn .. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(37) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Vogliamo studiare i modelli MT definiti da un albero T sotto le seguenti ipotesi: T albero binario (vertici interni con valenza 3) con n foglie; Variabili relative ai vertici a valori sempre nello stesso insieme [q] = {1 . . . q}; Variabili relative ai vertici interni latenti: MT ⊆ ∆qn . MT è chiamato in questo caso modello filogenetico e T albero filogenetico. a filogenetica. V (T ) = MT è detta variet`. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(38) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. I modelli filogenetici sono modelli algebrici parametrici: è possibile definire una mappa polinomiale omogenea φ : ∆q × A|E | −→ ∆qn , dove A è l’insieme delle matrici di transizione associate agli archi, per cui MT = Im(φ). Inoltre, l’immagine non dipende dalla posizione della radice.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(39) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. I modelli filogenetici sono modelli algebrici parametrici: è possibile definire una mappa polinomiale omogenea φ : ∆q × A|E | −→ ∆qn , dove A è l’insieme delle matrici di transizione associate agli archi, per cui MT = Im(φ). Inoltre, l’immagine non dipende dalla posizione della radice. Ci siamo occupati del Modello Generale di Markov, in cui     X A = M ∈ Rq×q : Mij = 1, Mij ≥ 0   j. è l’insieme delle matrici stocastiche.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(40) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Per poter usare concretamente i modelli filogenetici, dobbiamo trovare equazioni che lo generino. Definizione Un polinomio f ∈ C[x1 , . . . xqn ] è detto invariante filogenetico per T se f (p) = 0, ∀p ∈ V (T ). Indichiamo con F(T ) l’insieme degli invarianti filogenetici per T .. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(41) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Supponiamo di avere a disposizione una serie di realizzazioni indipendenti di una n-upla di variabili aleatorie X1 , . . . , Xn , a valori in [q] descritte da un albero filogenetico. Teoricamente, se conoscessimo il tensore di probabilit` a p per queste variabili, troveremmo un albero i cui invarianti si annullano tutti in p.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(42) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Supponiamo di avere a disposizione una serie di realizzazioni indipendenti di una n-upla di variabili aleatorie X1 , . . . , Xn , a valori in [q] descritte da un albero filogenetico. Teoricamente, se conoscessimo il tensore di probabilit` a p per queste variabili, troveremmo un albero i cui invarianti si annullano tutti in p. In pratica, dai dati possiamo ricavare soltanto il tensore delle frequenze pˆ: pî1 ,...,in =. ♯ occorrenze di (i1 , . . . , in ) . ♯ realizzazioni totali. u ”piccoli”. Sceglieremo quindi l’albero corrispondente agli invarianti pi`. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(43) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Per ogni arco di T consideriamo la bi-partizione delle foglie indotta dalla sua cancellazione (split). p p J. JJ Jp e. p J. J. J. Jp p Jp. p. B A B A . p. Flate (p). Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(44) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Per ogni arco di T consideriamo la bi-partizione delle foglie indotta dalla sua cancellazione (split). p p J. JJ Jp e. p J. J. J. Jp p Jp. p. B A B A . p. Flate (p). Dunque rk(Flate (p)) ≤ q: un insieme di invarianti filogenetici è [ Fedge (T ) = {minori(q + 1) × (q + 1) di Flate (p)} , e. detti invarianti degli archi. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(45) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Nel caso di variabili binarie questi costituiscono l’intero insieme degli invarianti: Teorema q = 2 ⇒ F(T ) = Fedge (T ). In generale gli invarianti degli archi non definiscono interamente la varietà filogenetica.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(46) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Nel caso di variabili binarie questi costituiscono l’intero insieme degli invarianti: Teorema q = 2 ⇒ F(T ) = Fedge (T ). In generale gli invarianti degli archi non definiscono interamente la varietà filogenetica. Teorema (Casanellas, Fernandez-Sanchez 2009) Per il modello generale di Markov gli invarianti degli archi sono sufficienti alla ricostruzione filogenetica.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(47) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Algoritmo (Metodo degli Invarianti) Input: Un allineamento di dati di n variabili da un alfabeto Σ con q stati. Output: Un albero binario con n foglie.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(48) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Algoritmo (Metodo degli Invarianti) Input: Un allineamento di dati di n variabili da un alfabeto Σ con q stati. Output: Un albero binario con n foglie. Passo 1: Calcolare le probabilit` a empiriche pî1 ...in e scriverle in un tensore pˆ.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(49) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Algoritmo (Metodo degli Invarianti) Input: Un allineamento di dati di n variabili da un alfabeto Σ con q stati. Output: Un albero binario con n foglie. Passo 1: Calcolare le probabilit` a empiriche pî1 ...in e scriverle in un tensore pˆ. Passo 2: Per ogni Ti topologia di alberi binari con n foglie - determinare F(Ti ) insieme di invarianti filogenetici. - Calcolare X ti = |f (ˆ p )|. f ∈F (Ti ). Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(50) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Algoritmo (Metodo degli Invarianti) Input: Un allineamento di dati di n variabili da un alfabeto Σ con q stati. Output: Un albero binario con n foglie. Passo 1: Calcolare le probabilit` a empiriche pî1 ...in e scriverle in un tensore pˆ. Passo 2: Per ogni Ti topologia di alberi binari con n foglie - determinare F(Ti ) insieme di invarianti filogenetici. - Calcolare X ti = |f (ˆ p )|. f ∈F (Ti ). Passo 3: Scegliere Ti corrispondente al minimo ti .. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(51) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Problemi del metodo:. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(52) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Problemi del metodo: ♯ di alberi: gli alberi binari con n foglie da confrontare sono (2n − 5)!!. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(53) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Problemi del metodo: ♯ di alberi: gli alberi binari con n foglie da confrontare sono (2n − 5)!! −→ per n grande il metodo è inutilizzabile;. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(54) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Problemi del metodo: ♯ di alberi: gli alberi binari con n foglie da confrontare sono (2n − 5)!! −→ per n grande il metodo è inutilizzabile; comportamento degli invarianti: quali sono necessari per la ricostruzione? Considerarli tutti può disturbare l’identificazione?. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(55) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Un approccio alternativo è stato proposto da N. Eriksson: invece di confrontare tutti gli alberi, cerchiamo di ricavare l’albero corretto rintracciando le coppie di specie pi` u simili.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(56) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Un approccio alternativo è stato proposto da N. Eriksson: invece di confrontare tutti gli alberi, cerchiamo di ricavare l’albero corretto rintracciando le coppie di specie pi` u simili. Proposizione - Se (A, B) è uno split, rk(FlatA (p)) ≤ q; - Se (A, B) non è uno split, rk(FlatA (p)) ≥ q 2 .. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(57) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Se troviamo che una partizione del tipo {i , j}, [n] \ {i , j} è uno split, possiamo dire che le foglie i e j sono unite allo stesso vertice interno nell’albero.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(58) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Se troviamo che una partizione del tipo {i , j}, [n] \ {i , j} è uno split, possiamo dire che le foglie i e j sono unite allo stesso vertice interno nell’albero. Idea: consideriamo i flattening di questo tipo, e uniamo le coppie (i , j) per le quali rk(Flat{i ,j} (ˆ p )) ≤ q.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(59) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Se troviamo che una partizione del tipo {i , j}, [n] \ {i , j} è uno split, possiamo dire che le foglie i e j sono unite allo stesso vertice interno nell’albero. Idea: consideriamo i flattening di questo tipo, e uniamo le coppie (i , j) per le quali rk(Flat{i ,j} (ˆ p )) ≤ q. Problema: su dati reali, il rango è quasi sempre massimo.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(60) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Se troviamo che una partizione del tipo {i , j}, [n] \ {i , j} è uno split, possiamo dire che le foglie i e j sono unite allo stesso vertice interno nell’albero. Idea: consideriamo i flattening di questo tipo, e uniamo le coppie (i , j) per le quali rk(Flat{i ,j} (ˆ p )) ≤ q. Problema: su dati reali, il rango è quasi sempre massimo. Soluzione: consideriamo le coppie (i , j) per le quali (Flat{i ,j} (ˆ p )) è pi` u vicino all’insieme delle matrici di rango ≤ q.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(61) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Se troviamo che una partizione del tipo {i , j}, [n] \ {i , j} è uno split, possiamo dire che le foglie i e j sono unite allo stesso vertice interno nell’albero. Idea: consideriamo i flattening di questo tipo, e uniamo le coppie (i , j) per le quali rk(Flat{i ,j} (ˆ p )) ≤ q. Problema: su dati reali, il rango è quasi sempre massimo. Soluzione: consideriamo le coppie (i , j) per le quali (Flat{i ,j} (ˆ p )) è pi` u vicino all’insieme delle matrici di rango ≤ q. Teorema min ||A − B||F =. rk(B)≤q. s X. σi2 ,. i ≥q+1. dove σi sono i valori singolari di A ottenuti con la fattorizzazione SVD. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(62) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Algoritmo (Costruzione degli alberi tramite SVD, N.Eriksson) Input: Un allineamento di dati genomici da n specie da un alfabeto Σ con q stati. Output: Un albero binario con n foglie.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(63) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Algoritmo (Costruzione degli alberi tramite SVD, N.Eriksson) Input: Un allineamento di dati genomici da n specie da un alfabeto Σ con q stati. Output: Un albero binario con n foglie. Passo 1: Calcolare le probabilit` a empiriche pî1 ...in e scriverle in un tensore pˆ.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(64) Statistica Algebrica Alberi Filogenetici Simulazioni. Definizione del Modelli Invarianti Filogenetici Metodi di Ricostruzione. Algoritmo (Costruzione degli alberi tramite SVD, N.Eriksson) Input: Un allineamento di dati genomici da n specie da un alfabeto Σ con q stati. Output: Un albero binario con n foglie. Passo 1: Calcolare le probabilit` a empiriche pî1 ...in e scriverle in un tensore pˆ. Passo 2: Per k = n ց 4 effettuare le seguenti operazioni: - Per ognuna delle k2 coppie di specie (i , j) scrivere Flat{i ,j}(ˆ p ) e trovarne la fattorizzazione SVD. qP 2 - Scegliere la coppia rispetto alla quale i ≥q+1 σi sia minimo e unirla ad un unico vertice dell’albero. Considerare nei successivi passi queste due variabili come un’unica a valori in [mi ] × [mj ] con mi e mj stati rispettivamente di Xi e Xj . Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(65) Statistica Algebrica Alberi Filogenetici Simulazioni. Confronto fra i metodi. Per confrontare i due metodi abbiamo simulato con MATLAB dati provenienti dal modello definito da questo albero con variabili binarie. q J. J J ^q J. q. . q 6. -q. -q. J. q. . J J J ^q. Albero filogenetico usato nella simulazione.. Abbiamo effettuato 1000 simulazioni per 3 volte, ognuna con diversi parametri generati casualmente.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(66) Statistica Algebrica Alberi Filogenetici Simulazioni. Confronto fra i metodi. 100. Percentuale corretta ricostruzione. 90 80 70 60 50 40 30 20 Invarianti SVD. 10 0. 0. 1000. 2000. 3000 4000 Lunghezza sequenze. 5000. 6000. 7000. Confronto fra i due metodi con il primo set di parametri.. In questo caso le matrici di transizione sono state generate in maniera completamente casuale. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(67) Statistica Algebrica Alberi Filogenetici Simulazioni. Confronto fra i metodi. 100. Percentuale corretta ricostruzione. 90 80 70 60 50 40 30 Invarianti SVD. 20 10 0. 0. 1000. 2000. 3000 4000 Lunghezza sequenze. 5000. 6000. 7000. Confronto fra i due metodi con il secondo set di parametri.. In questo caso le matrici di transizione sono state generate nella forma 1 1 2 M + 2 Id(2), con M matrice stocastica casuale. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(68) Statistica Algebrica Alberi Filogenetici Simulazioni. Confronto fra i metodi. 100. Percentuale corretta ricostruzione. 90 80 70 60 50 40 30. Invarianti SVD. 20 10 0. 0. 1000. 2000. 3000 4000 Lunghezza sequenze. 5000. 6000. 7000. Confronto fra i due metodi con il terzo set di parametri.. In questo caso le matrici di transizione sono state generate nella forma 1 9 ` u 10 M + 10 Id(2), con M matrice stocastica casuale. E il caso pi` significativo dal punto di vista biologico. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(69) Statistica Algebrica Alberi Filogenetici Simulazioni. Confronto fra i metodi. 4 11 5 14 13 15 1 6 8 7 3 12 2 9 10 0. 1. 2. 3. 4. 5. 6. Albero ricostruito con il metodo SVD.. Metodi di Geometria Algebrica per la ricostruzione statistica degli alberi filogenetici Luigi Biondi.

(70)