Computational method and system for predicting fragmented hybridization and for identifying potential cross-hybridization

• US 6,403,314 B1
• Filed: 02/04/2000
• Issued: 06/11/2002
• Est. Priority Date: 02/04/2000
• Status: Expired due to Fees

• Current Assignee: Agilent Technologies Europe BV (Agilent Technologies, Inc.)
• Original Assignee: Agilent Technologies, Inc.
• Inventors: Sampas, Nicholas M., Wolber, Paul K., Yakhini, Zohar H., Lange, Daniel H.
• Primary Examiner(s): FREDMAN, JEFFREY NORMAN
• Application Number:
  US09/498,608
• Time in Patent Office: 858 Days
• Field of Search: 702/14, 702/20, 435/6, 435/91.2, 536/22.1
• US Class Current: 435/6.18
• CPC Class Codes: C12Q 1/6813 Hybridisation assays
• CPC Class Codes: G16B 25/00 ICT specially adapted for hybridisation; ICT specially adapted for gene or protein expression

Abstract

A computational method and system for predicting the hybridization potential for two polymers. A probe/target interaction matrix is prepared to contain indications of all possible probe/target subunit interaction stabilities. The probe/target interaction matrix is analyzed to create a list of possible single-fragment hybridizations. A graph is then generated with vertices representing fragments, and edges representing possible loops in one or both of the probe and target sequences that allow the pair of fragments interconnected by the edge to coexist within a multi-fragment cross-hybridization. Finally, the graph is analyzed to construct a list of all possible single-fragment and multi-fragment cross-hybridizations possible between the probe molecule and the target molecule. The different hybridizations are scored and sorted by score.

Claims

1. A method for predicting the hybridization potential between a probe polymer and a target polymer, the method comprising:

predicting and storing stabilities of pairing between pairs of subunits, one subunit of the pair in a sequence of probe subunits that together compose the probe polymer, and a second subunit of the pair in a sequence of target subunits that together compose the target polymer;

analyzing the stabilities of pairing between pairs of subunits to enumerate possible fragments, each fragment comprising a probe subunit subsequence and a target subunit subsequence that may pair together in a stable association;

considering all possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form different types of two-fragment hybridizations, including two-fragment hybridizations in which the two fragments are separated by intervening, non-hybridized sequences of different lengths in the target and probe polymers; and

enumerating possible full-length, single-fragment, and multi-fragment hybridizations.

2. The method of claim 1 wherein the probe polymer is a DNA polymer and the target polymer is a DNA polymer.

3. The method of claim 1 wherein the probe polymer is a DNA polymer and the target polymer is an RNA polymer.

4. The method of claim 1 wherein the probe polymer is an RNA polymer and the target polymer is a DNA polymer.

5. The method of claim 1 wherein the probe polymer is an RNA polymer and the target polymer is an RNA polymer.

6. The method of claim 1 wherein the probe and target polymers are selected from among:

DNA polymers;

RNA polymers;

protein polymers;

hybrid biopolymers; and

synthetic polymers, including synthetic nucleotide polymers.

7. The method of claim 1 wherein the stabilities of pairing between pairs of subunits are predicted by thermodynamic considerations.

8. The method of claim 1 wherein the stabilities of pairing between pairs of subunits are predicted by symbolic matching of subunits and retrieval of stability values predetermined for each possible pair of symbols representing polymer subunits.

9. The method of claim 1 wherein the stabilities of pairing between pairs of subunits are predicted by symbolic matching of subunits and retrieval of stability values predetermined for each possible pair of symbols representing polymer subunits and by consideration of stabilities of nearest-neighbor subunit pairs.

10. The method of claim 1 wherein the stabilities of pairing between pairs of subunits are predicted by thermodynamic considerations and by consideration of stabilities of nearest-neighbor subunit pairs.

11. The method of claim 1 wherein the predicted stabilities of pairing between pairs of subunits are stored in a probe/target interaction matrix comprising rows and columns of values, each value indexed by:

a position of the probe subunit of the pair of subunits corresponding to the value; and

a position of the target subunit of the pair of subunits corresponding to the value.

12. The method of claim 11 wherein analyzing the stabilities of pairing between pairs of subunits to enumerate possible fragments further includes:

considering initial values within the probe/target interaction matrix, and for each initial value, adding to a list of possible fragments any consecutive diagonal sequences of values that conform to threshold stability requirements emanating from the initial value.

13. The method of claim 12 wherein the threshold stability requirements include a length of fragment requirement.

14. The method of claim 12 wherein the threshold stability requirements include a threshold stability value calculated from the stabilities of subunit pairings that together compose the fragment.

15. The method of claim 1 wherein considering possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form a two-fragment hybridization further includes considering all possible fragment pairs, storing an indication that a fragment pair may occur concurrently in the probe and target polymers when the subsequences composing the fragments are separated by unpaired sequences within the probe and target polymers meeting minimum and maximum length requirements.

