Beginners Guide to TikTok for Search - Rachel Pearson - We are Tilt __ Bright...
Algoritmi bioinformatici per la classificazione sintattica delle lingue
1. 1
Università degli Studi di Trieste
Dipartimento di Ingegneria e Architettura
Laurea Triennale in Ingegneria dell’Informazione
Curriculum
Informatica
Algoritmi bioinformatici per la classificazione
sintattica delle lingue
Relatore: Prof. Andrea Sgarro
Correlatore: Prof. Alberto Casagrande
Candidato: Devis Meka
3. 3
Indice:
Introduzione 4
1.Algoritmi bioinformatici 6
1.1 Concetti generali 6
1.2 Metodi basati sui caratteri 8
1.3 Metodi basati sulle distanze 11
1.4 Metodi di consenso 13
2.Algoritmi bioinformatici nell’ambito della linguistica 14
2.1 Il problema della classificazione delle lingue 14
2.2 La Massima Parsimonia e i parametri linguistici 15
2.3 Il Metodo di Massima Verosimiglianza 20
2.4 Analisi dei risultati 23
3.Due tipi di distanze e una filosofia distance-based 26
3.1 Applicazioni di UPGMA e NJ sulle distanze di Hamming 26
3.2 Le distanze fuzzy di Hamming 32
3.3 Perche l’algoritmo NJ non funziona bene 38
4.Conclusioni 44
4. 4
1.Introduzione
Il concetto d’algoritmo è indispensabile quando si vuole trovare una soluzione ad un
problema. L’algoritmo si può definire come una sequenza d’istruzioni che si devono seguire
in modo da risolvere un problema (Jones N, Pevzner P : 2004). In altre parole, un algoritmo è
il metodo in cui un dato input si trasforma nell’output. L’input può essere per esempio una
serie di numeri interi e l’output può essere il massimo tra questi numeri. Si può dimostrare
che esistono infiniti algoritmi che risolvono lo stesso problema, ognuno dei quali avrà
bisogno di un certa quantità di tempo per dare una risposta. La complessità di un problema
è, intuitivamente, il minor tempo necessario alla soluzione di una delle sue istanze. In molti
casi, dato un problema, è possibile stabilire la sua complessità e identificare un insieme di
algoritmi che risolvono tutte le sue istanze nel minor tempo possibile. In altri casi, la
complessità del problema è ignota e, nel caso in cui algoritmi che lo risolvano siano noti, è
disponibile una sola stima per eccesso.
La Bioinformatica è una disciplina recente che ha cercato di beneficiare dei mezzi informatici
per risolvere i problemi della Biologia. Così problemi come l’analisi delle somiglianze e le
differenze tra le varie sequenze dei geni o delle proteine vengono risolti grazie agli algoritmi
bioinformatici. Alcuni di questi algoritmi prendono in input un insieme di sequenze oppure
qualche misura di distanza tra ogni coppia di sequenze e restituiscono un albero che
rappresenta delle ipotetiche relazioni di parentela tra le varie specie. Tale albero è detto
albero filogenetico. Le foglie di un albero filogenetico rappresentano le specie considerate,
mentre i nodi interni sono associati a delle ipotetiche specie progenitrici. In particolare, ogni
nodo è progenitore delle foglie del sottoalbero radicato in esso. Se due specie vengono
rappresentate da nodi che giacciono su uno stesso ramo dell’albero filogenetico, la loro
distanza genetica è il numero di nodi che li separano.
Gli obbiettivi di questa tesi saranno: verificare il fatto che i metodi basati sulle distanze
funzionano meglio dei metodi basati sui caratteri in termini di classificazione e fare un
analisi dettagliata sui pregi e difetti delle distanze di Hamming e sulle distanze fuzzy di
Hamming come strumenti di misura delle divergenze tra le lingue.
5. 5
Nel capitolo 1 viene fatto una rappresentazione generale dei metodi basati sui caratteri e dei
metodi basati sulle distanze, nonché dei metodi di consenso.
Nel capitolo2 vengono applicati i metodi basati sui caratteri su una griglia di parametri
sintattici e si prova a creare una classificazione delle lingue, ricostruendo diversi alberi
filogenetici.
Nel capitolo 3 vengono applicati gli algoritmi NJ e UPGMA prima sulle distanze di Hamming,
poi sulle distanze fuzzy di Hamming. In questo capitolo viene analizzato dettagliatamente il
funzionamento di NJ e vengono evidenziate le imprecisioni causate da questo metodo.
6. 6
Desidero ricordare tutti coloro che mi hanno aiutato nella stesura della tesi con
suggerimenti, critiche ed osservazioni: a loro va la mia gratitudine, anche se a me spetta la
responsabilità per ogni errore contenuto in questa tesi.
Ringrazio anzitutto il professor Andrea Sgarro, Relatore, ed il professor Alberto Casagrande,
Correlatore: senza il loro supporto e la loro guida sapiente questa tesi non esisterebbe.
Vorrei infine ringraziare le persone a me più care: i miei amici e la mia famiglia.
7. 7
1.Algoritmi bioinformatici
1.1 Concetti generali
I metodi che vengono utilizzati per ricostruire l’albero filogenetico sono molteplici. In base al
formato dei dati in input possiamo distinguere due sottogruppi1
:
a) Metodi basati sui caratteri
b) Metodi basati sulle distanze
I primi prendono in input un insieme di sequenze e valutano passo dopo passo ogni carattere
dell’alfabeto nucleotidico o amminoacidico, confrontando i caratteri che si trovano nella
stessa posizione in ogni sequenza. Mentre nei secondi si considera come input una matrice
di distanze, le cui componenti matriciali rappresentano le divergenze tra le differenti
sequenze.
L’input di questi metodi sarà un insieme di lingue e non un insieme di specie. Gli algoritmi
valuteranno sequenze di caratteri ‘+’, ‘-‘, ‘0’, che rappresentano rispettivamente la presenza,
l’assenza e la non applicabilità di alcune strutture sintattiche in una determinata lingua.
Queste sequenze sono state riassunte nella Figura 1. Nelle righe sono rappresentati i
parametri sintattici mentre nelle colonne le lingue da classificare.
1
Wing-Kin Sung, Algorithms in Bioinformatics, A Practical Introduction.
9. 9
1.2 Metodi basati sui caratteri
Nei metodi basati sui caratteri l’input è costituito da un insieme di sequenze di caratteri.
Questi metodi ricostruiscono l’albero filogenetico, confrontando i caratteri corrispondenti
delle sequenze. L’input è una matrice M il cui elemento nella n-esima riga e m-esima colonna
corrisponde allo stato del carattere che si trova nella posizione m della sequenza n. In base al
criterio di ottimizzazione utilizzato per ricostruire questi alberi filogenetici si possono
distinguere 3 metodi distinti:
1) Massima Parsimonia
2) Compatibilità
3) Massima Verosimiglianza
1.2.1 Massima Parsimonia
Il metodo di Massima Parsimonia probabilmente è tra i più diffusi e utilizzati tra quelli sovra
elencati. Il criterio della Massima Parsimonia afferma che tra tutti gli alberi che descrivano le
relazioni filogenetiche tra le sequenze, si deve scegliere l’albero che richiede il minor numero
di cambiamenti per spiegare la variabilità tra le sequenze. L’output di questo metodo può
essere un albero, o più di uno, con altezza pari al numero totale di cambiamenti nei rami
dell’albero. L’obbiettivo di questo metodo è proprio la minimizzazione di questa altezza.
Il processo attraverso il quale è possibile andare a determinare l’albero/gli alberi più
parsimoniosi può essere suddiviso in due problemi:
- Il piccolo problema parsimonioso (The Small parsimony problem). Presa in esame
una topologia d’albero, si vuole trovare l’altezza dell’albero e la distribuzione dei nodi
interni, che spiega l’evoluzione dell’ entità, in modo che ci sia il minimo numero di
cambiamenti. Per questo problema esistono vari algoritmi che danno una risposta in tempo
polinomiale.
10. 10
- Il grande problema parsimonioso (The large parsimony problem). Presa in esame
una matrice di caratteri M, si vuole trovare l’albero più parsimonioso che spiega questa
matrice. Questo è un problema NP-hard, 2
cioè esistono solo algoritmi che nei migliore dei
casi possono dare una risposta in tempo esponenziale. Comunque esistono diversi algoritmi
proposti per risolvere il problema, tra cui l’algoritmo di Fitch, il metodo di Hendy e Penny e
l’algoritmo approssimato.
1) Algoritmo di Fitch.
Questo algoritmo è stato proposto da Fitch e indipendentemente da Hartigan. L’algoritmo di
Fitch risolve il Piccolo Problema Parsimonioso in tempo polinomiale. Esso può essere usato
anche per risolvere il Grande Problema Parsimonioso. L’algoritmo di Fitch deve confrontare
(2*n-5)!! alberi filogenetici senza radice, dove n è il numero di sequenze di caratteri, per
trovare l’albero più parsimonioso. Questo algoritmo è basato sulla programmazione
dinamica.
In questa ricerca è stato utilizzato l’algoritmo “Pars” del software “PHYLIP 3.695”. Questo
algoritmo implementa la strategia di Wagner. Secondo Wagner, i cambiamenti tra i caratteri
sono equiprobabili in tutte le direzioni. In questo caso, ciò sta a significare che la
trasformazione +→- ha la stessa probabilità della trasformazione -→+. Questo algoritmo ci
dà la possibilità di inserire anche il simbolo ‘?’ per rappresentare quei casi dove manca
l’informazione oppure c’ è una dipendenza tra i parametri. L’albero filogenetico riprodotto
sarà senza radice. Questo problema può essere risolto usando un’entità qualsiasi come
radice. “Pars” ci offre la possibilità di mischiare anche l’ordine delle entità in input e di
decidere il numero massimo di alberi che vogliamo salvare.
2) Il metodo di Hendy e Penny
Questo metodo è stato proposto da Hendy e Penny nel 1982. Esso procede inizialmente
creando un albero costituito solo da 2 entità /specie, nel caso di un albero con radice oppure
costituito da 3 sequenze/specie nel caso di un albero senza radice. Di seguito aggiunge
un'altra entità all’ albero corrente e siccome un albero senza radice con n entità ha (2*n-3)
rami, allora l’algoritmo può inserire l’entità in qualsiasi delle (2*n-3) posizioni. In questa
maniera si riescono ad ottenere tutti gli alberi possibili che sono in numero (2*n-5)!!. L’idea
2
Graham and Foulds, 1982; Day, 1983.
11. 11
di Hendy e Penny fu di interrompere il procedimento nel caso in cui l’albero considerato
superasse l’altezza di un albero già noto. Perciò appena ciò avviene viene interrotta
l’espansione di questo albero e si torna indietro rimuovendo l’entità appena aggiunta.
Questo metodo sfrutta la strategia della ricerca in profondità. E’ un algoritmo abbastanza
lento e chiede alcuni informazioni in anticipo, per esempio le lunghezze di un certo numero
di alberi già completati e non assicura sempre la soluzione .
Nel lavoro a seguire verrà utilizzato il metodo “Penny”, un algoritmo del software “PHYLIP
3.695”, al fine di ricostruire alberi basandoci sul metodo sovra descritto. “Penny”
implementa il criterio di Wagner, non permette di mischiare l’ordine delle entità in input,
accetta il carattere ‘?’ nei casi dove non ci sia informazione ma è molto lento. Infatti per
trovare l’albero più parsimonioso con questo algoritmo si sono dovute impiegare 12 ore.
3)Algoritmo approssimato
Questo algoritmo non trova una soluzione esatta ma una soluzione approssimata. Nei
migliori dei casi si ottiene una soluzione di grado 1.55. Questo valore rappresenta il rapporto
tra il risultato dell’algoritmo e i suoi costi ottimali, nel presente studio questo algoritmo
troverà un albero che avrà altezza al massimo 1.55 volte più grande dell‘ albero più
parsimonioso. Questo algoritmo riduce il problema della ricostruzione di un albero
filogenetico con il criterio di massima parsimonia nel problema del minimo albero di
connessione, cioè di quell‘albero connesso che minimizza i costi degli archi il quale è
risolvibile in tempo polinomiale.
1.2.2 Compatibilità
Il metodo di compatibilità assume che la maggior parte dei caratteri/stati che costituiscono
le entità/specie alterino il loro valore raramente e al massimo una volta nella loro storia.
Questo metodo ricostruisce l’albero filogenetico nel quale il numero dei caratteri che
alterino il loro valore una volta è massimo. La compatibilità assume che i valori che possono
prendere i caratteri in input siano binari, cioè 1 o 0.
12. 12
1.2.3 Massima Verosimiglianza
Il metodo di Massima Verosimiglianza, diversamente dal metodo di Massima Parsimonia, usa
un modello esplicito di riferimento. Questo metodo è stato proposto da Felsenstein,
A.Edwards e E.Thompson. La matrice dell’input in questo caso si ipotizza sia il risultato di
alcuni modelli di evoluzione. L’albero che ricostruirà questo metodo sarà l’albero che meglio
spiega la matrice di input basato su questo modello di evoluzione.
In questo elaborato è stato impiegato il programma “Dnaml” del medesimo software
precedentemente indicato “PHYLIp 3.695”. Il modulo che implementa questo programma e’
il Modello Nascosto di Markov3
. Quest’ultimo permette di impostare diversi tassi di
evoluzione per le entità. In più si possono impostare anticipatamente le probabilità di
evoluzione. Nel caso specifico la scelta è ricaduta su un tasso di evoluzione costante per
tutte le lingue.
1.3 Metodi basati sulle distanze
Questi metodi, diversamente da quelli precedenti, prendono in input una matrice M
simmetrica, dove un valore Mij al i-esima riga e j-colonna corrisponde alla distanza che
l’entità i-esima ha dall’entità j-esima. Questi metodi, a partire dalla matrice M,
ricostruiscono l’albero filogenetico e siccome vengono scelte 2 entità alla volta, l’albero
ricostruito sarà binario. Esistono vari metodi basati sulle distanze che differiscono tra loro
dal modo in cui vengono scelte le entità da fondere insieme.
A seguire verranno elencati alcuni dei metodi distance-based più importanti:
1.3.1 Il metodo Unweighted Pair Group with Aritmetic Means (UPGMA)
Questo metodo si basa sul fatto che entità simili devono trovarsi vicine nell’ albero
filogenetico e sull’ approccio bottom-up, cioè risolve il problema risalendo dal basso verso
l’alto. UPGMA è un metodo ultrametrico, ossia l’albero ricostruito avrà tutti i rami di ugual
lunghezza. Il metodo usa un algoritmo iterativo, il quale in n-1 iterazioni, dove n è il numero
delle specie/entità, raggruppa ad ogni passo le 2 entità che più si assomigliano (più
3
Trattato da Felsenstein e Churchill in una pubblicazione del 1996.
13. 13
precisamente le 2 entità che hanno la distanza media più piccola). In questo modo il metodo
ricostruisce l’albero filogenetico in un tempo O(n^2)4
. L’algoritmo UPGMA è robusto ma non
sempre riesce a trovare l’albero più parsimonioso e questo accade quando l’evoluzione tra
l’entità non è uniforme.
Per implementare questo metodo è stato scelto il programma “UPGMA ” del software
“PHYLIP 3.695”. UPGMA ha la caratteristica di produrre un albero con radice senza aiuto
esterno.5
Questo programma accetta le matrici di distanze sia in forma triangolare superiore
che triangolare inferiore.
1.3.2 Il metodo di Neighbor-joining(NJ)
Questa metodica è stata proposta nel 1987 ed è simile alla precedente. NJ parte da un
albero senza radice e con una topologia a stella, dove le 3 entità scelte all’inizio non hanno
nessuna relazione tra di loro. Inseguito, proseguendo nell’iterazione si scelgono le 2 entità
che hanno distanza minore e si collegano ad un padre comune. Da questo punto le 2 entità
vanno trattate come una singola entità. NJ si basa sulla proprietà additiva, ossia la distanza
tra una coppia di foglie dell’albero deve essere uguale alla somma delle distanze tra i nodi
che costituiscono il percorso tra le foglie. La complessità di NJ è uguale alla complessità di
UPGMA, O(n^2). L’albero ricostruito dall’algoritmo NJ può avere rami di lunghezza diversa e
il fatto che le entità possano avere una evoluzione non uniforme, non è una restrizione per
questo algoritmo.
1.4 Metodi di consenso
I metodi di consenso si usano per trovare un albero di consenso partendo da un insieme di
alberi. Questi metodi sono particolarmente interessanti quando si cerchi di ottenere un
albero di bootstrapping6
da un insieme relativamente grande di alberi di partenza. Ci sono
4
Questo notazione sta ad indicare che un raddoppio della dimensione dell’input, nei casi peggiori, quadruplica
il tempo di risposta dell’algoritmo.
5
Il fatto che UPGMA consideri che tutte le lingue abbiano un tasso di evoluzione costante implica che deve
esserci un antenato comune e le lunghezze dei rami debbano essere uguali.
6
Il concetto di bootstrapping viene trattato in seguito.
14. 14
vari metodi di consenso proposti che differiscono tra di loro dal modo di scegliere i rami
dell’albero filogenetico finale. A seguire ne verranno descritti in breve:
a) La regola della maggioranza.
Questa regola è stata introdotta da Margush e McMorris nel 1981. L’albero di consenso
ricostruito basandosi su questo metodo avrà esattamente quei rami che compaiono almeno
nella metà degli alberi di partenza e si ottiene sempre un albero di consenso unico.
b) La regola stretta
Questa regola è stata introdotta da R.R.Sokol e F.J.Rohlf. L’albero di consenso che questa
regola ricostruisce contiene esattamente i rami che compaiono in tutti gli alberi di partenza.
Come nel metodo della maggioranza, l’albero ricostruito esiste sempre ed è unico.
c) La regola della maggioranza estesa
Questa regola si basa sullo stesso principio della regola della maggioranza, ma per
completare l’albero, dopo aver scelto i rami che compaiono in almeno la metà degli alberi di
partenza, usa anche gli altri rami nell’ordine di comparizione. In questo lavoro di tesi si è
scelto proprio questo metodo di consenso per trovare gli alberi di bootstrapping. Il
programma usato è stato Consense del software PHYLIP 3.695.
d) La regola della mediana
Questa regola considera le distanze tra tutte le coppie degli alberi di partenza. Per distanza
tra gli alberi si intende il numero di rami che compaiono in un albero ma non nell’altro.
L’albero di consenso proposto da questo metodo minimizza la somma delle distanze tra
tutte le coppie degli alberi. Questo albero esiste sempre ma non è unico.
15. 15
2.Algoritmi bioinformatici nell’ambito della linguistica
2.1 Il problema della classificazione delle lingue
Dal diciannovesimo secolo l’evoluzione biologica e la storia delle lingue hanno seguito strade
parallele ma con la stessa meta. L’obbiettivo comune era classificare la popolazione umana e
le lingue in famiglie genealogiche, evidenziare le relazione di parentela e trovare l’origine
comune. Questo obbiettivo ha fatto in modo che queste due discipline apparentemente
lontane, possano condividere gli stessi meccanismi e procedure di comparazione e
ricostruzione.
Per classificare le lingue ed evidenziare le relazioni di parentela, all’inizio si è investigato sugli
elementi più facilmente accessibili come gli elementi lessicali: l’insieme delle parole e i
morfemi.7
Dall’altra parte la classificazione delle lingue raramente è stata basata sulle regole
sintattiche, le quali non sono cosi immediatamente accessibili. La classificazione basata
sull’entità lessicali è stata, fondamentalmente, rappresentata dal Metodo Classico di
Comparazione e dal Metodo Multilaterale. Il primo metodo indubbiamente è stato uno dei
successi più grandi delle scienze umane e riesce a risolvere parzialmente il problema delle
classificazione delle lingue senza usare metodi sofisticati. Questo metodo è stato introdotto
da Bopp F. e Rask R. e sfrutta le relazioni lessicali e fonetiche per classificare le lingue.
Presenta però una forte limitazione in quanto la velocità di evoluzione di queste entità
lessicali fa si che non si possano recuperare relazioni in un periodo di tempo più grande di
10,000 anni (Sgarro ed altri, 2011:1).
Il Metodo Multilaterale, conosciuto anche come metodo di Greenberg (1987, 2000), si basa
nuovamente sulle entità lessicali. Ma Greenberg pensava che bisognasse fare un confronto
dell’insieme delle parole non solo su una coppia di lingue, ma su un insieme più grande di
lingue nello stesso tempo. Questo metodo in teoria può essere applicato ad ogni lingua,
indipendentemente quanto remota possa essere. Anche questa strategia, però, fallisce nel
trovare misure precise nelle somiglianze di suoni o significati.8
Per aggirare questi ostacoli, in particolare la limitazione di applicabilità e l’impossibilità di
misurare distanze esatte, si è iniziato a cercare altri strumenti e metodi. Cosi inevitabilmente
7
Longobardi C.(2009:1680).
8
Longobardi C.( 2009:1679).
16. 16
l’attenzione si è concentrata sulla sintassi ed in particolare sul Metodo Comparativo dei
Parametri(PCM). La pietra miliare in questa direzione fu la pubblicazione di
“Principles&Parameters”.9
In questa pubblicazione, i parametri vengono concepiti come
parte di una Grammatica Universale(UG) e come delle scelte aperte tra 2 valori binari.
Questo approccio verso la sintattica ha dato una svolta al problema della classificazione delle
lingue tenendo conto anche del fatto che le entità sintattiche cambiano più lentamente nel
tempo rispetto alle entità lessicali.10
Infatti i parametri sono immuni dalla selezione naturale,
al contrario delle entità lessicali che possono cambiare con il cambiamento dell’oggetto che
descrivano. I parametri sembrano essere immuni anche dal libero cambiamento individuale,
cioè dalla trasformazione, anche se piccola, che ognuno può dare alle entità lessicali come le
parole o i suoni. Nel PCM non c’è spazio per ambiguità siccome si conoscono perfettamente
le entità che vanno confrontate, diversamente dal caso delle entità lessicali.
2.2 Massima parsimonia e i parametri linguistici
In questo paragrafo si cercherà di implementare il metodo di massima parsimonia sulla
griglia dei parametri aventi a disposizione. Il metodo di MP è il metodo character-based più
facile per ricostruire alberi filogenetici ed è stato proposto per la prima volta in Edwards e
Calvalli-Sforza nel 1963. Il criterio della Massima Parsimonia si basa sul trovare l’albero che
richiede il minimo numero di cambiamenti.11
Ossia la Massima Parsimonia MP valuta diversi
alberi e fornisce l’albero (o gli alberi) che minimizza il numero dei cambiamenti di stati nei
suoi rami. Nel trovare l’albero oppure gli alberi che minimizzano il numero di cambiamenti,
questo algoritmo non solo prova ad aggiungere nuove foglie nei rami esistenti dell’albero,
ma cerca anche di aggiungerle alla fine dei nuovi rami.11
Dall’ altra parte questo metodo non
usa tutte le sequenze che vengono date in input, poiché alcune le considera senza
informazione.
Perché i parametri? I parametri sono universali e anche binari (al massimo ternari, nei casi
dove manca l’informazione o c’è una relazione di dipendenza). In questo modo, avendo una
lista di parametri universali che possono prendere solo due valori, si ha la possibilità di fare
misurazioni precise tra le lingue, usufruendo degli strumenti matematici e degli algoritmi
9
Chomsky, 1981.
10
Longobardi&Guardiano, 2009:1694.
11
J. Felsenstein, 2008.
17. 17
bioinformatici. Questi parametri sono infatti applicabili a qualsiasi lingua,
indipendentemente se è una lingua recente o remota.
MP e i parametri sembrano fatti l’uno per l’altro, ma non risulta essere così. MP assume
infatti che i parametri siano indipendenti tra di loro in modo che possano essere considerati
informativi12
. Dall’ altra parte i parametri linguistici hanno un grado di correlazione tra di
loro e questo problema si rifletterà nell’albero filogenetico ricostruito.
Nel caso trattato in questo studio, i parametri prendono i valori da un alfabeto ternario. Il
caso ‘0’ verrà escluso dalla computazione siccome è un caso dove non è presente
informazione, oppure il valore è prevedibile. Questo vuol dire che le coppie dove compare
almeno un simbolo ‘0’ non influenzeranno sulla parsimonia dell’albero. Ai fini della
computazione, anche le coppie dove appare almeno un ‘?’ non avranno effetto sulla
parsimonia dell’albero.
Facendo riferimento alla Tabella 7, dove nelle righe compaiono le lingue e nelle colonne
compaiono i vari parametri, ed utilizzando il programma “Seeqboot” del software Phylip
3.695, si sono ricostruite 2999 matrici di bootstrapping. Il bootstrapping è una tecnica
statistica di ricampionamento con riemissione che si usa per approssimare la distribuzione
campionaria di una statistica. Gli alberi ricostruiti dai metodi basati sui caratteri oppure sulle
distanze possono essere instabili, infatti se si rimuovono alcuni caratteri o se ne aggiungono
altri, è possibile avvenga un cambiamento della loro struttura. Il bootstapping viene
utilizzato appunto per fare diventare stabili questi alberi.
Una matrice di bootstrapping è una matrice che ha lo stesso numero di colonne della
matrice originaria. Per costruire questa matrice si scelgono casualmente diverse colonne
dalla matrice originaria, una o più volte. Queste matrici serviranno come input per il
programma “Pars” dello stesso software. In questo modo sono stati ricostruiti almeno 30000
alberi usando il metodo di Massima Parsimonia. Il fatto che ci siano almeno 30000 alberi,
partendo da 2999 matrici di dati, si spiega con la proprietà di questo metodo, cioè che
spesso non torna un albero unico ma un insieme di alberi parsimoniosi.
12
MP considera non informativi i parametri che hanno per esempio solo un carattere ‘+’ in confronto con un
grande numero di ‘-‘ e ‘0’.
18. 18
La figura raffigurante tutti gli alberi trovati non è stata riportata in questa tesi per mancanza
di spazio, ma partendo da questi alberi e usando il programma “Consense ” dello stesso
software è stato possibile ottenere un albero di consenso costruito basandosi sulla strategia
della “Regola della maggioranza estesa” (Figura 2). Questa strategia sceglie, inizialmente,
quei rami dall’insieme degli alberi che compaiono almeno nella metà delle volte e
successivamente, in base alla frequenza, sceglie quei rami che completa l’albero. I numeri
presenti sui rami indicano quante volte sono comparse su un insieme di 2999 alberi. Come si
può osservare la coppia Polacco-Russo la troviamo in 1369 alberi mentre la coppia formata
dalle lingue Hindi e Marathi compare in 2679 alberi. Questo albero in generale è coerente
con quello che si sarebbe dovuto ottenere. In questo modo i sottogruppi delle lingue slave
viene correttamente evidenziato con il Polacco, raggruppato a sua volta al Russo. Il Rumeno
viene rappresentato come esterno alle lingue Latine ed anche questo risulta essere corretto.
Ma dall’altra parte MP comporta alcuni imprecisioni. Ad esempio, come si può osservare
nella Figura 2 le lingue Germaniche vengono unite con le lingue Celtiche ed inoltre i dialetti
italiani (Siciliano, Salentino e Calabrese) vengono fusi insieme con i dialetti Greci (Bovese e
Grico) ed il Greco.
20. 20
Per avere una panoramica più chiara su come applicare la filosofia character-based in
generale ed il metodo della massima parsimonia in particolare sui parametri linguistici, si è
cercato di ricostruire anche un albero di consenso usando l’algoritmo di Hendy e Penny,
partendo da un insieme iniziale di 1000 alberi. L’albero ricostruito viene rappresentato nella
Figura 3. Di nuovo i numeri sui rami mostrano quante volte gli stessi rami compaiono su un
insieme di 1000 alberi di partenza. Questo metodo fa uso dell’algoritmo “branch and bound”
che non garantisce di trovare l’albero più parsimonioso (J.Felsenstein, PHYLIP) e risulta
essere abbastanza lento. Solo per un insieme di 10 entità, se il procedimento viene eseguito
fino in fondo, si riescono a ricostruire 34,459,425 alberi. Il particolare software, che è stato
utilizzato, è dipendente dall’ordine in cui le lingue compaiono in input. Questo algoritmo
inizialmente sceglie due lingue casualmente, e le unisce in un unico ramo. Dopo di che prova
ad aggiungere le altre lingue in ordine dell’input, nella posizione migliore che possa
trovare13
. Per esimere tale dipendenza, prima della computazione è stato eseguito un
mescolamento nell’ordine dell’input per 1000 volte. In questo caso come radice esterna è
stata utilizzata la lingua Basca.14
L’albero ricostruito in generale, si comporta meglio della MP. Infatti, i dialetti italiani in
questo caso vengono correttamente raggruppati con le lingue romane. Dall’altra parte
questo algoritmo distingue bene le lingue Germaniche da quelle Celtiche. Ma anche in
questo caso sono presenti alcune imperfezioni. Ad esempio il Rumeno, anche se nella
posizione più esterna, viene raggruppato con il Greco, ed i suoi dialetti con le lingue Latine.
Una leggera imprecisione compare anche nel sottogruppo dei dialetti italiani dove il Siciliano
viene raggruppato con l’Italiano, ed il Calabrese compare nella posizione più esterna.
I risultati ottenuti finora, basandosi sulla Massima Parsimonia sono abbastanza soddisfacenti
e coerenti con ciò che concerne la classificazione delle lingue Indo-Europee, ma rimangono,
comunque, alcune imprecisioni.
13
Felsenstein, 2008.
14
Il Basco è stato selezionato come radice esterna perché è una lingua isolata che si differenzia da tutte le
lingue indoeuropee. Il Basco, inoltre, viene considerato come una lingua senza legami con le altre lingue.(Trask,
R.L :1997).
21. 21
2.3 Il metodo di Massima Verosimiglianza
Per verificare se le imprecisioni siano frutto della Massima Parsimonia in particolare oppure
dei metodi basati sui caratteri in generale, è stato eseguito un terzo tentativo: un albero di
consenso basato sul metodo di Massima Verosimiglianza(Figura 3). All’inizio sono state
ricostruite 2999 matrici di bootstrapping, le quali sono servite come input al software DNAml
dell’PHYLIP, al fine di poter costruire 2999 alberi di Massima Verosimiglianza. Questo
algoritmo si basa sul Modello Nascosto di Markov (Hidden Markov Model). A seguito è stato
determinato un albero di consenso con la Regola della Maggioranza estesa, dove i numeri sui
rami mostrano quante volte quest’ultimi compaiano su un totale di 2999 alberi. I vantaggi
della Massima Verosimiglianza sono individuabili in questo metodo in quanto risulta ben
fondato statisticamente e considera come informativi tutte le sequenze dell’input
(F.Opperdoes:1997). Dall’altra parte questo metodo è relativamente lento e dipende dal
modello scelto come riferimento.
23. 23
Figura 4. Albero di consenso basato sul metodo di Massima Verosimiglianza
24. 24
2.4 Analisi dei risultati
Come si osserva dai tre alberi ricostruiti con i metodi character-based (Figura 2, Figura 3,
Figura 4), le differenze tra di loro sono minime. Il primo albero di consenso costruito con il
metodo di massima parsimonia, utilizzando il software “Phylip 3.695” e partendo da più di
30000 alberi iniziali, riporta in modo corretto la posizione della lingua Bulgara nel
sottogruppo delle lingue slave. Risulta essere corretta anche la posizione della lingua
Rumena. Le imprecisioni presenti sono il mescolamento dei sottogruppi delle lingue
Germaniche e Celtiche ed il collasso in un unico sottogruppo dei dialetti greci e di quelli
italiani.
Il mescolamento tra le lingue Germaniche e Celtiche può essere stato causato da un certo
numero di parametri che i due sottogruppi condividono. Per esempio se prendiamo l’Inglese
ed il Gallese come rappresentanti dei due sottogruppi, solo i seguenti parametri non
vengono condivisi:
Le rimanenti coppie dei parametri sono uguali oppure presentano almeno un ‘0’. Questo
numero elevato di parametri uguali può essere conseguenza di uno sviluppo parallelo di
questi sottogruppi15
. Anche il mescolamento tra i dialetti Greci, il Greco ed i dialetti italiani
può essere stata conseguenza di un’affinità tra questi due sottogruppi. Infatti dalla griglia è
possibile osservare che il numero dei parametri non condivisi risulta essere molto piccolo16
.
In conclusione possiamo affermare che il numero ridotto dei parametri, nonché l’effetto
dello sviluppo parallelo tra alcuni sottogruppi, rendono difficile la distinzione tra tali
sottogruppi.
Il secondo albero, ricostruito col metodo di Hendy e Penny, classifica erroneamente il
Rumeno con i dialetti greci. Questa imprecisione può essere frutto del fatto che il Rumeno è
15
Questi sottogruppi sono stati sempre in contatto uno con l’altro, come ad esempio durante l’invasione
Scandinava. Ad oggi il contatto e i conflitti tra l’Inglese e le lingue Celtiche è un dibattito che risulta essere
ancora aperto.
16
Prendendo ad esempio il Siciliano ed il Greco come rappresentanti di ciascun sottogruppo, il numero dei
parametri dove divergono i due e’ 4.
25. 25
la lingua più esterna del sottogruppo Latino cosi come può essere dovuto anche all’usuale
problema del numero ridotto dei parametri in input.
Anche l’albero ricostruito con il metodo della Massima Verosimiglianza rappresenta alcuni
imprecisioni abbastanza evidenti. Infatti siamo in presenza di un mescolamento tra le lingue
Germaniche e quelle Celtiche, come nel caso dell’albero di Massima Parsimonia. Inoltre il
Farsi viene raggruppato dentro questo gruppo mescolato in 893 alberi su 2999, andando ad
aumentare l’imprecisione di questo metodo. Per il resto l’albero rappresenta abbastanza
bene i sottogruppi e colloca correttamente il Rumeno con le lingue Latine, come l’elemento
più esterno. La stessa cosa vale anche per il Bulgaro presente nel sottogruppo delle lingue
slave.
La collocazione della lingua Farsi nel sottogruppo delle lingue Celtiche può essere
conseguenza di un fenomeno definito come “Long branch attraction”17
. Questo fenomeno
viene descritto come la tendenza di 2 sequenze che evolvono rapidamente e diversamente
dalle altre sequenze, di collassare in un unico nodo. In questo caso le 2 sequenze che
vengono unite non hanno un’affinità tra loro, ma sono presenti nello stesso ramo solo a
causa di questa attrazione tra i rami lunghi. Nel caso specifico, il Farsi è la lingua più esterna
all’insieme delle lingue Indo-Europee. Anche il sottogruppo delle lingue Celtiche si trova
all’estremità di questa classificazione. Queste lingue collassano in un unico gruppo 893 volte
su un totale di 2999 alberi.
Gli errori presenti anche nell’ultimo albero, come si può osservare dalla Figura 4, non sono
dovuti solo alla Massima Parsimonia in particolare ma ai metodi basati sui caratteri in
generale. Ma quali possono essere i fattori che generano questi comportamenti?
La risposta a questa domanda deve essere cercata nell’insieme dei parametri che sono stati
utilizzati per ricostruire questi alberi. Essi rispettano alcuni criteri e sono scelti con cura
(Longobardi&Guardiano:2009, Sgarro e collaboratori: 2011). Cosi i parametri linguistici
possono avere delle dipendenze parziale ma che siano note. Inoltre i parametri devono
essere il frutto di una quantità grande di dati intersecati. Ma cosa si aspetta in input un
metodo basato sui caratteri? Secondo J. Felsenstein (1986-2008), nell’ ipotesi della Massima
Parsimonia del software PHYLIP, deve essere garantita l’indipendenza evolutiva tra i
17
L’attrazione tra i rami lunghi, trattato da Felsenstein nel 1978, Gribaldo e Philippe nel 2002.
26. 26
parametri ed inoltre il numero dei parametri deve essere relativamente grande in modo che
si possa ricostruire un albero affidabile.
I parametri di questo lavoro rappresentano legami di dipendenza, infatti i simboli ‘0’ e ‘?’
rappresentano quei casi dove non ci sia informazione, oppure quel parametro per una
precisa lingua dipende dal valore di un altro parametro. Nella Tabella1 vengono
rappresentati 4 parametri e 3 lingue.
Tabella 1. La dipendenza tra i parametri
Il valore del parametro 11 dipende direttamente dai parametri 5,6 e 8. Come si può
osservare anche in Tabella1, nel caso del Sloveno, se il parametro 5 non è ‘-‘, oppure il
parametro 6 non è ‘-‘ o il parametro 8 non è ‘+’, allora il parametro 11 non potrà essere
valutato e verrà posto a ‘0’. Perciò un unico cambiamento dà luogo ad una reazione a catena
che tende a cambiare la parsimonia dell’albero.
Usando la notazioni standard delle proposizioni logiche, una regola per il parametro 11
potrebbe essere18
:
18
Sgarro ed altri, 2011:11.
Parametri Norwegian Serbo-Croat Slovenian
5.+/- feature spreadN + + +
6.+/-numb.on N + + +
8.grammar.def + 0 0
11.grammar.dist.art - 0 0
27. 27
3. Due tipi di distanze e una filosofia distance-based
In questo capitolo si cercherà d’implementare i metodi basati sulle distanze nell’ ambito
della linguistica al fine di riuscire a classificare le lingue Indo-Europee. Poiché questi metodi
chiedono in input una matrice simmetrica costituita dalle distanze tra le entità (lingue nel
nostro caso), a partire dalla Tabella 7 si andranno a misurare 2 tipi diversi di distanze:
distanza di Hamming normalizzata e una distanza fuzzy di Hamming. In base a queste
distanze, usufruendo degli algoritmi distance-based, verranno ricostruiti vari alberi
filogenetici e infine verranno analizzati i risultati.
3.1 Applicazioni di NJ e UPGMA sulle distanze di Hamming
La distanza di Hamming tra 2 stringhe binarie della stessa lunghezza è il numero delle
posizioni nelle quali le 2 stringhe differiscono tra di loro. La distanza di Hamming è una
distanza metrica e come tale soddisfa anche la disuguaglianza triangolare:
dove a,b,c sono delle stringhe binarie.
Nel nostro caso l’alfabeto dei caratteri non è un alfabeto binario ma è un alfabeto ternario
{+,-,0}. Basandosi sulla Tabella 1, un carattere ‘+’ nella i-esima riga e j-esima colonna vuole
significare che il parametro alla posizione i-esima e condiviso dalla lingua nella posizione j-
esima, un carattere ‘-‘ vuole dire che la lingua j-esima non rispetta il parametro i-esima
mentre un carattere ‘0’ significa che è impossibile assegnare uno tra i valori ‘+’ o ’-’ oppure il
valore è prevedibile. Le coppie dei caratteri dove appare almeno uno ‘0’, indipendentemente
dal carattere con il quale viene associato, verranno esclusi dal calcolo della distanza di
Hamming tra le coppie delle lingue.
Nella seguente griglia sono state prese 2 lingue come esempio: l’Italiano e il Francese.
Indicando con ‘d’ il numero delle posizioni dove le 2 lingue differiscono, con ’n’ il numero
totale dei parametri e ‘z’ le posizioni dove compare almeno un ‘0’, la distanza di Hamming
normalizzata risulterà essere:
28. 28
In questo caso d = 2, z = 14 e n = 56. La distanza di Hamming normalizzata sulle posizioni
sani sarà 0,0476. La matrice completa con le distanze tra tutte le coppie è presentata nelle
Figura 5, Figura 6 e Figura 7. Questa matrice è simmetrica e la diagonale principale
rappresenta le distanze identità.
Tabella 2. Griglia dei parametri per l’Italiano ed il Francese
Figura 5. La matrice delle distanze di Hamming tra le coppie delle lingue.
Ita + + + - + + + + + - - - 0 - - + - + 0 - + + + 0 + 0 + -
Fra + + + - + - + + + 0 - - 0 - - + - 0 0 - + + + 0 + 0 + -
Ita + - + - - - + 0 - 0 - - - 0 + + - - - + 0 0 0 0 0 - - +
Fra + - + - - + + 0 - 0 - - - 0 + + - - - + 0 0 0 0 0 - - +
29. 29
Figura 6. Matrice delle distanze di Hamming tra le coppie delle lingue
Figura 7. Matrice delle distanze di Hamming tra le coppie delle lingue
30. 30
Nella Figura 8 viene rappresentato un albero filogenetico ricostruito basandosi sul metodo
UPGMA. Questo metodo è un metodo tipico di clustering19
e unisce in un unico nodo quelle
entità che minimizzano la distanza media tra di loro costruendo un albero con radice e
binario. Yu-Rong Ch.(2012:1) . Dall’albero si vede che questo metodo dà i risultati più
soddisfacenti fin adesso. Tutti i sottogruppi sono ben distinti, con il Rumeno nella posizione
più esterna delle lingue romane, il Bulgaro nella posizione più esterna delle lingue slave del
sud, il Sloveno che giustamente viene unito con il Serbo-Croato(709 volte su 1000 alberi), le
lingue germaniche sono distinte dalle lingue Celtiche e i dialetti Greci sono correttamente
rappresentati. Anche i dialetti italiani sono ben collocati, con l’Italiano esterno al
sottogruppo. I numeri sui rami come sempre indicano il numero di volte che gli stessi rami
compaiono in un insieme di 1000 alberi. Per arrivare a questo albero ho usato la Regola della
Maggioranza estesa.
19
Il metodo di clustering procede accoppiando ad ogni iterazione due diverse specie che hanno la minima
distanza tra di loro.
33. 33
Nella Figura8 viene rappresentato un altro albero di consenso, questa volta ricostruito con il
metodo di Neighbor-Joining, il quale non assume che ci sia un tasso di evoluzione uguale per
tutte le lingue, e di conseguenza l’albero ricostruito non sarà ultrametrico. Questo metodo è
piu veloce dell’ UPGMA ed accetta anche valori di distanze negativi. NJ funziona bene
quando il tasso di evoluzione da un’entità ad un’altra e molto diverso. ( Felsenstein.J,
2008:PHYLIP). Di nuovo questo albero è un albero di consenso ricostruito con la Regola della
Maggioranza estesa e partendo da 2999 alberi.
Come si vede dall’albero,NJ funziona relativamente bene ma rispetto UPGMA presenta
alcune imprecisioni.
3.2 Le distanze fuzzy di Hamming
La distanza fuzzy di Hamming20
, si può considerare come una estensione della distanza di
Hamming ‘classica’. Date 2 stringhe della stessa lunghezza con caratteri da un alfabeto
ternario {+,-,b}, dove b rappresenta il caso della mancanza dell’informazione oppure il
risultato è prevedibile, per trovare la distanza fuzzy di Hamming, diversamente da come
abbiamo fatto prima, non possiamo più ignorare le posizioni dove compare almeno una ‘b’.
A questi posizioni gli daremmo un peso specifico ‘w’ preso dall’intervallo continuo [0,1]. Il
caso particolare quando w=1/2 rappresenta quella che si chiama la distanza fuzzy di
Hamming. In altre parole questo vuol dire che, ogni volta che in una coppia di caratteri che
confrontiamo,compare almeno un zero (b) si aumenta il numero di differenze con 0,5.
La scelta particolare w=0,5 e in generale w>=0,5 dipende dal fatto che al di sotto di questo
valore, la proprietà triangolare non vale ed l’uso dei algoritmi come UPGMA e NJ può dare
risultati errati(Bortolussi, L., Sgarro, A., 2007:11).
La distanza fuzzy di Hamming rispetta la disuguaglianza triangolare (Sgarro, 2007:2 ) ed e ‘
stata usata in precedenza dal linguista Muljačić per classificare le lingue romane nel 1967.
In questo paragrafo io proverò a fare la stessa cosa con le lingue Indo-Europee, ricostruendo
alberi filogenetici basandomi sugli algoritmi distance-based e usando proprio le distanze
20
Sgarro Distance, come nel Dictionary of Distances, Deza E., Deza M. M;
34. 34
fuzzy di Hamming. Riprenderò le 2 lingue usate in precedenza, l’Italiano e il Francese e
misurerò la distanza fuzzy di Hamming.
Ita + + + - + + + + + - - - 0 - - + - + 0 - + + + 0 + 0 + -
Fr
a
+ + + - + - + + + 0 - - 0 - - + - 0 0 - + + + 0 + 0 + -
Ita + - + - - - + 0 - 0 - - - 0 + + - - - + 0 0 0 0 0 - - +
Fr
a
+ - + - - + + 0 - 0 - - - 0 + + - - - + 0 0 0 0 0 - - +
Tabella 3. La griglia dei parametri per l’Italiano ed il Francese
Come prima, sia ‘d’ il numero dei caratteri dove differiscono le 2 lingue escludendo le
coppie dove appare almeno un 0 , ’b’ il numero delle coppie dove appare almeno un
carattere 0. Nel nostro caso d=2, b=14. Siccome i caratteri ‘0’ devono essere pesati con
w=0,5 allora il valore totale del loro contributo sarà 7. La distanza fuzzy di Hamming sarà:
La matrice completa con tutte le coppie delle distanze tra le lingue è rappresentata nella
Tabella3. In questo caso le distanze identità che si trovano nella diagonale principale, cioè
d(x,x) dove ‘x’ è una qualsiasi lingua, sono forzate a 0. Infatti la distanza fuzzy di Hamming
viola uno dei criteri per essere una pseudo-distanza metrica : si può avere una distanza
identità strettamente maggiore di zero. (Sgarro, 2007:8).
Ma questo fatto è irrilevante ai fini del nostro scopo. La matrice è stata rappresentata nella
forma triangolare superiore .
La distanza fuzzy di Hamming è più recente ed è stata introdotta per correggere un
inconvenienza della distanza di Hamming normale. Quest’ultima fa delle misurazioni
assolute senza tener conto della vicinanza o del quasi uguale. Mentre la distanza fuzzy di
Hamming considera anche la vicinanza tra due stringhe, con distanze minori alle stringhe più
vicine. Per questo motivo Muljačić ha scelto questa distanza per fare la sua classificazione,
dando peso ai casi “parziali”. Ma diversamente dal caso di Muljačić dove si fa la
35. 35
comparazione basandosi sulle entità lessicale21
e il fatto di somiglianze parziali ha
significato, nel nostro caso i caratteri ‘0’ stanno a significare una mancanza d’informazione
oppure una dipendenza dei parametri.
Tabella 4. Le distanze fuzzy di Hamming tra tutte le coppie.
Nella Figura10 viene rappresentato l’albero di consenso per il metodo Neighbor-Joining
basato sulle distanze fuzzy di Hamming. Questo metodo non fa una ricostruzione abbastanza
accurata come UPGMA ma ricompensa questa imprecisione con la sua velocità di esecuzione
(Felsenstein, 2008 : PHYLIP). Inizialmente, partendo dalla matrice originaria, vengono
ricostruite 100 matrice di bootstrapping. In seguito vengono ricostruite 100 alberi
filogenetici basandosi sul metodo di Neighbor-Joining e infine viene trovato l’albero di
consenso in base alla Regola di Maggioranza estesa. Viene usato il Basco come radice
dell’albero.
21
Sgarro ed altri, 2011.
36. 36
Come si vede nella Figura 10 ci sono alcune imprecisioni in confronto allo stesso metodo
basato sulle distanze di Hamming classica. NJ sulle distanze fuzzy classifica in modo errato il
Rumeno unendolo con il Greco ed i suoi dialetti(38 volte su 100 alberi), cosi come classifica
in modo errato anche il Bulgaro come l’elemento più esterno di questo maxi-gruppo di
lingue Latine e Greche(25 volte su 100 alberi). Quest’ultimo errore può essere spiegato con il
fatto che il Bulgaro è la lingua più esterna del sottogruppo delle lingue slave e dall’altra parte
il Bulgaro è attratto dal Rumeno. Ma queste imprecisioni sono dovute al metodo specifico
oppure alle distanze fuzzy che non rappresentano correttamente le distanze tra le lingue?
Per rispondere a questa domanda viene applicato sulle stesse distanze fuzzy il metodo
UPGMA(Figura 11). Questo metodo ha funzionato molto bene con le distanze classiche ma
con le distanze fuzzy le cose non vanno cosi bene. L’albero di consenso con il metodo
UPGMA partendo da 100 alberi iniziali classifica in modo errato il Bulgaro raggruppandolo
addirittura con le lingue germaniche (45 volte su 100 alberi), mentre vengono confermate le
coppie Serbo-Croato con lo Sloveno(74/100), il Rumeno come elemento esterno delle lingue
romane ed il Farsi come l’elemento più esterno della classificazione(90/100 alberi). Questo
albero riesce anche a distinguere le lingue nord-germaniche dalle lingue germaniche
dell’ovest,con il Norvegese che viene raggruppato con il Danese e l’Islandese,e l’Inglese con il
Tedesco come lingue esterne a queste sottogruppo. Ma come ho sottolineato l’errore più
grave resta la classificazione del Bulgaro con quest’ultimo sottogruppo.
39. 39
3.3 Perché l’algoritmo NJ non funziona bene?
Se vengono confrontati gli alberi ricostruiti dai metodi NJ e UPGMA sulle distanze di
Hamming e quelle fuzzy, si vedono delle piccole differenze. Cosi partendo con l’algoritmo
Unweighted Pair Group Method with Arthimetic Mean , l’albero sulle distanze di Hamming si
comporta relativamente meglio di quello basato sulle distanze fuzzy. In particolare la
posizione del Bulgaro è sbagliata. Il Bulgaro viene raggruppato con le lingue Germaniche,
invece che con le lingue Slave come succede con le distanze di Hamming “classiche” .
Nella Tabella 4 ho provato a confrontare il Bulgaro con altre lingue Slave e Germaniche, in
termini di distanze. Le distanze sono calcolate come la media della distanze del Bulgaro da
ogni lingua del rispettivo sottogruppo.
Tabella 5. Confronto tra 2 tipi di distanze.
Come si vede da questa tabella, la situazione cambia con le distanze fuzzy. Cosi nel caso delle
distanze di Hamming “classica”, il Bulgaro è più vicino alle lingue Slave rispetto alle lingue
Germaniche. Mentre nel caso delle distanze fuzzy, il Bulgaro è più vicino alle lingue
Germaniche che quelle Slave. Il motivo di questo ribaltamento lo possiamo trovare nella
Tabella1 dei parametri. Cosi i parametri 7, 8, 11, 12, 13 e 14 per quanto riguarda le lingue
Slave prendono il valore ‘0’. Questi parametri fanno si che il Bulgaro sia più distante dalle
lingue Slave piuttosto che dalle lingue Germaniche. Questo è il motivo della classificazione
errata del Bulgaro nell’albero UPGMA delle distanze fuzzy.
Se facciamo un confronto tra i due algoritmo basati sulle distanze, indipendentemente dalle
distanze usate, si vede che UPGMA funziona leggermente meglio di NJ. Cosi il Neighbor-
Joining sulle distanze di Hamming “classiche” classifica erroneamente il Bulgaro con le lingue
Indo-Iraniane invece che con le lingue Slave. Mentre il Neighbor-Joining sulle distanze fuzzy
fa ancora peggio, poiché classifica erroneamente sia il Bulgaro che il Rumeno con i dialetti
greci. Ma in questo caso, diversamente da prima, la causa principale di questi imprecisioni e
Lingua Bulgara Lingue Slave Lingue Germaniche
Distanza di Hamming 0,1102 0,1532
Distanza fuzzy di Hamming 0,2633 0,2321
40. 40
l’algoritmo stesso. Per avere una spiegazione di questo comportamento viene preso un
insieme di lingue piccolo e viene implementato sia il metodo di NJ, sia il metodo UPGMA
basandosi sulle distanze fuzzy di Hamming. Cosi vengono scelto le lingue latine, i dialetti
greci, il Rumeno ed il Bulgaro come input. La matrice delle distanze è rappresentato nella
Tabella In questo caso le distanze sono calcolate come la media delle distanze tra il Rumeno,
il Bulgaro e le singole lingue dei sottogruppi.
Lingua Rumeno Lingue latine Dialetti grechi Bulgaro
Rumeno 0.0 0.249 0.2827 0.2946
Lingue latine 0.2493 0.0 0.2864 0.2640
Dialetti grechi 0.2827 0.2864 0.0 0.3243
Bulgaro 0.2946 0.2640 0.3243 0.0
Tabella 6. Le distanze fuzzy iniziali.
ll Rumeno è l’unica lingua del blocco dell’Est che è parte del sottogruppo delle lingue latine
ed per secoli è stata isolata dallo sviluppo del mondo Neolatino. Nel corso della storia, il
Rumeno è stato influenzato da un certo numero di lingue e di culture. Cosi le lingue slave, la
lingua Turca, l’Albanese, la lingua Greca, l’Ungherese ma soprattutto le lingue latine hanno
dato il loro contributo nella trasformazione del Rumeno, una trasformazione che non è
ancora finita(Niculescu A.,1981). Questa diversità si traduce in difficoltà di classificazione
negli alberi filogenetici.
Neighbor-Joining usa un algoritmo iterativo di clustering per ricostruire l’albero. Questo
metodo parte da un albero senza radice a topologia a stella ed unisce ad un padre comune
quelle lingue che hanno la distanza minima. Ma siccome questo algoritmo considera anche
entità che hanno un tasso di evoluzione molto diversa, può non bastare cercare tra le foglie
più vicine in questa matrice. Può succedere che si abbiano due foglie vicine ma la distanza
41. 41
tra una delle due entità e un'altra foglia sia più piccola22
. Infatti NJ non usa questa matrice
direttamente ma ne ricostruisce un’altra. La nuova matrice ricostruita è rappresentata nella
Figura 6. Per arrivare a questa matrice, l’algoritmo NJ prima calcola la divergenza per ogni
lingua, cioè la somma delle distanze per ogni riga . La matrice delle divergenze è
rappresentata nella Tabella6 mentre la formula per ricavare questo divergenze è:
Dove N è il numero delle lingue.
Tabella 7. Le divergenze delle lingue.
In un passo successivo viene calcolato la matrice finale. Per calcolare, per esempio, la
distanza finale tra la lingua Rumena e i dialetti greci occorre trovare la differenza tra la
distanza iniziale e la somma delle divergenze. In questo modo si trovano le distanze tra tutte
le coppie.
Tabella 8. Le distanze fuzzy finali
Da questa matrice si possono scegliere le coppie che hanno la distanza più piccola le quali
andranno unite in un unico nodo. Come si vede le coppie con la distanza più piccola sono il
22
Questo può succedere quando le lunghezze dei rami sono molto diverse.
Rumeno Lingue latine Dialetti grechi Bulgaro
0.4133 0.3998 0.4467 0.4414
Lingua Rumeno Lingue latine Dialetti grechi Bulgaro
Rumeno 0.0
Lingue latine -0.5638 0.0
Dialetti grechi -0.5773 -0.5601 0.0
Bulgaro -0.5601 -0.5772 -0.5638 0.0
42. 42
Rumeno e i Dialetti Grechi, e l’algoritmo le classifica insieme . Da questo punto in poi, queste
due coppie saranno un’unica unita. Quindi il procedimento viene ripetuto di nuovo, fino a
trovare due elementi. L’albero ricostruito viene rappresentato nella Figura 12. La lingua
Basca viene usata come radice dell’albero. I numeri sui rami indicano in quale passaggio
dell’algoritmo vengono uniti i seguenti rami.
Figura12. Albero NJ sulle distanze fuzzy
Come si vede il Rumeno viene classificato in modo errato con i dialetti Grechi, cosi come il
Bulgaro. Ma cosa succede con l’algoritmo UPGMA?
Il metodo UPGMA si basa sull’ipotesi che il tasso di evoluzione sia quasi uguale tra tutte le
entità. Per ricostruire l’albero filogenetico, questo metodo non ricostruisce un’altra matrice.
UPGMA trova direttamente le coppie che hanno la distanza minima nella matrice di
partenza. Cosi nella matrice delle distanze, l’UPGMA classifica insieme il Rumeno con le
lingue Latine, visto che hanno la distanza più piccola tra tutte le coppie delle lingue. L’albero
ricostruito è rappresentato nella Figura 13. Di nuovo i numeri sui rami rappresentano il passo
dove i stessi rami sono riuniti. Come si vede dall’albero, per prima si riunisce il Rumeno con
le lingue Latine. Quindi si aggiunge il Bulgaro.
43. 43
Figura13. Albero UPGMA sulle distanze fuzzy
Come si vede(Figura 12, Figura 13), l’UPGMA funziona meglio di NJ. Questa differenza può
essere conseguenza di alcuni fattori. Cosi per esempio NJ non fa una ricostruzione molto
accurata quando le specie hanno un tasso di evoluzione quasi uguale 23
ed è molto sensibile
al modello di evoluzione scelto. Dall’altra parte NJ funziona bene con un insieme grande di
dati, ed è molto utile per fare operazioni di consenso o di bootstrapping24
. Il metodo UPGMA
ipotizza che il tasso di evoluzione tra tutte le lingue sia quasi uguale e ciò ci permette una
ricostruzione corretta.
Figura 14. Albero NJ sulle distanze fuzzy
23
Kuhner e Felsenstein hanno dimostrato nel 1994 con simulazioni nel computer che NJ fa una valutazione
meno accurata della UPGMA .
24
Felsenstein:PHYLIP
44. 44
Nella Figura14 viene rappresentato lo stesso insieme di lingue, meno il Bulgaro. Il Bulgaro
viene lasciato fuori dalla computazione per vedere il comportamento del Rumeno rispetto
alle lingue Latine e i dialetti Greci. Come si vede, in questo caso, il Rumeno viene collocato
correttamente con le lingue Latine. Questo esperimento sostiene il fatto che NJ comporta
delle imprecisioni quando le entità da classificare sono lingue contemporanee con un tasso
di evoluzione più o meno uguale.
45. 45
4.Conclusioni
In questa ricerca si confrontano due diverse filosofie e due diverse distanze. La filosofia
basata sui caratteri viene confrontata con quella basata sulle distanze. Dall’altra parte viene
fatto un confronto anche tra le distanze di Hamming e le distanze fuzzy di Hamming.
Dall’analisi fatta, si conclude che i metodi basati sui caratteri in generale funzionano bene
con i parametri sintattici e gli alberi ricostruiti sono coerenti con quello che ci aspettiamo.
Comunque ci sono delle imprecisioni dovuti non tanto ai metodi stessi ma al fatto che il
numero dei parametri in grado di identificare in modo chiaro i sottogruppi delle lingue è
piccolo. Dall’altra parte, anche la dipendenza tra i parametri usati fa si che ci siano delle
imprecisioni negli alberi filogenetici ricostruiti.
Per quanto riguarda i metodi basati sulle distanze,l’UPGMA funziona meglio di NJ. UPGMA
applicato sulle distanze di Hamming è quello che ricostruisce la migliore classificazione delle
lingue Indo-Europee. Mentre NJ riporta alcuni imprecisioni sopratutto per quanto riguarda il
mescolamento tra le lingue Germaniche e quelle Celtiche, e il posizionamento del Bulgaro.
Le distanze fuzzy in generale danno vita a classificazioni meno accurate e con tanti
imprecisioni, sia applicando UPGMA che NJ. Probabilmente questa mancanza di accuratezza
può essere spiegato con il fatto che queste distanze non rappresentano un vero strumento
di misura della diversità tra le lingue.
In futuro, usando i metodi basati sui caratteri su un numero maggiore di dati da valutare, si
potranno ottenere risultati migliori.
46. 46
Bibliografia
[1] Bortolussi L., Sgarro A., 2007, Hamming-like Distances for Ill-Defined Strings in Lingusitic
Classification, 2007, RIMUT.
[2] Bortolussi L., Sgarro A., Liviu, P., D., Measures of fuzzy disarray in linguistic typology, 2009,
RIMUT.
[3] Chomsky N., Lasnik H., “Principles and Parameters Theory”, in Syntax: An International Handbook
of Contemporary Research, 1993.
[4] Bortolussi, L., Longobardi, G., Guardiano, C, Sgarro, A., 2011, How many languages are there?
Biology, Computation and Linguistics: New interdisciplinary Paradigms.
[5] Deza, E., Deza, M., M., Dictionary of Distances, 2006, Elsevier.
[6] Dinu, L., P., Sgarro, A., A low complexity distance for DNA strings, 2006, Fundamenta
Informaticae.
[7] Felsenstein, J., Inferring Phylogenis, 2004, Sinauer Associates.
[8] Felsenstein, J., PHYLIP, version 3.695.
[9] Jones, N., C., Pevzner, P., A., An introduction to bioinformatics algorithms, 2004, Bredford Books.
[10] Longobardi, G., Guardiano, C., Evidence for syntax as a signal of historical relatedness, 2009,
Lingua 119.
[11] Minett W. J., Wang Williams S.-Y., On detecting borrowing: distance-based and character-based
approaches, Hong-Kong, P.R.C.
[12] Nakhleh L., Warnow T., Ringe D., Evans N., S., 2005, Transactions of the Philological Society, Rice
University.
47. 47
[13] Saitou N., Masatoshi N., The Neighbor-joining Method: A new Method for Riconstruing
Phylogenetic Trees, 1987, University of Tokyo, Tokyo.
[14] www.evolution.genetics.washington.edu/phylip.html.
[15] www.icp.ucl.ac.be/~opperd/private
[16] www.online.liebertpub.com/doi/abs/10.1089/106652702761034136.
