Dresden 2006 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe
AKB: Biologische Physik
AKB 40: Poster Session II
AKB 40.20: Poster
Mittwoch, 29. März 2006, 16:30–19:30, P3
Statistics of local sequence alignments — •Stefan Wolfsheimer and Alexander K. Hartmann — Institut für theoretische Physik, Göttingen, Germany
Sequence alignment is a tool used for comparison in protein and DNA databases. Widely used algorithms are e.g. BLAST and FASTA. Knowledge about the distribution of gaped optimal subalignment scores of random sequences is essential in order distinguish relevant alignments from alignments that occurred by chance[1]. Analytical solutions are only available for the ungaped case, and yield the Gumbel distribution. Nevertheless, for database applications gaped alignments schemes are much more relevant.
Here we use a method to obtain regions of the distribution on a wide range, including the rare event tail down to p ∼ 10−40. This is similar to the problem of obtaining the density of states of a complex physical system, like spin glasses and therefore methods from statistical mechanics could be adopted [2]. The optimum alignment score corresponds to the ground state of the physical system. By simulated annealing techniques and using the sequences as dynamic variables, rather than the alignments, the distribution of scores is obtained. We study different BLOSUM and PAM scoring matrices and quantifiy in each case the deviations in the rare event tail from the Gumble distribution.
[1] S.F. Altschul and W. Gish, Methods in Enzymology, 266 , 460
[2] A.K. Hartmann, Phys. Rev. E 65, 056102 (2002)