The threading score of a protein sequence should be compared with the threading score distribution of a random amino-acid sequence, of the same length, thread on the same structure. We claim that, due to protein contact map properties, this reference distribution is a Weibull ex- treme value distribution whose parameters depend on threading method, structure, query length and random sequence simulation model used. Parameters can be estimated off-line with simulated sequence samples, for different sequence lengths. They can further be interpolated at the exact length of a query, enabling the quick computation of the p-value.