The combinatorics and extreme value statistics of protein threading

In protein threading, one is given a protein sequence, together with a database of protein core structures that may contain the natural structure of the sequence. The object of protein threading is to correctly identify the structure(s) corresponding to the sequence. Since the core structures are already associated with specific biological functions, threading has the potential to provide biologists with useful insights about the function of a newly discovered protein sequence. Statistical tests for threading results based on the theory of extreme values suggest several combinatorial problems. For example, what is the number of waysm′=# _t {L _i >x _i } _i ⁼⁰ⁿ of choosing a sequence {X _i } _i ⁼¹ⁿ from the set {1, 2, ...,t}, subject to the difference constraints {L _i =X _i+1?X _i >x _i } _i ⁼⁰ⁿ , whereX ₀=0,X _n+1=t+1, and {x _i } _i ⁼⁰ⁿ is an arbitrary sequence of integers? The quantitym′ has many attractive combinatorial interpretations and reduces in special continuous limits to a probabilistic formula discovered by the Finetti. Just as many important probabilities can be derived from de Finetti's formula, many interesting combinatorial quantities can be derived fromm′. Empirical results presented here show that the combinatorial approach to threading statistics appears promising, but that structural periodicities in proteins and energetically unimportant structure elements probably introduce statistical correlations that must be better understood.