Method for determining sequence alignment significance

1. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x, P(x|K N 1,K ,λ(j) N 1,λ + ), using the Island method wherein K N 1,K is determined using N 1,K islands, λ(j) N 1,λ + is determined using N 1,λ islands and j≧3;

c. comparing P(x|K N 1,K ,λ(j) N 1,λ + ) to P th ; and

d. if P(x|K N 1,K ,λ(j) N 1,λ + )>P th , determining said alignment score is statistically insignificant, otherwise, determining said alignment score may or may not be statistically insignificant.

2. The method of claim 1 wherein N 1,K , N 1,λ are each less than 5000.

3. The method of claim 1 wherein N 1,K , N 1,λ are each less than 3000.

4. The method of claim 1 wherein N 1,K , N 1,λ are each less than 1000.

5. The method of claim 1 wherein N 1,K , N 1,λ are each less than 500.

6. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically significant or insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x, P(x|K N 1,K ,λ(j) N 1,λ + ), using the Island method wherein K N 1,K is determined using N 1,K islands, λ(j) N 1,λ + is determined using N 1,λ islands and j≧3;

c. comparing P(x|K N 1,K ,λ(j) N 1,λ + ) to P th ;

d. if P(x|K N 1,K ,λ(j) N 1,λ + )≦P th , determining a second estimate of the p-value of said alignment score x, P(x|K N 2,K ,λ(j) N 2,λ + ) using the Island method wherein K N 2,K is determined using N 2,K ≧9000 islands, λ(j) N 2,λ + is determined using N 2,λ ≧9000 islands and j≧3, otherwise, determining said alignment score x is statistically insignificant;

e. comparing P(x|K N 2,K ,λ(j) N 2,λ + ) to P th ; and

f. if P(x|K N 2,K ,λ(j) N 2,λ + )≦P th , determining said alignment score is statistically significant, otherwise, determining said alignment score is statistically insignificant.

7. The method of claim 6 wherein N 1,K , N 1,λ are each less than 5000.

8. The method of claim 6 wherein N 1,K , N 1,λ are each less than 3000.

9. The method of claim 6 wherein N 1,K , N 1,λ are each less than 1000.

10. The method of claim 6 wherein N 1,K , N 1,λ are each less than 500.

11. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically significant or insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x, P(x|K N 1,K ,λ(j) N 1,λ + ), using the Island method wherein K N 1,K is determined using N 1,K islands, λ(j) N 1,λ + is determined using N 1,λ islands and j≧3;

c. comparing P(x|K N 1,K ,λ(j) N 1,λ + ) to P th ;

d. if P(x|K N 1,K ,λ(j) N 1,λ + )≦P th , determining a second estimate of the p-value of said alignment score x, P(x|K N 2,K ,λ(j) N 2,λ + ), using the Island method wherein K N 2,K is determined using N 2,K islands, λ(j) N 2,λ + is determined using N 2,λ islands and j≧3, otherwise, determining said alignment score x is statistically insignificant;

e. repeating steps c) and d) until determining a final estimate of the p-value of said alignment score, P(x|K N final,K ,λ(j) N final,λ + ), using the, Island method wherein K N final,K is determined using N final,K ≧9000 islands, λ(j) N final,λ + is determined using N final,λ ≧9000 islands and j≧3;

f. comparing P(x|K N final,K ,λ(j) N final,λ + ) to P th ; and

g. if P(x|K N final,K ,λ(j) N final,λ + )≦P th determining said alignment score x is statistically significant, otherwise determining said alignment score x is statistically insignificant.

12. The method of claim 11 wherein N 1,K , N 1,λ are each less than 3000.

13. The method of claim 11 wherein N 1,K , N 1,λ are each less than 1000.

14. The method of claim 11 wherein N 1,K , N 1,λ are each less than 500.

15. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically significant or insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x, P(x|K N 1 ,λ(j) N 1 + ), using the Island method wherein K N 1 and λ(j) N 1 + are each determined using N 1 islands and j>3;

c. comparing P(x|K N 1 ,λ(j) N 1 + ) to P th ;

d. if P(x|K N 1 ,λ(j) N 1 + )≦P th , determining a second estimate of the p-value of said alignment score x, P(x|K N 2 ,λ(j) N 2 + ), using the Island method wherein K N 2 and λ(j) N 2 + are each determined using N 2 islands and j≧3, otherwise, determining said alignment score x is statistically insignificant;

e. repeating steps c) and d) until determining a final estimate of the p-value of said alignment score, P(x|K N final ,λ(j) N final + ), using the Island method wherein K N final and λ(j) N final + are each determined using N final ≧9000 islands and j≧3, otherwise;