16. The method of claim 1 wherein considering possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form a two-fragment hybridization further includes considering all possible fragment pairs, storing an indication that a fragment pair may occur concurrently in the probe and target polymers when a calculation of the thermodynamic and configurational stability of a two-fragment hybridization comprising the fragment pair meets a threshold stability requirement.

17. The method of claim 1 wherein considering possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form a two-fragment hybridization further includes storing indications of the pairs of fragments that may occur concurrently in the probe and target polymers within a representation of a graph having fragment vertices, with edges representing pairs of fragments that may occur concurrently in the probe and target polymers.

18. The method of claim 1 wherein enumerating possible multi-fragment hybridizations further includes:

initializing a list of possible hybridizations to contain possible single-fragment hybridizations; and

repeatedly selecting each hybridization from the list added in previous iterations and during initialization, and, for each selected hybridization,

selecting each possible single-fragment hybridization,

when the selected single-fragment hybridization and concurrently occur along with the selected hybridization from the list, creating a new multi-fragment hybridization from the selected hybridization and the selected single-fragment hybridization and adding the new multi-fragment hybridization to the list.

19. The method of claim 1 further including:

storing the enumerated possible full-length, single-fragment, and multi-fragment hybridizations in a list of hybridizations.

20. The method of claim 19 further including:

scoring each hybridization in the list of hybridizations for overall stability.

21. The method of claim 20 wherein the score for a hybridization is a sum of scores of all fragments included in the hybridization.

22. The method of claim 20 wherein the score for a hybridization is a sum of scores of all fragments included in the hybridization each raised to a real power.

23. The method of claim 20 wherein the score for a hybridization is a monotonic function of the scores of all fragments included in the hybridization.

24. The method of claim 20 wherein the score for a hybridization is −

Δ

G, where Δ

G is the free energy of the configuration implied by the hybridization.

25. The method of claim 19 further including:

sorting the list of hybridizations by score.

26. A computer-readable medium storing computer instructions that implement the method of claim 1.

27. Electronic signals embodied in a carrier wave that encodes computer instructions that implement the method of claim 1.

51. The method of claim 1 wherein a probe subunit subsequence and a target subunit subsequence may pair together in a stable association when the probe subunit subsequence and the target subunit subsequence are chemically complementary.

52. The method of claim 1 wherein a probe subunit subsequence and a target subunit subsequence may pair together in a stable association when the probe subunit subsequence and the target subunit subsequence are chemically complementary and have lengths greater than a minimum subsequence length in subunits.

28. A system that predicts the hybridization potential between a probe polymer and a target polymer, the system comprising:

a computer processor;

a computer memory; and

a computer program that takes, as input, a subunit sequence for the probe polymer, a subunit sequence for the target polymer, and a minimum fragment length, and that, by considering all possible pairs of fragments having at least the minimum fragment length to determine pairs of fragments that may occur concurrently in the probe and target polymers to form different types of two-fragment hybridizations, enumerates possible full-length, single-fragment, and multi-fragment hybridizations between the probe polymer and the target polymer in order to predict the hybridization potential between the probe polymer and the target polymer.

29. The system of claim 28 wherein the probe and target polymers are selected from among:

DNA polymers;

RNA polymers;

protein polymers;

hybrid biopolymers; and

synthetic polymers, including synthetic nucleotide polymers.

30. The system of claim 28 wherein the computer program enumerates possible full-length, single-fragment, and multi-fragment hybridizations between the probe polymer and the target polymer by:

predicting and storing stabilities of pairing between pairs of subunits, one subunit of the pair in a sequence of probe subunits that together compose the probe polymer, and a second subunit of the pair in a sequence of target subunits that together compose the target polymer;

analyzing the stabilities of pairing between pairs of subunits to enumerate possible fragments, each fragment comprising a probe subunit subsequence and a target subunit subsequence that may pair together in a stable association;

considering possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form different types of two-fragment hybridizations, including two-fragment hybridizations in which the two fragments are separated by intervening, non-hybridized sequences of different lengths in the target and probe polymers; and

combining the enumerated fragments in ways compatible with the determined pairs of fragments that may occur concurrently in the probe and target polymers in order to enumerate possible full-length, single-fragment, and multi-fragment hybridizations.

31. The system of claim 30 wherein the stabilities of pairing between pairs of subunits are predicted by thermodynamic considerations.

32. The system of claim 30 wherein the stabilities of pairing between pairs of subunits are predicted by symbolic matching of subunits and retrieval of stability values predetermined for each possible pair of symbols representing polymer subunits.

33. The system of claim 30 wherein the stabilities of pairing between pairs of subunits are predicted by symbolic matching of subunits and retrieval of stability values predetermined for each possible pair of symbols representing polymer subunits and by consideration of stabilities of nearest-neighbor subunit pairs.

34. The system of claim 30 wherein the stabilities of pairing between pairs of subunits are predicted by thermodynamic considerations and by consideration of stabilities of nearest-neighbor subunit pairs.

