31 martie 2014

Analiza genetică a populațiilor umane de pe teritoriul României

Arată că:
Există diferențe semnificative din punct de vedere statistic între Valahia și București  la un locus; între Valahia și Grecia la un locus; între Valahia și Turcia  la 3 loci; între Valahia și Italia la 3 loci; între Valahia și Ungaria (Budapesta)  la 5 loci; între Valahia și Belarus la 10 loci  și în final între Valahia și Polonia, la 11 loci. Nu există diferențe majore între Valahia și Croația precum și între Valahia și Serbia. 
 alte lucruri interesante aflați aici

Sequence logo - inaltimea unei nucleotide

La fiecare pozitie 1, 2, 3 ... N , sequence logo reprezinta care geana dintre {a,c,g,t} este dominanta. In sirul ADN/ARN sau de aminoacizi, geana "dominanta" se spune ca indica cat de buna va fi conservarea acelei secvente.
Cunoscand matricea de frecvente, este lesne de calculat "inaltimea" fiecarei nucleotide. Am folosit formulele de aici si le-am aplicat pe doua gene: Mecom & FOXD1. Pentru ambele am preluat matricele de frecventa de pe situl Jaspar.
In fine, algoritmul este foarte simplu si are urmatorul output (pentru FOXD1, din poza):


Figura si rezultatele se interpreteaza astfel: analizand 20 de secvente de lungime 8 fiecare, obtinem ca nucleotida A apare o singura data pe pozitia 1, niciodata pe pozitia 2, .... , intotdeauna pe pozitia 7 si de 7 ori pe pozitia 8. Similar si pentru celelalte gene.
Aplicand formulele, se obtine ca inaltimea maxima 2 apare pentru h(a) la pozitia 4, de exemplu (reflectata si in logo); asadar nucleotida A domina categoric pozitia a patra, in toate cele 20 de secvente analizate. Pe de alta parte, pe pozitia 8, frecventele sunt cele mai apropiate, de 7 ori apare A, de 8 ori apare T, nu putem spune cu precizie cine va domina in viitor (care se va conserva mai bine). Asadar, inaltimea acestor gene e destul de mica pentru fiecare.
O inaltime 0 corespunde genei care nu apare niciodata pe pozitia respectiva.

Arunca o privire pe nucleotideHeight.py


Explicatie: cea mai proasta combinatie, care nu spune nimic, este aceea in care nucleotidele A, C, G, T apar fiecare in proportie de 25% . Aceasta combinatie nu ofera nicio predictie despre modul cum se va conserva secventa in viitor. Aplicand formulele, obtinem entropia H = 4 * (-0.5) log(0.5) = 2 . Asadar, pentru cele 4 nucleotide, entropia maxima este 2 si cea minima poate fi 0 (cand una din nucleotide are probabilitate 1 si restul 0, rezulta H=0). "Inaltimea" celor 4 nucleotide impreuna este insa invers proportionala cu entropia lor - pentru a ilustra acest fapt, inaltimea respectiva va fi luata ca 2 - H. In ceea ce priveste fiecare nucleotida in parte, ele au proportia lor din inaltimea totala care este reprezentata de probabilitate. Astfel sunt afisate logo-urile in grafic.

28 martie 2014

GEM5 example | configuration | commands | with Parsec

### configuration ###
cores: 8
CPU clock: 2GHz
Memory: 1GB
L1-Cache size: 64kB
L1-Cache associativity: 2
L2-Cache size: 256kB
L2-Cache associativity: 16
Parsec Benchmark: streamcluster
Parsec Benchmark size: simdev

###

GEM5 commands (run from gem5 directory):

0) download from [here] the script generator: writescripts.pl & the input set files.

1) run this script to create other scripts, using one of the available benches:
> ./writescripts.pl streamcluster 8
The results will be:
streamcluster_8c_simdev.rcS
streamcluster_8c_simlarge.rcS
streamcluster_8c_simmedium.rcS
streamcluster_8c_simsmall.rcS
streamcluster_8c_test.rcS
2) run the command which creates the configuration & run the generated streamcluster_8c_simdev.rcS script on it:
> ./build/ALPHA/gem5.opt --stats-file=test.out ./configs/example/fs.py --kernel=/localhome/yourUser/M5_system_ALPHA_small/binaries/vmlinux_2.6.27-gcc_4.3.4 --disk-image=/localhome/yourUser/M5_system_ALPHA_small/disks/linux-parsec-2-1-m5-with-test-inputs.img --cpu-clock=2GHz -n 8 --mem-size=1GB --caches --l1d_size=32kB --l1i_size=32kB --l1d_assoc=2 --l1i_assoc=2 --l2cache --l2_size=256kB --l2_assoc=16 --script=/localhome/yourUser/gem5/streamcluster_8c_simdev.rcS
The result of this script is ready in m5out/test.out

4) if you run the configuration without any script, the configuration will be created & you can connect to this computer via telnet, have access to a console and write whatever commands you like.
> ./build/ALPHA/gem5.opt --stats-file=test.out ./configs/example/fs.py --kernel=/localhome/yourUser/M5_system_ALPHA_small/binaries/vmlinux_2.6.27-gcc_4.3.4 --disk-image=/localhome/yourUser/M5_system_ALPHA_small/disks/linux-parsec-2-1-m5-with-test-inputs.img --cpu-clock=2GHz -n 8 --mem-size=1GB --caches --l1d_size=32kB --l1i_size=32kB --l1d_assoc=2 --l1i_assoc=2 --l2cache --l2_size=256kB --l2_assoc=16
Output:
.....
Listening for system connection on port 3456
...
> telnet localhost 3456
> ls

24 martie 2014

Optimal binary search tree (OBST)

Titlul problemei: Se dă un set de chei cu o probabilitate de accesare, să se creeze arborele binar optim de căutare astfel încât costul total / timpul mediu de accesare să fie minim.

Formule importante:
OBST(i,j) = min {OBST(i, r-1) + OBST(r+1,j) + p[k]}, unde i r j and i k j
OBST(i,i) = p[i] și OBST(i,i-1) = 0 pentru oricare 1 i N

Costul final este OBST(1,N)
Reconstituirea se face în functie de r-ul ales pentru fiecare iterație a lui OBST, care reprezintă rădăcina arborelui sau sub-arborelui curent.

Și un program pentru rezolvarea în Python are următorul output:



Programul se poate descărca aici.