f. comparing P(x|K N final ,λ(j) N final + ) to P th ; and

g. if P(x|K N final ,λ(j) N final + )≦P th , determining said alignment score x is statistically significant, otherwise determining said alignment score x is statistically insignificant.

16. The method of claim 15 wherein N 1 is less than 1000.

17. The method of claim 15 wherein N 1 is less than 500.

18. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x, P(x|K(λ(j) N 1,λ + ) N 1,K − ,λ(j) N 1,λ + ), using the Island method wherein K(λ(j) N 1,λ + ) N 1,K − is determined using N 1,K islands, λ(j) N 1,λ + is determined using N 1,λ islands and j≧3;

c. comparing P(x|K(λ(j) N 1,λ + ) N 1,K − ,λ(j) N 1,λ + ) to P th ; and

d. if P(x|K(λ(j) N 1,λ + ) N 1,K − ,λ(j) N 1,λ + )>P th , determining said alignment score x is statistically insignificant, otherwise, determining said alignment score may or may not be statistically insignificant.

19. The method of claim 18 wherein N 1,K , N 1,λ are each less than 5000.

20. The method of claim 18 wherein N 1,K , N 1,λ are each less than 3000.

21. The method of claim 18 wherein N 1,K , N 1,λ are each less than 1000.

22. The method of claim 18 wherein N 1,K , N 1,λ are each less than 500.

23. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically significant or insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x, P(x|K(λ(j) N 1,λ + ) N 1,K − ,λ(j) N 1,λ + ), using the Island method wherein K(λ(j) N 1,λ + ) N 1,K − is determined using N 1,K islands, λ(j) N 1,λ + is determined using N 1,λ islands and j≧3;

c. comparing P(x|K(λ(j) N 1,λ + ) N 1,K − ,λ(j) N 1,λ + ) to P th ;

d. if P(x|K(λ(j) N 1,λ + ) N 1,K − ,λ(j) N 1,λ + )≦P th , determining a second estimate of the p-value to said alignment score x, P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 2,λ + ), using the Island method wherein K(λ(j) N 2,λ + ) N 2,K − is determined using N 2,K ≧9000 islands, λ(j) N 2,λ + is determined using N 2,λ 9000 islands and j≧3, otherwise, determining said alignment score x is statistically insignificant;

e. comparing P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 2,λ + ) to P th ; and

f. if P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 2,λ + )≦P th , determining said alignment score x is statistically significant, otherwise determining said alignment score x is statistically insignificant.

24. The method of claim 23 wherein N 1,K , N 1,λ are each less than 5000.

25. The method of claim 23 wherein N 1,K , N 1,λ are each less than 3000.

26. The method of claim 23 wherein N 1,K , N 1,λ are each less than 1000.

27. The method of claim 23 wherein N 1,K , N 1,λ are each less than 500.

28. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically significant or insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x P(x|K(λ(j) N 1,λ + ) N 1,K − ,λ(j) N 1,2 + ), using the Island method wherein K(λ(j) N 1,λ + ) N 1,K − is determined using N 1,K islands, λ(j) N 1,λ + is determined using N 1,λ islands and j≧3;

c. comparing P(x|K(λ(j) N 1,λ + ) N 1,K − ,λ(j) N 1,λ + ) to P th ;

d. if P(x|K(λ(j) N 1,λ + ) N 1,K − ,λ(j) N 1,λ + )≦P th , determining a second estimate of the p-value to said alignment score x, P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 2,λ + ), using the Island method wherein K(λ(j) N 2,λ + ) N 2,K − is determined using N 2,K islands, λ(j) N 2,λ + is determined using N 2,λ islands and j≧3, otherwise, determining said alignment score x is statistically insignificant;

e. repeating steps c) and d) until determining a final estimate of the p-value of said alignment score x, P(x|K(λ(j) N final,λ + ) N final,K − λ(j) N final,λ + ), using the Island method wherein K(λ(j) N final,λ + ) N final,K − is determined using N final,K ≧9000 islands, λ(j) N final,λ + is determined using N final,λ ≧9000 islands and j≧3;

f. comparing P(x|K(λ(j) N final,λ + ) N final,K − λ(j) N final,λ + ) to P th ; and

g. if P(x|K(λ(j) N final,λ + ) N final,K − ,λ(j) N final,λ + )≦P th determining said alignment score x is statistically significant, otherwise determining said alignment score x is statistically insignificant.

29. The method of claim 28 wherein N 1,K , N 1,λ are each less than 3000.

30. The method of claim 28 wherein N 1,K , N 1,λ are each less than 1000.

31. The method of claim 28 wherein N 1,K , N 1,λ are each less than 500.

32. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically significant or insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x P(x|K(λ(j) N 1 + ) N 1 − ,λ(j) N 1 + ), using the Island method wherein K(λ(j) N 1 + ) N 1 − and λ(j) N 1 + are each determined using N 1 islands and j≧3;

c. comparing P(x|K(λ(j) N 1 + ) N 1 − ,λ(j) N 1 + ) to P th ;

d. if P(x|K(λ(j) N 1 + ) N 1 − ,λ(j) N 1 + )≦P th , determining a second estimate of the p-value to said alignment score x, P(x|K(λ(j) N 2 + ) N 2 − ,λ(j) N 2 + ) using the Island method wherein K(λ(j) N 2 + ) N 2 − and λ(j) N 2 + are each determined using N 2 islands and j≧3, otherwise, determining said alignment score x is statistically insignificant;

e. repeating steps c) and d) until determining a final estimate of the p-value of said alignment score x, P(x|K(λ(j) N final + ) N final − ,λ(j) N final + ), using the Island method wherein K(λ(j) N final + ) N final − and λ(j) N final + are each determined using N final ≧9000 islands and j≧3;

f. comparing P(x|K(λ(j) N final + ) N final − ,λ(j) N final + ) to P th ; and

g. if P(x|K(λ(j) N final + ) N final − ,λ(j) N final + )≦P th determining said alignment score x is statistically significant, otherwise determining said alignment score x is statistically insignificant.

33. The method of claim 32 wherein N 1 is less than 1000.

34. The method of claim 32 wherein N 1 is less than 500.

35. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically significant or insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x P(x|K(λ(j) N 1,λ + ) N 1,K + ,λ(j) N 1,λ − ), using the Island method wherein K(λ(j) N 1,λ + ) N 1,K + is determined using N 1,K islands, λ(j) N 1,λ − and λ(j) N 1,λ + are each determined using N 1,λ islands and j≧3;

c. comparing P(x|K(λ(j) N 1,λ + ) N 1,K + ,λ(j) N 1,λ − ) to P th ;

d. if P(x|K(λ(j) N 1,λ + )) N 1,K + ,λ(j) N 1,λ − )>P th , determining a second estimate of the p-value to said alignment score x, P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 2,λ + ), using the Island method wherein K(λ(j) N 2,λ + ) N 2,K − is determined using N 2,K =N 1,K islands, λ(j) N 2,λ + is determined using N 2,λ =N 1,λ islands and j≧3, otherwise, determining said alignment score x is statistically significant;

e. comparing P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 1,λ + ) to P th ;

f if P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 1,λ + )≦P th , determining a third estimate of the p-value of said alignment score x, P(x|K(λ(j) N 3,λ + ) N 3,K + ,λ(j) N 3,λ − ) using the Island method wherein K(λ(j) N 3,λ + ) N 3,K + is determined using, N 3,λ ≧9,000 islands, λ(j) N 3λ − and λ(j) N 3,λ + are each determined using N 3,λ ≧9,000 islands and j≦3, otherwise, determining said alignment score x is statistically insignificant;

g. comparing P(x|K(λ(j) N 3,λ + ) N 3,K + ,λ(j) N 3,λ − ) to P th ; and

h. if P(x|K(λ(j) N 3,λ + ) N 3,K + ,λ(j) N 3,λ − )≦P th , determining said alignment score x is statistically significant, otherwise, determining said alignment score x is statistically insignificant.

36. The method of claim 35 wherein N 1,K , N 1,λ are each less than 5000.

37. The method of claim 35 wherein N 1,K , N 1,λ are each less than 3000.

38. The method of claim 35 wherein N 1,K , N 1,λ are each less than 1000.

39. The method of claim 35 wherein N 1,K , N 1,λ are each less than 500.

40. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically significant or insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x P(x|K(λ(j) N 1,λ + ) N 1,K + ,λ(j) N 1,λ − ), using the Island method wherein K(λ(j) N 1,λ + ) N 1,K + is determined using N 1,K islands, λ(j) N 1,λ − and λ(j) N 1,λ + are each determined using N 1,λ islands and j≦3;

c. comparing P(x|K(λ(j) N 1,λ + ) N 1,K + ,λ(j) N 1,λ − ) to P th ;

d. if P(x|K(λ(j) N 1,λ + ) N 1,K + ,λ(j) N 1,λ − )>P th , determining a second estimate of the p-value of said alignment score x, P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 2,λ + , using the Island method wherein K(λ(j) N 2,λ + ) N 2,K − is determined using N 2,K =N 1,K islands, λ(j) N 2,λ + is determined using N 2,λ =N 1,λ islands and j≧3, otherwise, determining said alignment score x is statistically significant;

