Methods of populating data structures for use in evolutionary simulations

• US 7,873,499 B2
• Filed: 10/09/2007
• Issued: 01/18/2011
• Est. Priority Date: 10/12/1999
• Status: Expired due to Fees

• Current Assignee: Codexis, Inc.
• Original Assignee: Codexis, Inc.
• Inventors: Selifonov, Sergey A., Stemmer, Willem P. C.
• Primary Examiner(s): Zhou; Shubo (Joe)
• Application Number:
  US11/973,805
• Publication Number:
  US 20080040045A1
• Time in Patent Office: 1,197 Days
• Field of Search: None
• US Class Current: 703/2
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G16B 10/00 ICT specially adapted for evolutionary bioinformatics, e.g. phylogenetic tree construction or analysis
• CPC Class Codes: G16B 20/00 ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations
• CPC Class Codes: G16B 20/20 Allele or variant detection, e.g. single nucleotide polymorphism [SNP] detection
• CPC Class Codes: G16B 20/30 Detection of binding sites or motifs
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search
• CPC Class Codes: G16B 30/20 Sequence assembly
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding

Abstract

In particular, this invention provides novel methods of populating data structures for use in evolutionary modeling. In particular, this invention provides methods of populating a data structure with a plurality of character strings. The methods involve encoding two or more a biological molecules into character strings to provide a collection of two or more different initial character strings; selecting at least two substrings from the pool of character strings; concatenating the substrings to form one or more product strings about the same length as one or more of the initial character strings; adding the product strings to a collection of strings; and optionally repeating this process using one or more of the product strings as an initial string in the collection of initial character strings.

Claims

1. A computer program product on a computer readable storage medium comprising computer code for

i) encoding two or more biological molecules into initial character strings to provide a collection of two or more different initial character strings wherein each of said biological molecules comprises at least about ten subunits;

ii) selecting at least two substrings from said initial character strings;

iii) concatenating said at least two substrings to form one or more product strings about the same length as one or more of the initial character strings;

iv) determining sequence identities of at least one of the product strings relative to at least one initial character string; and

v) selecting one or more product biological molecules for production, wherein the one or more product biological molecules correspond to one or more of the product strings.

2. The computer program product of claim 1, wherein said two or more biological molecules are nucleic acid sequences.

3. The computer program product of claim 1, wherein said two or more biological molecules are nucleic acid sequences encoding naturally occurring proteins.

4. The computer program product of claim 1, wherein said two or more biological molecules are amino acid sequences.

5. The computer program product of claim 1, wherein said initial character strings have at least 30% sequence identity with each other.

6. The computer program product of claim 1, wherein said computer code in (ii) comprises computer code for selecting at least one substring from an initial character string such that the ends of said substring occur in string regions of about three to about twenty characters in length in the initial character string that have higher sequence identity with corresponding regions of another of said initial character strings than the overall sequence identity between the two initial character strings.

7. The computer program product of claim 1, wherein said computer code in (ii) comprises computer code for selecting substrings such that the ends of said substrings occur in predefined motifs of about 4 to about 8 characters.

8. The computer program product of claim 1, wherein the computer code in (ii) comprises computer code for selecting substrings by aligning two or more of said initial character strings to maximize pairwise identity between two or more substrings of the character strings, and selecting a character that is a member of an aligned pair for the end of one substring.

9. The computer program product of claim 1, wherein said computer code further comprises code for randomly altering one or more characters of said initial or product character strings.

10. The computer program product of claim 1, wherein said computer code further comprises code for randomly selecting and altering one or more occurrences of a particular preselected character in said initial or product character strings.

11. The computer program product of claim 1, wherein the initial character strings of (i) are related in that they encode the same gene or protein family but differ in sequence.

12. The computer program product of claim 1, further comprising code for instructing physical screening of the molecule(s) represented by the product strings for one or more desired properties.

13. The computer program product of claim 1, further comprising code for computationally predicting a property for molecules represented by the product strings.