Method and system for optimization of polymer sequences to produce polymers with stable, 3-dimensional conformations
One embodiment of the present invention is directed to a method and system for designing the monomer sequence of a polymer to produce a particular polymer that adopts an initially specified, 3-dimensional conformation in a specified chemical environment. In one specific embodiment, the method and system produces amino-acid sequences for polypeptides in order to generate polypeptides that adopt initially specified, 3-dimensional conformations. Additional embodiments determine sequences for various other types of biopolymers in order to produce biopolymers that adopt specific conformations in specified chemical environments. For example, these method embodiments may be used to design sequences for polysaccharides, polynucleotides, and hybrid biopolymers.
1. A method, carried out on an electronic computer, for determining a monomer sequence for a polymer in order to produce a polymer that adopts a specific, predetermined 3-dimensional conformation in a specified chemical environment, the method comprising:
receiving, by the electronic computer, a specification of a desired 3-dimensional conformation;
selecting, by the electronic computer, a number m of initial polymer-backbone conformations, where m is greater than 1;
for each of the m initial polymer-backbone conformations, selecting, by an electronic computer, a number n of initial sequences, where n is greater than 1, thereby creating mn threads;
iteratively
optimizing, by the electronic computer, the polymer-backbone conformations of each thread with respect to an estimated free energy, and
optimizing, by the electronic computer, the polymer sequence of each thread with respect to an estimated free energy; and
outputting, by the electronic computer, final monomer sequences of a number of threads to a user by listing each of the number of threads in a computer-readable medium or on a display device, the listing indicating, for each of the number of threads, a probability or relative probability that a polymer having a sequence of the thread adopts the desired 3-dimensional conformation.
2. The method of claim 1 wherein the specification of a desired 3-dimensional conformation includes one or more of:
a polymer-backbone length, in monomers;
a polymer-backbone shape;
sequence constraints;
distance-between-specific-monomer constraints; and
local conformation constraints.
3. The method of claim 1 wherein selecting a number m of initial polymer-backbone conformations further comprises:
for the m of initial polymer-backbone conformations,
initializing a currently considered initial-polymer-backbone-conformation data structure; and
iteratively
selecting a polymer-subsequence-backbone conformation from a known polymer compatible with the specification of a desired 3-dimensional conformation; and
adding the selected polymer-subsequence-backbone conformation to the currently considered initial-polymer-backbone-conformation data structure
until a complete initial polymer-backbone conformation has been constructed in the initial-polymer-backbone-conformation data structure.
4. The method of claim 1 wherein selecting a number n of initial sequences for a thread further comprises;
allocating a number n of thread data structures, each thread data structure initialized to have a selected polymer-backbone conformation; and
for each thread data structure,
iteratively
randomly selecting a monomer position within the thread data structure and randomly assigning a particular type of monomer and monomer conformation for the position; and
evaluating a free energy for a polymer described by the resulting thread data structure to either accept the randomly assigned monomer type at the randomly selected monomer position or to reject the randomly assigned monomer type at the randomly selected monomer position.
5. The method of claim 1 wherein optimizing a polymer-backbone conformation of a thread further comprises:
iteratively,
locally and randomly perturbing a current polymer-backbone conformation of the thread;
relaxing the polymer-backbone conformation with respect to the perturbation; and
evaluating a free energy for a polymer described by the resulting thread to either accept the locally and randomly perturbed conformation or to reject the locally and randomly perturbed conformation.
6. The method of claim 5 wherein evaluating a free energy for a polymer described by the resulting thread to either accept the locally and randomly perturbed conformation or to reject the locally and randomly perturbed conformation further comprises:
when the evaluated free energy for the polymer described by the resulting thread is lower than a free energy computed for the thread prior to the perturbation, accepting the locally and randomly perturbed conformation;
when a probability proportional to e −Δ/T , where Δ is a difference between the evaluated free energy for the polymer described by the resulting thread and the free energy computed for the thread prior to the perturbation and T is a tunable parameter, is greater than or equal to a randomly selected probability, accepting the locally and randomly perturbed conformation; and
otherwise rejecting the locally and randomly perturbed conformation.
7. The method of claim 1 wherein optimizing the polymer sequence of a thread further includes:
randomly selecting a monomer position within the thread and randomly assigning a randomly selected monomer type and monomer conformation for the position; and
evaluating a free energy for a polymer described by the resulting thread to either accept the randomly assigned monomer type at the randomly selected monomer position or to reject the randomly assigned monomer type at the randomly selected monomer position.
8. The method of claim 7 wherein evaluating a free energy for a polymer described by the resulting thread to either accept the randomly assigned monomer type at the randomly selected monomer position or to reject the randomly assigned monomer type at the randomly selected monomer position further comprises:
when the evaluated free energy for the polymer described by the resulting thread is lower than a free energy computed for the polymer described by the thread prior to randomly selecting the monomer position within the thread and randomly assigning the randomly selected monomer type and monomer conformation for the position, accepting the randomly assigned monomer type and conformation at the randomly selected position;
when a probability proportional to e −Δ/T , where Δ is a difference between the evaluated free energy for the polymer described by the resulting thread and the free energy computed for the thread prior to prior to randomly selecting the monomer position within the thread and randomly assigning the randomly selected monomer type and monomer conformation for the position, is greater than or equal to a randomly selected probability, accepting the randomly assigned monomer type and conformation at the randomly selected position; and
otherwise rejecting the accepting the randomly assigned monomer type and conformation at the randomly selected position.
9. The method of claim 8 wherein outputting final monomer sequences of each thread to a user by listing the threads in a computer-readable medium or on a display device in order of a probability that a polymer having a sequence of the thread adopts the desired 3-dimensional conformation further comprises:
outputting final monomer sequences of each thread to a user by listing the threads in a computer-readable medium or on a display device in increasing order of free energy calculated for a polymer described by the thread.
10. The method of claim 1
wherein the polymer is a polypeptide;
wherein monomers are amino acids; and
wherein polypeptide-backbone conformations and amino-acid sequences of a thread are optimized with respect to free energy of a polymer described by the thread in solution, the free energy approximated by free energy terms related to amino acids and free energy terms related to pair-wise interaction of amino-acids.
11. Computer instruction encoded in a computer-readable medium that implement a method, carried out on an electronic computer, for determining a monomer sequence for a polymer in order to produce a polymer that adopts a specific, predetermined 3-dimensional conformation in a specified chemical environment by:
receiving, by the electronic computer, a specification of a desired 3-dimensional conformation;
selecting, by the electronic computer, a number m of initial polymer-backbone conformations, where m is greater than 1;
for each of the m initial polymer-backbone conformations, selecting, by the electronic computer, a number n of initial sequences, where n is greater than 1, thereby creating mn threads;
iteratively
optimizing, by the electronic computer, the polymer-backbone conformations of each thread with respect to an estimated free energy, and
optimizing, by the electronic computer, the polymer sequence of each thread with respect to an estimated free energy; and
outputting, by the electronic computer, final monomer sequences of a number of threads to a user by listing each of the number of threads in a computer-readable medium or on a display device, the listing indicating, for each of the number of threads, a probability or relative probability that a polymer having a sequence of the thread adopts the desired 3-dimensional conformation.
12. A computer system comprising:
one or more processors; and
a program running on the one or more processors that determines a monomer sequence for a polymer in order to produce a polymer that adopts a specific, predetermined 3-dimensional conformation in a specified chemical environment by:
receiving, by the electronic computer, a specification of a desired 3-dimensional conformation;
selecting, by the electronic computer, a number m of initial polymer-backbone conformations, where m is greater than 1;
for each of the m initial polymer-backbone conformations, selecting, by the electronic computer, a number n of initial sequences, where n is greater than 1, thereby creating mn threads;
iteratively
optimizing, by the electronic computer, the polymer-backbone conformations of each thread with respect to an estimated free energy, and
optimizing, by the electronic computer, the polymer sequence of each thread with respect to an estimated free energy; and
outputting, by the electronic computer, final monomer sequences of a number of threads to a user by listing each of the number of threads in a computer-readable medium or on a display device, the listing indicating, for each of the number of threads, a probability or relative probability that a polymer having a sequence of the thread adopts the desired 3-dimensional conformation.
13. The computer of claim 12 wherein the specification of a desired 3-dimensional conformation includes one or more of:
a polymer-backbone length, in monomers;
a polymer-backbone shape;
sequence constraints;
distance-between-specific-monomer constraints; and
local conformation constraints.
14. The computer of claim 12 wherein the computer selects a number m of initial polymer-backbone conformations further by:
for the m of initial polymer-backbone conformations,
initializing a currently considered initial-polymer-backbone-conformation data structure; and
iteratively
selecting a polymer-subsequence-backbone conformation from a known polymer compatible with the specification of a desired 3-dimensional conformation; and
adding the selected polymer-subsequence-backbone conformation to the currently considered initial-polymer-backbone-conformation data structure
until a complete initial polymer-backbone conformation has been constructed in the initial-polymer-backbone-conformation data structure.
15. The computer of claim 12 wherein the computer selects a number n of initial sequences for a thread by;
allocating a number n of thread data structures, each thread data structure initialized to have a selected polymer-backbone conformation; and
for each thread data structure,
iteratively
randomly selecting a monomer position within the thread data structure and randomly assigning a particular type of monomer and monomer conformation for the position; and
evaluating a free energy for a polymer described by the resulting thread data structure to either accept the randomly assigned monomer type at the randomly selected monomer position or to reject the randomly assigned monomer type at the randomly selected monomer position.
16. The computer of claim 12 wherein the computer optimizes a polymer-backbone conformation of a thread by:
iteratively,
locally and randomly perturbing a current polymer-backbone conformation of the thread;
relaxing the polymer-backbone conformation with respect to the perturbation; and
evaluating a free energy for a polymer described by the resulting thread to either accept the locally and randomly perturbed conformation or to reject the locally and randomly perturbed conformation.
17. The computer of claim 16 wherein the computer evaluates a free energy for a polymer described by the resulting thread to either accept the locally and randomly perturbed conformation or to reject the locally and randomly perturbed conformation by:
when the evaluated free energy for the polymer described by the resulting thread is lower than a free energy computed for the thread prior to the perturbation, accepting the locally and randomly perturbed conformation;
when a probability proportional to e −Δ/T , where Δ is a difference between the evaluated free energy for the polymer described by the resulting thread and the free energy computed for the thread prior to the perturbation and T is a tunable parameter, is greater than or equal to a randomly selected probability, accepting the locally and randomly perturbed conformation; and
otherwise rejecting the locally and randomly perturbed conformation.
18. The computer of claim 12 wherein the computer optimizes the polymer sequence of a thread by:
randomly selecting a monomer position within the thread and randomly assigning a randomly selected monomer type and monomer conformation for the position; and
evaluating a free energy for a polymer described by the resulting thread to either accept the randomly assigned monomer type at the randomly selected monomer position or to reject the randomly assigned monomer type at the randomly selected monomer position.
19. The computer of claim 18 wherein the computer evaluates a free energy for a polymer described by the resulting thread to either accept the randomly assigned monomer type at the randomly selected monomer position or to reject the randomly assigned monomer type at the randomly selected monomer position by:
when the evaluated free energy for the polymer described by the resulting thread is lower than a free energy computed for the polymer described by the thread prior to randomly selecting the monomer position within the thread and randomly assigning the randomly selected monomer type and monomer conformation for the position, accepting the randomly assigned monomer type and conformation at the randomly selected position;
when a probability proportional to e −Δ/T , where Δ is a difference between the evaluated free energy for the polymer described by the resulting thread and the free energy computed for the thread prior to prior to randomly selecting the monomer position within the thread and randomly assigning the randomly selected monomer type and monomer conformation for the position, is greater than or equal to a randomly selected probability, accepting the randomly assigned monomer type and conformation at the randomly selected position; and
otherwise rejecting the accepting the randomly assigned monomer type and conformation at the randomly selected position.
20. The computer system of claim 12
wherein the polymer is a polypeptide;
wherein monomers are amino acids; and
wherein polypeptide-backbone conformations and amino-acid sequences of a thread are optimized with respect to free energy of a polymer described by the thread in solution, the free energy approximated by free energy terms related to amino acids and free energy terms related to pair-wise interaction of amino-acids.