35. The system of claim 30 wherein the predicted stabilities of pairing between pairs of subunits are stored in a probe/target interaction matrix comprising rows and columns of values, each value indexed by:

a position of the probe subunit of the pair of subunits corresponding to the value; and

a position of the target subunit of the pair of subunits corresponding to the value.

36. The system of claim 35 wherein analyzing the stabilities of pairing between pairs of subunits to enumerate possible fragments further includes:

considering initial values within the probe/target interaction matrix, and for each initial value, adding to a list of possible fragments any consecutive diagonal sequences of values that conform to threshold stability requirements emanating from the initial value.

37. The system of claim 36 wherein the threshold stability requirements include a length of fragment requirement.

38. The system of claim 36 wherein the threshold stability requirements include a threshold stability value calculated from the stabilities of subunit pairings that together compose the fragment.

39. The system of claim 30 wherein considering possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form a two-fragment hybridization further includes considering all possible fragment pairs, storing an indication that a fragment pair may occur concurrently in the probe and target polymers when the subsequences composing the fragments are separated by unpaired sequences within the probe and target polymers meeting minimum and maximum length requirements.

40. The system of claim 30 wherein considering possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form a two-fragment hybridization further includes considering all possible fragment pairs, storing an indication that a fragment pair may occur concurrently in the probe and target polymers when a calculation of the thermodynamic and configurational stability of a two-fragment hybridization comprising the fragment pair meets a threshold stability requirement.

41. The system of claim 30 wherein considering possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form a two-fragment hybridization further includes storing indications of the pairs of fragments that may occur concurrently in the probe and target polymers within a representation of a graph having fragment vertices, with edges representing pairs of fragments that may occur concurrently in the probe and target polymers.

42. The system of claim 30 wherein enumerating possible multi-fragment hybridizations further includes:

initializing a list of possible hybridizations to contain possible single-fragment hybridizations; and

repeatedly selecting each hybridization from the list added in previous iterations of during initialization, and, for each selected hybridization,

selecting each possible single-fragment hybridization,

when the selected single-fragment hybridization and concurrently occur along with the selected hybridization from the list, creating a new multi-fragment hybridization from the selected hybridization and the selected single-fragment hybridization and adding the new multi-fragment hybridization to the list.

43. The system of claim 30 further including:

storing the enumerated possible full-length, single-fragment, and multi-fragment hybridizations in a list of hybridizations.

44. The system of claim 30 further including:

scoring each hybridization in the list of hybridizations for overall stability.

45. The system of claim 44 wherein the score for a hybridization is a sum of scores of all fragments included in the hybridization.

46. The system of claim 44 wherein the score for a hybridization is a sum of scores of all fragments included in the hybridization each raised to a real power.

47. The system of claim 44 wherein the score for a hybridization is a monotonic function of the scores of all fragments included in the hybridization each raised to a real power.

48. The system of claim 43 further including:

sorting the list of hybridizations by score.

49. A method for predicting the hybridization potential between a probe polymer and a target polymer, the method comprising:

predicting and storing stabilities of pairing between pairs of subunits, one subunit of the pair in a sequence of probe subunits that together compose the probe polymer, and a second subunit of the pair in a sequence of target subunits that together compose the target polymer;

analyzing the stabilities of pairing between pairs of subunits to enumerate possible fragments, each fragment comprising a probe subunit subsequence and a target subunit subsequence that may pair together in a stable association;

considering possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form different types of two-fragment hybridizations, including two-fragment hybridizations in which the two fragments are separated by intervening, non-hybridized sequences of different lengths in the target and probe polymers, by

considering all possible fragment pairs, and

storing an indication that a fragment pair may occur concurrently in the probe and target polymers when a calculation of the thermodynamic and configurational stability of a two-fragment hybridization comprising the fragment pair meets a threshold stability requirement; and

enumerating possible full-length, single-fragment, and multi-fragment hybridizations.

50. A method for predicting the hybridization potential between a probe polymer and a target polymer, the method comprising:

predicting and storing stabilities of pairing between pairs of subunits, one subunit of the pair in a sequence of probe subunits that together compose the probe polymer, and a second subunit of the pair in a sequence of target subunits that together compose the target polymer;

analyzing the stabilities of pairing between pairs of subunits to enumerate possible fragments, each fragment comprising a probe subunit subsequence and a target subunit subsequence that may pair together in a stable association;

considering possible pairs of fragments to determine pairs of fragments that may occur concurrently in the probe and target polymers to form different types of two-fragment hybridizations, including two-fragment hybridizations in which the two fragments are separated by intervening, non-hybridized sequences of different lengths in the target and probe polymers, by storing indications of the pairs of fragments that may occur concurrently in the probe and target polymers within a representation of a graph having fragment vertices, with edges representing pairs of fragments that may occur concurrently in the probe and target polymers; and

enumerating possible full-length, single-fragment, and multi-fragment hybridizations.