e. comparing P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 2λ + ) to P th ;

f. if P(x|K(λ(j) N 2,λ + ) N 2,K − ,λ(j) N 2λ + )≦P th ,determining a third estimate of the p-value of said alignment score x, P(x|K(λ(j) N 3,λ + ) N 3,K + ,λ(j) N 3,λ − ), using the Island method wherein K(λ(j) N 3,λ + ) N 3,K + is determined using N 3,K islands, λ(j) N 3,λ + and λ(j) N 3,λ − are each determined using N 3,λ islands and j≧3, otherwise, determining said alignment score x is statistically insignificant;

g. repeating steps c)-f) until determining a final estimate of the p-value of said alignment score x, P(x|K(λ(j) N final,λ + ) N final,K + ,λ(j) N final,λ − ), using the Island method wherein K(λ(j) N final,λ + ) N final,K + is determined using N final,K ≧9000 islands, λ(j) N final,λ − and λ(j) N final,λ + are each determined using N final,λ ≧9000 islands and j≧3;

h. comparing P(x|K(λ(j) N final,λ + )) N final,K + ,λ(j) N final,λ − ) to P th ; and

i. if P(x|K(λ(j) N final,λ + ) N final,K + ,λ(j) N final,λ − )≦P th , determining said alignment score x is statistically significant, otherwise, determining said alignment score x is statistically insignificant.

41. The method of claim 40 wherein N 1,K , N 1,λ are each less than 3000.

42. The method of claim 40 wherein N 1,K , N 1,λ are each less than 1000.

43. The method of claim 40 wherein N 1,K , N 1,λ are each less than 500.

44. A method for determining whether an alignment score x, determined from the alignment of a first sequence with a second sequence, is statistically significant or insignificant comprising the steps of:

a. determining a threshold p-value, P th ;

b. determining a first estimate of the p-value of said alignment score x P(x|K(λ(j) N 1 + ) N 1 + ,λ(j) N 1 − ), using the Island method wherein K(λ(j) N 1 + ) N 1 + ,λ(j) N 1 + ) and λ(j) N 1 − are each determined using N 1 islands and j≧3;

c. comparing P(x|K(λ(j) N 1 + ) N 1 + ,λ(j) N 1 − ) to P th ;

d. if P(x|K(λ(j) N 1 + ) N 1 + ,λ(j) N 1 − )>P th , determining a second estimate of the p-value of said alignment score x, P(x|K(λ(j) N 2 + ) N 2 − ,λ(j) N 2 + ), using the Island method wherein K(λ(j) N 2 + ) N 2 − and λ(j) N 2 + are each determined using N 2 =N 1 , islands and j≧3, otherwise, determining said alignment score x is statistically significant;

e. comparing P(x|K(λ(j) N 2 + ) N 2 − ,λ(j) N 2 + ) to P th ;

f. if P(x|K(λ(j) N 2 + ) N 2 − ,λ(j) N 2 + )≦P th , determining a third estimate of the p-value of said alignment score x, P(x|K(λ(j) N 3 + ) N 3 + ,λ(j) N 3 − ), using the Island method wherein K(λ(j) N 3 + ) N 3 + ,λ(j) N 3 + and λ(j) N 3 − are each determined using N 3 islands and j≧3, otherwise, determining said alignment score x is statistically insignificant;

g. repeating steps c)-f) until determining a final estimate of the p-value of said alignment score x, P(x|K(λ(j) N final + ) N final + ,λ(j) N final − ), using the Island method wherein K(λ(j) N final + ) N final + ,λ(j) N final − and λ(j) N final − are each determined using N final ≧9000 islands and j≧3;

h. comparing P(x|K(λ(j) N final + ) N final + ,λ(j) N final − ) to P th ; and

i. if P(x|K(λ(j) N final + ) N final + ,λ(j) N final − )≦P th , determining said alignment score x is statistically significant, otherwise, determining said alignment score x is statistically insignificant.

45. The method of claim 44 wherein N 1 is less than 1000.

46. The method of claim 44 wherein N 1 is less than 500.

47. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 2 .

48. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 7 .

49. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 12 .

50. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 17 .

51. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 19 .

52. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 24 .

53. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 29 .

54. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 34 .

55. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 36 .

56. A computer system comprising:

a. a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming for an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 41 .

57. A computer system comprising:

a. an input device;

b. an output device;

c. a processor;

d. a memory;

e. programming an operating system;

f. programming for determining sequence alignment scores;

g. programming for storing and retrieving a plurality of sequences and sequence alignment scores; and

h. programming for the method of claim 46 .