Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Massively parallel computation of null-models describing molecular co-evolution

 
: Wächter, Michael
: Goesele, Michael

Darmstadt, 2011, 58 S.
Darmstadt, TU, Master Thesis, 2011
Englisch
Master Thesis
Fraunhofer IGD ()
Bioinformatics; General Purpose Computation on Graphics Processing Unit (GPGPU); parallel algorithms; Forschungsgruppe Capturing Reality (CARE)

Abstract
In order to draw conclusions about structural connections in protein or DNA sequences an information theoretic measure - Mutual Information, which measures statistical correlation of different points on a sequence - can be used. As this measure is sensitive to noise due to finite data effects it requires normalization. The incorporation of a null-model for normalization makes the computation process rather lengthy. Since Mutual Information computation offers a lot of possibilities for parallelization, this thesis investigates massive parallelization as a method of speeding up the computation significantly.
Furthermore, a building block for the Mutual Information computation - parallel shuffling - is investigated. It is demonstrated that certain parallel shuffling algorithms introduce a shuffling bias if they are generalized from n which are a power of two to arbitrary n. Also it is shown how this bias can be reduced in a general way, along with proving the bias reduction convergence and the convergence speed.

: http://publica.fraunhofer.de/dokumente/N-167876.html