3.5 Rational scores
What if we consider now a rational score instead of an integer one ? If we denote by  ⊂ ℚ the support of S1, let us define M = mini∈ℕ{i ⊂ ℤ}. Changing the scale of the problem by the factor M allows us to get back to the integer case:
ℙ(Hn ≥ a) = ℙ(M Hn ≥ M a)     (19)
This scale factor will obviously increase the complexity of the problem, but as the support cardinal (denoted η) is not changed during the process, the resulting complexities are O(M × a × η) in memory and O(M × n × a × η) in time (n could vanish from the time complexity thanks to the faster algorithm presented above).
For example, if we consider the Kyte-Doolittle hydrophobicity score of the amino-acids (see [10] and table 1), it takes only η = 20 values and M = 10, the resulting complexity to compute ℙ(Hn ≥ a) is then O(200 × n × a). If we consider now the more refined Chothia score ([4]), the scale factor increases from M = 10 to M = 100 and the resulting complexities are multiplied by 10.
Table 1  Distribution of amino-acids estimated on Swissprot (release 47.8) database and Kyte-Doolittle hydrophobic scale. Mean score is -0.244.
a. a.  F  M  I  L  V  C  W  A  T  G
ℙ in %  4.0  2.4  5.9  9.6  6.7  1.5  1.2  7.9  5.4  6.9
score  2.8  1.9  4.5  3.8  4.2  2.5  -0.9  1.8  -0.7  -0.4
a. a.  S  P  Y  H  Q  N  E  K  D  R
ℙ in %  6.9  4.8  3.1  2.3  3.9  4.2  6.6  5.9  5.3  5.4
score  -0.8  -1.6  -1.3  -3.2  -3.5  -3.5  -3.5  -3.9  -3.5  -4.5