KR20010083870A - Methods of populating data structures for use in evolutionary simulations - Google Patents

Abstract

Specifically, the present invention provides a novel method of distributing data structures used in evolutionary modeling. More specifically, the present invention provides methods for distributing a data structure having a plurality of character strings. The methods include encoding two or more biological molecules into strings to provide a set of two or more different initial character strings; Selecting at least two lower columns from the character string; Connecting the lower columns to form one or more generation columns having a length substantially equal to one or more lengths of the initial character columns; Adding the generated columns to the set of columns; And optionally repeating the step of using one or more of the generated columns as an initial column of the set of initial character strings.

Description

[0001] METHODS OF POPULATING DATA STRUCTURES FOR USE IN EVOLUTIONARY SIMULATIONS [0002]

There is a long history of using computers to investigate and / or simulate life, genetic systems of individuals and / or genetic / biological entity phenotypic systems, and / or genetic / phenotypic systems. Most motor-driven alife simulations are algorithms that allow artificial life to adapt and / or evolve in the environment. The basic algorithms can be broadly divided into two categories: learning algorithms (algorithms represented by neural networks) and evolutionary algorithms represented, for example, by genetic algorithms.

Many artificial life researchers, especially those who are interested in relatively high-level processes such as learning and adaptation, give their artificial creatures a neural network that acts as an artificial brain (Touretzky (1088-1991) Neural Information Processing Systems , volume 1 -4 Morgan Kaufmann, 1988-1991). The neural network is a learning algorithm. For example, neural networks can be trained to classify images into categories. A typical task is to recognize a character corresponding to a given writing body.

The neural network consists of a combination of input-output devices, called neurons, that are organized in a (higher-level connected) network. Generally, networks are organized into layers, which include an input layer for receiving the input of the sensor, a so-called hidden layer for performing the actual operation, And an output layer. Neural network training involves controlling the intensity of connections between neurons in the network.

Another important form of the biologically inspired basic algorithm is evolutionary algorithms. Metaphorically speaking, if learning processes (eg neural networks) are based on a learning process in an organism of an individual, the evolutionary algorithm can be said to be inspired by evolutionary changes in the distribution of these individuals. Recently, as compared to neural networks, evolutionary algorithms have received widespread support from academia and industry.

An evolutionary algorithm is generally iterative. A single iteration is generally called a "generation". The basic evolutionary algorithm traditionally begins with the distribution of randomly selected individuals. In each generation, each entity "compete" internally to solve a given problem. Relatively well-executed individuals are more likely to "survive" to the next generation. Individuals surviving until the next generation may face small but random changes. If the algorithm is well established and the problem is in fact the kind of solution that can be reached in this way, then the distribution of individuals will show increasingly higher quality solutions as the feedback continues.

The most popular evolutionary algorithm is J. Holland's genetic algorithm. (JHHolland (1992) Adaptation in Natural and Artificial Systems. University of Michgan Press 1975, Reprinted by MIT Press.) Genetic algorithms are widely used in real-life situations (eg, financial forecasting, management science, etc.). In particular, it applies well to multivariate problems where the solution space is discontinuous ("rugged") and not easily understood. To apply a genetic algorithm, it is necessary to 1) map from a set of parameters to a set of bit strings (e.g., character strings), 2) map mats from reals, Called fitness function.

In most evolutionary algorithms, a randomly selected set of bit strings constitutes an initial distribution. The basic genetic algorithm evaluates the fitness of each individual in a group for a single cycle, generates a copy of the individuals proportional to the fitness of each of these individuals, and repeats this cycle again. As such, these evolutionary algorithms typically set a randomly selected set of one bit string as a starting point. Using such a random or unplanned "arbitrary" starting distribution makes it impossible for the evolutionary algorithm to provide an efficient and accurate or concise solution to a given problem, It is even more prominent when it is used to model or analyze biological history or evolution. In fact, whatever it is, the only "force" that drives evolutionary algorithms with a given solution is fitness determination and the associated selection pressure. Since the process has departed from a random (eg, arbitrary) initial state, which ultimately reaches an answer, the distribution of that distribution during the course of this algorithm is dynamic The dynamics show little or no information reflecting the dynamic state of the system being simulated.

In addition, evolutionary algorithms are typically high-dimensional simulations and thus provide group-level information. Certain genetic information, although present, generally exists as an allele (typically as a single character) or as an abstract representation of the frequency of alleles. As a result, evolutionary algorithms provide little or no information about events at the molecular level.

Similarly, neural networks and / or automata use internal rules (algorithms) to mimic the processes of an organism, essentially taking an artificial structure as its starting point. As a result, these models generally mimic processes or meta processes, but this also provides little or no information or insight into events at the molecular level.

<Summary of the Present Invention>

The present invention provides, for example, a novel method for generating " initial " distributions suitable for further computation using genetic / evolutionary algorithms. Members of the population generated according to the method of the present invention possess varying degrees of "association" or "similarity" with each other that reflects the degree of covariance found in naturally occurring distributions. Moreover, unlike the distributions used as input in conventional evolutionary algorithms, the distributions generated by the method include detailed information about the member entities, and generally this information is used to determine the diversity and / Quot; continuous " measurement (rather than the &lt; / RTI &gt; In fact, the methods of the present invention provide a method for precisely encoding information at the molecular level of an individual contained in a distribution generated according to the present invention.

Thus, in one embodiment, the present invention provides methods for distributing one data structure with character strings (e.g., creating a library or collection of character strings). The method comprises the steps of: i) encoding each of the biomolecules in the string of characters with the character strings to provide a set of two or more different initial character strings, each containing at least 10 sub-units; ii) selecting at least two lower columns in said character strings; iii) concatenating the sub-columns to form one or more generated columns having a length substantially equal to one or more of the initial character strings; iv) adding the generated columns to a set of columns (data structure); And v) optionally repeating steps i) or ii) to iv) using one or more of the above generated columns as an initial column in the set of initial character strings. In a particularly preferred embodiment, " encoding " comprises encoding one or more nucleic acid sequences and / or one or more amino acid sequences into character strings. The nucleic acid and / or amino acid sequences may be unknown and / or may be selected by chance, but it is desirable to encode the known protein (s). In a preferred embodiment, the biomolecule is at least about 30%, preferably at least about 50%, more preferably about 75%, and most preferably at least about 85%, 90%, or even 95% sequence Biomolecules are selected to be identical.

In one embodiment, about 3 to about 300, preferably about 6 to about &lt; RTI ID = 0.0 &gt; about &lt; / RTI &gt; about &lt; RTI ID = 0.0 &gt; The lower column (s) are selected such that the end points of the lower rows occur in the column region consisting of 20, more preferably about 10 to about 100, and most preferably about 20 to about 50 characters. In another embodiment, about 4 to about 100, preferably about 4 to about 50, more preferably about 4 to about 10, even more preferably about 6 to about 30, and most preferably, Selecting a sub-row so that the end points of the sub-columns occur in a predetermined motif of about 6 to about 20 characters.

In one embodiment, the step of selecting comprises concatenating each selected lower column from two different initial columns, wherein the concatenation is performed by comparing the sequence sequences of the two initial columns with each other, And in an area consisting of about three to about twenty characters with higher sequence identity between the other two initial columns. The selecting may include aligning two or more of the initial character strings to maximize pairwise identity between two or more sub-columns of the character strings, and selecting a character that is a member of the aligned pair as the end point of one sub-column .

In some embodiments, the " adding " step includes computing the theoretical PI, PK, molecular weight, hydrophobicity, secondary structure, and / or other properties of the protein encoded by the character string. In one preferred embodiment, the resultant columns are added to the set only when there is a sequence identity of at least 30%, preferably at least 50%, more preferably at least 75% or 85%, with the initial columns.

The method may further comprise randomly changing one or more characters of the character strings. This can be accomplished in a number of ways including, but not limited to, introducing a random column into the initial column set and / or using a stagger operator described below. In a particularly preferred embodiment, the above operations are performed in a computer.

In another embodiment, the invention provides a method comprising: i) encoding two or more biological molecules, each comprising at least about 10 subunits, into character strings to provide two or more different sets of initial character strings; ii) selecting at least two sub-columns from the character strings; iii) connecting the sub-columns to form one or more generated columns having substantially the same length as at least one of the initial character strings; iv) adding the generated columns to a set of columns; And v) selectively repeating from step (i) or (ii) to step (iv) using one or more of the above generated columns as an initial column in the initial set of character strings And a computer program product. In other words, the computer program product includes computer code for performing the above-described operations. The program code may be provided in a compiled form such as source code, object code, or executable code. The program may be provided in a convenient medium such as, for example, magnetic media, optical media, electronic media, magneto-optical media, and the like. The code may also reside in a memory, such as a dynamic or static memory, on a computer, e.g., a hard drive.

In another embodiment, the invention provides music derived from a system for producing labels (tags) and / or sequences of biomolecules. The system includes an encoder for encoding two or more initial columns from biological molecules (e.g., nucleic acids and / or proteins); An isolator for identifying and selecting sub-columns from the two or more columns; A concatenator for connecting the lower columns; A data structure for storing the connected lower-order columns as a set of columns; A comparator for measuring the number and variability of the set of columns and determining if sufficient rows are present in the set of columns; And an instruction register for writing the set of columns into a raw string file. In a preferred embodiment, the isolator includes a comparator for aligning and determining the identification regions between the two or more initial columns. Similarly, a comparator may include a method for computing sequence identity, and an isolator and a comparator may optionally share this method. In a preferred embodiment, the isolator is arranged in a column region consisting of about 3 to about 100 characters with a sequence identity with the corresponding region of the other of the initial character strings, rather than the overall sequence identity of the same two columns, The sub-columns are selected so that a point occurs.

In another embodiment, about 4 to about 100, preferably about 4 to about 50, more preferably about 4 to about 10, even more preferably about 6 to about 30, and most preferably, Preferably, the isolator selects the bottom rows so that the end points of the bottom rows occur in a predefined motif of about six to about twenty characters. In one embodiment, the isolator and the coupler may comprise connecting individually or in combination a respective lower column selected from two different initial columns, wherein the connection is made by a combination of a plurality of initial columns, In the region of about 3 to about 300, preferably from about 5 to about 200, and most preferably from about 10 to about 100, characters having higher sequence identity in the two different initialisations . In one preferred embodiment, the isolator aligns two or more of the initial character strings to maximize pairwise identity between two or more sub-columns of character strings, and selects one character that is a member of the aligned pair as the endpoint of one sub-column.

The comparator can impose various selection criteria. Thus, in various embodiments, the comparator can calculate other properties of the protein encoded by the theoretical PI, PK, molecular weight, hydrophobicity, secondary structure, and / or character string. In a preferred embodiment, the comparator adds the columns to the data structure only when there is at least 30% sequence identity with the initial columns.

The system may optionally include an operator that randomly changes one or more characters of the character strings. In some embodiments, such an operator may randomly select and change one or more occurrences of a pre-selected particular character of the character strings. Preferred data structures in this system store encoded (or deconvolved) nucleic acid sequences and / or encoded or unwound amino acid sequences.

A more accurate understanding of the present invention can be obtained from the following detailed discussion of the embodiments. For clarity, this discussion refers to devices, methods and concepts according to particular examples. However, the method of the present invention can operate in various types of logic devices. The present invention is not meant to be limited except as indicated by the appended claims (which should be interpreted in accordance with the doctrine of equivalents).

Further, the logic system may include other elements and other functions in a very broad fashion. Different embodiments of the system may include a mixture of different elements and functions and may group various functions as part of various elements. For clarity, the present invention is described in terms of a system that incorporates many innovative elements and innovative combinations of those elements. The results of any inference should not be construed as limiting the invention to combinations that include all of the innovative elements listed herein as exemplary embodiments.

<DEFINITIONS>

A "character string", a "word", a "binary string" or an "encoded string" refers to a sequence of information (eg, a nucleic acid nucleotide sequence, A subunit structure of a biological molecule such as a sugar sequence of a polysaccharide, and the like. In one embodiment, the character string may be a simple sequence of characters (letters, numbers, or other symbols), or a numerical representation of such information in the form of a type or an intangible (electronic or magnetic, etc.) It is possible. The character string need not be " linear ", and may exist in many other forms, such as a linked list.

A " character " refers to a sub-unit of this character string when used in a meaning associated with one character in the character string. In a preferred embodiment, one character in the string of characters encodes one sub-unit of the encoded biological molecule. Thus, for example, in a preferred embodiment, if the encoded biological molecule is a protein, then one character in the character string at this time encodes one amino acid.

&Quot; Motif " refers to a pattern of subunits that make up a biological molecule. A motif may mean a sub-unit pattern of an uncoded biological molecule, or a sub-unit pattern of a coded representation of a biological molecule.

A " substring " refers to a column found in another column. A sub-column may include a full-length of the "parent" column, but generally refers to a sub-column of such a standard length column.

&Quot; Data structure " refers to an organization for storage of information, typically a plurality of " pieces ", and optionally associated devices. The data structure may be a simple record (e.g., a list) of such information, or it may include additional information (e.g., annotations) related to the information contained therein, members (information "pieces"), or may provide pointers to or pointers to resources external to the data structure. The data structure may be intangible The data structure is not limited to a simple list, but may be a linked list, an indexed list, a data table, an index, a hash index, a flat file database, , A relational database, a local database, a distributed database, a thin client database, and so on. In a preferred embodiment, the data structure provides a field sufficient to store one or more character strings. The data structure is preferably organized to enable alignment of character strings, and optionally, (E.g., a similarity index) and / or the degree of similarity of the columns and / or the degree of similarity of the columns. In one embodiment, Quot; has the form of an alignment map that indicates alignment of a subunit (e.g., nucleotides in the case of nucleic acids). The " encoded string of characters " means a representation of a biological molecule, Sequence / structure information.

The term " similarity degree " is used herein to mean a similarity measure between molecules expressed by an encoded representation of a molecule (e.g., initial character string) (s) or by such a coded character string.

When referring to an operation on a column (e.g., insert, delete, transform, etc.), such an operation may be performed on an encoded representation of a biological molecule, Molecule ". &lt; / RTI &gt;

&Quot; Subunit " when used in the context of a biological molecule means a characteristic " monomer " constituting the biological molecule. Thus, the subunit of the nucleic acid is the nucleotide, the subunit of the polypeptide is amino acid, and the subunit of the polysaccharide is the sugar.

A " pool " or " collection " is used interchangeably when used to refer to a column.

A " biological molecule " refers to a molecule commonly found in biological organisms. A desired biological molecule or a biological polymer composed of a plurality of subunits and having the nature as a polymer. Typical biological molecules include, but are not limited to, nucleic acids (composed of nucleotide subunits), proteins (composed of amino acid subunits), polysaccharides (consisting of the subunits), and the like.

The term " encoding a biological molecule " preferably means generating an expression for the biological molecule that contains the information content of the original biological molecule and thus can also be used for the regeneration of the information content .

&Quot; Nucleic acid " refers to a deoxyribonucleotide or ribonucleotide polymer that is twisted in a single- or double-stranded form, including, but not limited to, naturally occurring nucleotides known to act in a manner similar to naturally occurring nucleotides &Lt; / RTI &gt;

&Quot; Nucleic acid sequence " refers to the nucleotide sequence and identity of a nucleotide containing a nucleic acid.

&Quot; Polypeptide ", " peptide ", and " protein " refer to polymers of amino acid residues and are used interchangeably herein. In addition, these terms apply not only to naturally occurring amino acid polymers, but also to nucleic acid polymers in which one or more amino acid surpluses are composed of artificial chemicals similar to the corresponding naturally occurring amino acid.

&Quot; Polypeptide sequence " refers to the nucleotide sequence and identity of a nucleic acid comprising a polypeptide.

"Adding the product strings to a collection of strings" does not require mathematical addition here. Rather, it refers to the process of identifying one or more rows contained in a set of columns. This process includes, but is not necessarily limited to, the means of copying or moving the column (s) in question into a data structure that is a collection of columns, or a pointer to a data structure that is a collection of columns from a column Means for setting a flag indicating the inclusion of a column in a particular set in relation to the column, or means for specifying a rule that merely includes such a generated column, and the like .

The present invention relates to the field of computer modeling and simulation. More specifically, the present invention provides a new method of distributing data structures used in evolutionary modeling.

1 is a flow diagram illustrating one embodiment of a method of the present invention.

Figure 2 illustrates selection and concatenation of subsequences according to the method of the present invention;

Figure 3 shows a set of subsequences and a connection according to the method of the present invention using a sorting algorithm to fix the order of the sub-columns.

Figure 4 illustrates an exemplary digital device 700 in accordance with the present invention.

FIG. 5 is a chart showing the similarity percentages between different subtilisins (an example of an initial character row set)

Figure 6 shows a pairwise dot-plot alignment showing the homology region between different subtilisins.

Figure 7 shows a pair of dot-plot alignments showing homology regions between seven different parent subtilins.

I. Generate distribution of character strings

The present invention provides a new computational method for generating a realistic or theoretical distribution representation of an entity suitable for use as an initial (or mature / advanced) distribution in an evolutionary model, in particular an evolutionary model represented by a genetic algorithm . Each entity generated by the method of the present invention contains important information (e.g., a representative amino acid or nucleic acid sequence) related to the underlying molecular biology when it is initialized to reflect the characteristics of a particular biological organism, Enables models based on enemy or other algorithms to provide unprecedented levels of information related to evolution at the molecular level.

In a particularly preferred embodiment, the method of the present invention produces a distribution of character strings in which each row represents one or more biological molecules. This method uses only a few columns as " seeds " to generate large-scale heat distributions containing " evolution " relationships to the initial seed members. Unlike conventional genetic algorithms in which the initial set of members is arbitrary or random / inadvertent, or mathematically or for convenience of indication, in a preferred embodiment the distribution generated by the methods of the present invention is a known entity Derived from a biological " precursor " (e.g., a particular nucleic acid sequence and / or a polypeptide sequence).

In a preferred embodiment, the methods of the present invention comprise the following steps:

1) selecting / identifying two or more biological molecules;

2) encoding the biological molecule as a character string;

3) selecting at least two sub-columns in the character string;

4) forming at least one generation column having the same length as at least one initial character string by connecting the lower columns;

5) adding a generation column to a set of columns that can be an initial set of columns or a set of independent sets; And

6) optionally, introducing additional variations in the calculated set of columns;

7) optionally, adding a selected pressure to the calculated set of columns;

8) optionally repeating steps 2) or 3) to 7) using one or more generated columns as the initial columns of the initial character column set.

Each process is described in more detail below.

II. Encode one or more biological molecules as character strings

The method of the present invention generally uses one or more " seed " members. These " seed " members are preferably representations of one or more biological molecules. Thus, the initial steps of the preferred embodiment of the invention include selecting two or more biological molecules and encoding the molecules into one or more character sequences.

A. Identifying / selecting "seed / early" biological molecules

Any actual biological molecule may be used in the methods of the present invention. However, preferred biological molecules are " polymer " biological polymers comprising a plurality of " subunits ". Particularly suitable biological polymers for the methods of the present invention include, but are not limited to, nucleic acids (e.g., DNA, RNA, etc.), proteins, glycoproteins, carbohydrates, polysaccharides,

When a nucleic acid is selected, the nucleic acid may be a single strand or a double strand (although a single strand may well represent / encode a double stranded nucleic acid). The nucleic acid is preferably a known nucleic acid. Such sequences of nucleic acids may be obtained from a variety of sources, including public databases (e.g., GenBank), proprietary databases (e.g., Incyte databases), scientific publications, commercial or personal sequencing laboratories, You can easily get it from the sources.

The nucleic acid may comprise a nucleic acid of the genome, cDNAs, mRNAs, an artificial sequence, a natural sequence having a modified nucleotide, and the like.

In one embodiment, two or more biological molecules are " related ", but not identical. Thus, nucleic acids may represent the same gene or genes, but the strain, species, genus, subsp., Neck, gate or system from which they are derived may be different. Similarly, in one embodiment, a protein, polysaccharide, or other molecule (s) may also be used, except for differences between the molecules that they have because they have been selected from other lines, species, entities, The same protein, polysaccharide or other molecules.

Biological molecules may represent a single gene product (e.g., one mRNA, one cDNA, one protein, etc.) or may represent a collection of gene products and / or uncoded nucleic acids. In some embodiments, the biological molecules will represent members of one or more particular metabolic pathways (e.g., modulatory, transmissible, or synthetic pathways). Thus, for example, the biological molecules may include whole operons, or complete biosynthetic pathways (e.g., lac operon, B-DNA gal operon, the colicin A operon, ), The lux operon, polyketide synthesis pathways, etc.).

In certain preferred embodiments, the biological molecules may comprise any number of other genes, proteins, and the like. Thus, in some embodiments, the biological molecules may comprise whole nucleic acids (e.g., genomic DNA, cDNA, or mRNA) or whole proteins, or whole lipids, of the same or different species (s).

In some embodiments, the biological molecules may reflect an " indication " of the overall distribution of molecules of their species. A high dimensional representation of the molecular distribution was made in the laboratory and can be performed in an in silico method according to the methods of the present invention. How to display the complex molecule or the distribution of molecules in and related technologies (Representational Difference Analysis) RDA (for example, Lisitsyn (1995) Trends Genet, 11 (8):.. 303-307, Rinsinger the like (1994) Mol Carcinog 11 (1): 13-18, and Michiels et al. (1998) Nucleic Acids Res 26: 15 3608-3610, and references cited therein).

Particularly suitable biological molecules for encoding and manipulating according to the methods of the present invention include therapeutic proteins such as protein and / or erythropoietin (EPO), peptide hormones such as insulin, human growth hormone; Growth factors and cytokines such as Neutrophil which activates peptide-78, GROα / MGSA, Groβ, GROγ, MIP-1α, MIP-16, MCP-1, epidermal growth factor epidermal growth factor, fibroblast growth factor, hepatocyte growth factor, insulin-like growth factor, interferon, interleukin, corneal growth factor keratinocyte growth factor, leukemia inhibitory factor, oncostatin M, PD-ECSF, PDGF, pleiotropin, SCF, c-kit ligand, angiogenesis factors Growth factors such as VEGF-A, VEGF-B, VEGF-C, VEGF-D, placental growth factor (PLGF) -CSF), soluble receptors (eg, IL4R, IL_13R, IL-10R, soluble T-cell receptors, etc.) Various comprises a nucleic acid encoding a protein of the layer.

Other preferred encoding molecules include, but are not limited to, transcription and expression activators. Radiation and expression activators include genes and / or proteins that coordinate cell growth, differentiation, regulation, etc. found in eukaryotes, including prokaryotes, viruses and fungi, plants, and animals. Expression activators include cytokines, inflammatory molecules, growth factors, growth factor receptors, tumor gene producers, interleukins (e.g. IL-1, IL-2, IL-8, , IGF-I, IGF-II, FF, PDGF, TNF, TGF- ?, TGF- ?, EGK, KGF, SCR / c-kit, CD40L / CD40, VLA-4 / VCAM-1, ICAM-1 / (Eg, Mos, RAS, Raf and Met), expression activators and inhibitory genes (eg, p53, Tat, Fos, Myc) and hyalurin / CD44, , Steroid hormone receptors such as Jun, Myb, Rel), estrogen, progesterone, testosterone, aldosterone, LDL receptor ligand and corticosterone do.

Preferred molecules for encoding in the methods of the present invention are A spregillus sp., Candida sp., E. coli, staphylococci sp., Streptocci sp., Clostridia sp., Neisseria sp., Enterobacteriace sp., Helicobacter sp., Vibrio sp Rocettsia sp., Coxiella sp., Ehrilichia sp., Rochalimaea sp., Pseudomonas sp., Pseudomonas sp., Ureaplasma sp., Legionella sp., Spirochetes, Mycobacteria sp., Actnomyces sp., Nocardia sp. Brucella, Yersinia, Fracisella, and Pasturella ; protozoa virus, (+) RNA virus, (-) RNA virus, Orthmyxoviruse, dsDNA virus, RNA tumor virus (retroviruse) etc.

Other suitable molecules include nucleic acids and / or proteins that act as inhibitors of transcription, toxins of cereal infectious diseases, industrially important enzymes (proteases, nucleases and lipases), and the like.

It is desirable to include members of the related " families " of nucleic acids or their encoded proteins as molecules. The association (eg, inclusion or exclusion in "and") can be determined by the protein function of the protein and / or its sequence identity with other members of the same. Sequence identity may be determined as described above, and the members preferably share at least 30% sequence identity, more preferably at least 50%, and most preferably at least 80%. In some cases, it is desirable to include molecules with an important association although the sequence identity is low (less than 30%). Such methods are well known in the field of bioinformatics and generally involve molecular folding patterns on sequence / similarity information. A common implementation of such an approach includes " threading algorithms ". The threading algorithm compares sequences with structural templates to find distant homogeneous relationships. If the structural similarity between the target and the template is large enough, then these relationships can be found without significant sequence similarity. Threading algorithms are well known to those skilled in the art and are available, for example, from the NCBI Structure Group Threading Package (National Center for Biological Information (see, http://www.ncbi.nlm.nih.gov/Structure/RESEARCH/threading.html) ) And SeqFold (Molecular Simulations, Inc.).

B) Encoding a biological molecule as a character string

The biological molecule (s) are encoded into character strings. In the simplest case, the character string is the same as the character code used to represent a biological molecule. Thus, for example, a character string when a nucleic acid is encoded includes a character A, C, G, T, or U. Similarly, a basic amino acid nomenclature can be used to represent a polypeptide sequence. To some extent, the encoding scheme may be performed arbitrarily. Thus, for example, in a nucleic acid, A, C, G, T and U may be represented by numbers 1, 2, 3, 4 and 5, respectively, and the nucleic acid may be represented by such a column of numbers, (Usually a very large number) but one number. Other encoding methods are possible. For example, a biological molecule can be encoded into a character string obtained by encoding each " subunit " of a molecule with a multi-character. A variety of compression indications are also possible (eg, periodic motifs can be displayed at one time as appropriate pointers to indicate when they occur).

In addition, biological molecules need not necessarily be encoded into discrete / single column data structures. More complex data structures (e.g., arrays, link lists, index structures, including databases or data tables) may be used to encode the biological molecule (s).

Essentially, data structures capable of input, storage, and retrieval of biological molecule representations are all appropriate. These tasks may be performed manually (e.g., with pencil and paper or card-file, etc.), but data structures may be manipulated optically and / or electronically and / or magnetically, It is more desirable to enable operations (e.g., by a computer).

I II. Choosing sub-columns

In a preferred embodiment, the character strings of the encoded biological molecules provide an initial thermal distribution in which the lower columns are selected. Generally, at least two sub-columns are selected by obtaining one sub-column from each initial column. If there are two or more initial character strings, then all the initial character strings do not have to provide one sub-column each, provided that at least two initial character strings provide each of the sub-columns. However, in the preferred embodiment, at least one lower column from each initial column will be selected.

A) Substring length

There is essentially no limit to the maximum number of sub-columns that can be selected from the initial column, except for the limit of the theoretical maximum number of columns that can be generated from a given column. Thus, for example, the maximum number of sub-columns selected in one initial column is the number of columns generated in the complete permutation of the initial column (s).

However, even in the initial rows of relatively intermediate lengths, the number of permutations is very large. Therefore, in the preferred embodiment, the sub-columns selected from one initial column are selected so that they do not overlap with each other. That is, in the preferred embodiment, the lower columns selected from any one initial column are selected from the corresponding initial columns so that they can be completely regenerated if they are connected in the correct order.

It is also preferable that the lower rows are selected so as not to be too short. Generally, it should not be shorter than the minimum length sufficient to display one subunit of the encoded biological molecule. Thus, for example, if the encoded biological molecule is a nucleic acid, the lower row should be long enough to encode at least one nucleotide. Similarly, if the encoded biological molecule is a polypeptide, the bottom row is long enough to encode at least one amino acid.

In a preferred embodiment, the selected sub-sequence encodes at least two sub-units of the encoded biological molecule, preferably four or more, more preferably ten or more, even more preferably twenty or more, Encodes 50,100 or more than 1000 subunits.

The length of the lower row is determined so as to capture a predetermined level of organic tissue of life. For example, encoding one complete gene, cDNA, and mRNA can be selected as one sub-sequence. In a " higher " level of organic tissue, one subsequence can be selected to encode a set of associated genes, cDNAs, mRNAs, etc. found in operons or control or synthetic pathways. At higher levels, you can choose to encode the entire nucleic acid of an individual (eg, genomic DNA, total mRNA, whole cDNA) as a sub-sequence. There is essentially no limit to the " level of organic tissue " captured by the lower row, as long as the initial column from which the lower row is selected encodes a higher level of organic tissue than that of the lower row. Therefore, when encoding a gene of an individual is selected as a subordinate column, the initial column encodes the entire metabolic path, and when the subordinate column is selected to encode the entire nucleic acid of one entity, the initial column is the entire Thereby encoding the nucleic acid.

Conversely, the bottom row may be selected to encode a sub-unit for a given level of biological organic tissue. Thus, for example, one subsequence can be used to select a specific region of a protein, a specific region of a chromosome (e.g., a region that is characteristically expanded, deleted, or displaced).

B) Sub-column selection algorithm

Any approach can be used to select sub-columns, but the specific approach is determined by the problem being modeled. Preferred selection methods include random substring selection, uniform substring selection, motif-based selection, alignment-based selection, and so on. But are not limited to, frequency-based selection. It is not necessary to apply the same sub-column determination method to all the initial character strings, and different sub-column determination methods may be used for different initial columns. It is also possible to apply a plurality of sub-column selection methods to an arbitrary initial character string.

1. How to select random sub-columns

The subordinate column, in brief, can be random. Many methods can be used to select a sub-column as " random ". For example, if a sub-column of minimum length " L " is selected from a string of encoded characters of length " M ", randomness (which means the position in the column) from L to ML You can select "cleavage points" using a ramdom number generator. "Internal" sub-columns of length less than L are discarded.

Another approach is to address each position on the character string by addressing it as an address (e.g., a character string of length N can be addressed by a number ranging from 1 to N ). According to the present method, the minimum length " L " and the maximum length " M " for the sub-column are firstly selected and a random number generator is used to generate the number " V " Subsequently, one lower column is selected from positions 1 to V, and the next position V + 1 is set to position 1 again, and the remaining lower column selecting operation is repeated. This process is repeated until all of the initial columns have been addressed.

Other ways of randomly selecting sub-columns are already being devised. For the purposes of the present invention, the " random " selection method need not satisfy the formal statistical requirements for randomness. A pseudorandom or haphazard selection method is also sufficient in view of the present invention.

2. Uniform sub-column selection method

In the uniform sub-column selection method, first, the number of sub-columns to be obtained from each initial column is determined. The initial columns are then evenly divided into the desired number of lower rows. If the initial column has a length that does not allow uniform division, sub-columns shorter or longer than one or more average values may be allowed.

3. Motif-based selection method

Sub-columns can be selected from the initial columns using a motif-based selection method. In this approach, the initial character string (s) is scanned to generate a pre-selected specific motif. Subsequently, the sub-row is selected by causing its endpoint (s) to occur in a predefined relationship with this motif. Thus, for example, the end of this sub-column may be inside the motive and may be in an " upstream " or " downstream " position by the number of previously selected sub-units from the end of the motif.

The motif may be perfectly arbitrary, or it may reflect the physical agent or characteristics of the biological molecule. Thus, for example, when the encoded biological molecule is a nucleic acid, the motif may include a binding specificity of a restriction endonuclease (e.g. EcoRv, HindIII, BamHI, PvuII, etc.), a protein binding site, A particular intron / exon junction, a transposon, and the like. Similarly, when the encoded biological molecule is a protein, the motif may include a protease binding site, a protein binding site, a receptor binding site, a specific ligand, a complementarity determining region, an epitope, And so on.

Similarly, the polysaccharide may comprise a particular sugar motif, and the glycoprotein may have certain sugar motifs and / or certain amino acid motifs.

The motif does not have to reflect the primary structure of the encoded biological molecule. Secondary and tertiary structure motives are possible, and they can be used to describe the end points of the sub-columns. Thus, for example, the encoded protein may include certain a-helix, b-sheet, and a-helix motifs, and the occurrence of this motif may be used to describe the bottom row endpoint.

Other "higher dimensional" motif types can be "meta-motifs" as indicated by "fragmentation digest". In this approach, the lower column endpoint is not determined by the occurrence of a single motif, but is described by the combination pattern and spacing of one or more motifs.

Rather than strictly reflecting the sequence patterns, motifs that reflect the information content of a particular region of the character string may also be selected / used. Thus, for example, U.S. Patent No. 5,867,402 describes a computer system and method of computing corresponding sequence signals by transforming them into an information content weight matrix denoted R _i (b, l). Subsequently, a second transformation process of recognizing the specific sequence signal to the information content weight matrix R _i (b, l) is performed to calculate the R _i value including the individual information content of this specific sequence signal. Other approaches to determining the information content of a character string are also well known (Staden (1984) Nucleic Acids Res. 12: 505-519; Schneider (1994) Nanotechnology 5: 1-8; Herman et al. Berg, et al. (1988) J. Mol. Biol., 200 (4): 709-723), Nucleic Acids Res., 18 (20): 6097-6100, J. Bacteriol. .

Other motifs that reflect biological signals can be considered. Thus, for example, one motif describing the end of a lower row can be a stop codon or a start codon for an encoded nucleic acid, and a methionine or polyadenylation signal for a protein .

The same motif need not be applied to all initial sequences. In addition, a plurality of motifs, meta-motifs, and / or motif / metamorphic combinations may be applied for any sequence.

4. Sort-based selection

Another approach is to sort the two or more initial character strings, extract regions with high levels of identity between these initial columns, and select the sub-columns by selecting the end points of the sub-column (s) therein . Thus, for example, the sub-columns may have a length of at least 5 subunits, preferably at least 10, more preferably at least 20, more preferably at least 30, and most preferably at least 50, 100 (E.g., in the middle of these regions) with a sequence identity of at least 30%, preferably at least 50%, more preferably at least 70%, even at least 99%, for a window of at least 200, 500, The end point of the corresponding lower column (s) may be selected to appear.

The terms "sequence identity" or "percent sequence identity" or "percent identity," or "percent homology" in the context of two or more biological polymers (eg, nucleic acids or polypeptides) Refers to two or more sequences or subsequences in which all or a certain percentage of subunits, such as amino acid surplus, or nucleotides, are determined to be identical, when sorted and compared, by sequence comparison algorithms or visual inspection do.

For sequence comparison, one sequence generally acts as a reference sequence, and test sequences are compared to this reference sequence. In a preferred embodiment, when using a sequence comparison algorithm, the test sequence and the reference sequence are input to a computer, subsequence coordinates are specified, and sequence algorithm program parameters are specified, if necessary. Subsequently, the sequence comparison algorithm calculates the percentage sequence identity of the test sequence (s) to the reference sequence, based on the specified program parameters.

Alignment and sequence comparison algorithms are well known to those skilled in the art. For example, a sequence optimal alignment algorithm for comparison is disclosed in Smith &Waterman's (1981) local homology algorithm ( adv. Apple. Math . 2: 482), Needle man & Wench (1970) homology alignment algorithm ( J. Mol. Biol. 48: 443) was compared with Pearson & Lipan (1988) 's search for similarity method, using the above algorithm in commercial modules and / or commercial software packages (eg, Wisconsin Genetics Software Package, Genetics Computer Group, 575 Science Dr ., Madison, WI), or algorithms implemented using visual inspection (see Amusable et al., Cited above).

An example of a useful algorithm is PIEUP. PILEUP generates multiple sequence arrays from the associated sequence group using progressive, pairwise alignments. You also create a tree or endogamy that shows the clustering relationships used to create this array. PILEUP uses a simplified method of the progressive sorting method of Feng & Doolittle (1987) ( J. Mol. Evol. 35: 351-360). The method used is similar to that described in Higgins & Sharp (1989) (CABIOS 5: 151-153). The program can sort up to 300 sequences with a maximum length of 5,000 nucleotides or amino acids. A multiple alignment procedure begins with a pairwise alignment of the two most similar sequences, creating a cluster of two aligned sequences. This cluster is then aligned next to the cluster of the second most similar sequence or ordered sequence. The two clusters of sequences are arranged in a manner simply extending the manner of arranging the two individual sequences one by one. Continue the progressive, pairwise alignment method to complete the alignment. The program is run in such a way that it assigns specific sequences and their amino acid or nucleotide coordinates to sequence comparison regions and specifies program parameters. For example, the reference sequence and other test sequences are compared to determine percent sequence identity using parameters such as default gap weight (3.00), default gap length weight (0.10), and weighted end gaps.

Another example suitable for determining percent sequence identity and sequence similarity is the BLAST algorithm, which is described in Altschul et al. (1990, J. Mo Biol . 215: 403-410). Software that performs BLAST analysis is available through the National Center for Biotechnology Information (http://www.ncbi.nlm.nih.gov/). The algorithm involves first identifying high scoring sequence pairs (HSPs) by identifying short words of length W in a query sequence, which is arranged as a word of the same length in a database sequence It means that some positive-valued threshold score T satisfies or is equal to T. T is referred to as the neighborhood word score threshold (Altschul et al. Cited supra). These initial neighborhood word hits serve as seeds to initiate finding longer HSPs that contain them. These word hits are then expanded in both directions along each sequence as long as they can increase the cumulative alignment score. The expansion of the word hits in both directions is performed when the cumulative score is less than or equal to zero as the accumulated alignment score is accumulated from the one or more negative scores accumulated when the cumulative alignment score falls by X from the maximum reached, And stops when reaching one end of the sequence. The BLAST algorithm parameters W, T and X determine the sensitivity and speed of the alignment. This BLAST program defaults to word length (W) of 11, BLOSUM62 scoring matrix (Henikoff & Henikoff, 1989, Proc. Natl Acad Sci USA 89: 10915) E) to 10, M = 5, N = -4, and the method of comparison of both helix.

In addition to calculating percent sequence identity, the BLAST algorithm also performs a statistical analysis of the similarity between two sequences (eg, Karlin & Altschul (1993, Proc. Natl. Acad Sci USA 90: 5873-5787). One measure of similarity is the smallest sum probability (P (N)), which provides a measure of the probability that a match between two nucleotide or nucleic acid sequences will occur by chance. If the minimum total probability of a nucleic acid relative to a reference nucleic acid is less than 0.1, more preferably less than 0.01, and most preferably less than 0.001, the test nucleic acid is considered to be similar to the reference sequence.

The above similarity algorithm is illustrative, but not limited thereto. It would be desirable if similarity was determined for the entire length of the initial character strings or if similarity determinations could be limited only to certain sub-regions.

5. Frequency-based selection

In the frequency-based subsequence selection method, subsequences are selected to occur when the subsequence regions that meet the preselected specific frequency criterion and the endpoints of the subsequence (s) are in a particular relationship. For example, where it is desirable to exclude encoded biological molecules, including highly repetitive sub-unit patterns (e.g., in nucleic acids, AC is highly concentrated and repeats "ACACACACACAC"), The sub-unit selection can be devised such that the end point is before the specific iteration density of the motif is reached. In this example, the repetition density is the number of subunits per length of the character string of the measured subunits or the number of subunit motives per subunit motive length.

Thus, in the above example, it is possible to select the lower column so that the end point of the lower row precedes the character row region where AC motifs occur with a frequency of 0.5 (50%) or more per at least four motive lengths (8 sub-unit lengths in this case).

Another example is to select a lower column based on the occurrence of a specific sub-unit that occurs at least 100% per X sub-unit. Thus, for example, if the encoded biological molecule is a nucleic acid and the subunit is adenosine " A ", the frequency-based selection method may set the lower column endpoint where the polyadenylation signal (e.g., AAAAAAA) occurs. Depending on the design of the frequency-based sub-column selection criteria, the same results as those obtained using the above motif-based selection method can be obtained.

6. Other standards.

Several other criteria may be used to influence the selection of certain sub-columns and / or to determine the choice. Such criteria include predicted hybrophobicity and / or PI and / or PK of molecules encoded by the bottom row. Other criteria include numerical values associated with the folding of the molecule (s) encoded by the cross-over number, the desired fragment size, the subsequence length distribution, and / or the subsequence (s) And rational information.

IV. Connection of sub-columns

Once the distribution of the sub-columns from the initial columns is selected, the sub-columns are connected to each other to generate new columns of nearly or exactly the same length as the parent initial columns. Thermal connections can be made in a wide variety of ways.

In one embodiment, the sub-columns are concatenated randomly to generate " recombined " One way of doing this "random" connection is to assign a unique identifier (eg, an integer or another identifier) to each sub-column. These identifiers are selected randomly from the pool (eg, using a random number generator), and the subsequences corresponding to these identifiers are combined to form a concatenated sequence. When the combined lower rows match the length of the initial character string (s) almost or exactly, this process is newly started to create another connected column. This process is repeated until the sub-columns are exhaustively used. Another way is to select the lower columns without subtracting the lower column from the "lower column pool", in which case this process is repeated until the desired number of "standard-length" columns are obtained.

However, in a preferred embodiment, it is desirable to keep the relative order that was present in the lower columns of the initial column also in the lower columns that form the connected columns. This can be done in so many ways. For example, an identifier (e.g., a pointer) may be " tagged " to each sub-column selected from its parent column, indicating the relative position of that sub-column relative to the position of the other sub-columns derived from the parent sequence. The lower rows derived from corresponding positions of other initial columns are assigned similar position identifiers. This scheme is illustrated in FIG. 2, where each of the three initial columns (labeled A, B, and C) has five sub-columns numbered from one to five. A5, B1, B2, ..., B5, C1, C2, ..., C5). One row from pool 1 (consisting of A1, B1, and C2), one column from pool 2 (consisting of A2, B2, and C2), and so on up to pool 5, Can be made.

In this connection scheme, once a child column is connected, the child column is removed from the pool. However, if you execute the connection by "copying" the subsequence and using it in the connected sequence, you can use this sub-column in subsequent connections. This method allows connections to be made in more ways.

In other embodiments, various sorting algorithms and / or similarity algorithms can be used to maintain the relative sequence of the sub-columns being concatenated. In this method, the relative positions in the connected sequences can be assigned to the subsequences by linking regions with high similarity (e.g., see FIG. 3).

In a preferred embodiment, the initial encoded biological molecules are somewhat related to each other. Thus, for example, if the encoded molecules represent members of a particular enzyme family, then the molecules represent individuals belonging to a particular group. These subsequences are expected to share a region of considerable similarity. In addition, critical functional domains tend to be retained, which also increases the similarity of certain regions of the subsequences. Thus, aligning regions with high similarities between subsequences can reconstruct the relative order of the subsequences that reflects the order of the subsequences in the initial columns.

It is not necessary that the order in all linked character columns be set perfectly. (E.g., preferably at least 1 percent or more, more preferably at least 10 percent, even more preferably at least 20 percent, and most preferably at least 40 percent, 60 percent, or 80 percent or more) It is preferable to preserve the order of

A similarity measure for reordering the order of the subsequences is similar to sequencing by the hybridization (SBH) method, which uses a similarity algorithm to reproduce nucleic acid sequences from fragments of a complete nucleic acid sequence (cf. Barinaga, 1991 ) Science, 253: 1489 and Bains (1992) Bio / Technology 10 : 757-758 and Drmanac and Crkvenjakov, Yugoslav Patent Application # 570/ 87, 1987 and Drmanac, etc. (1989) Genomics, 4: 114 .; Strezoska et al. (1991 Proc Natl Acad Sci USA 88: 10089 and Drmanac and Crkvenjako, U. S. Pat. No. 5,202,231).

Any connection operation can be displayed alone, or by a specific operator, together with selection and connection operations. These kinds of operators are well known in genetic algorithms. Thus, for example, a " crossing over " (reciprocal translocation) operator can be defined as exchanging subsequences at similar locations of two different initial sequences. Similarly, " linkage " operators may be defined as connecting certain subsequences to each other at an intersection such that the subsequences intersect (whether neighboring subsequences or not) together. Other operators that will appear in the discussion that follows are well known to those skilled in the art.

V) &lt; / RTI &gt; generation columns to a set of columns

The connected columns generated by the methods of the present invention are added to a set of columns that form a " populated dataset ". The columns of this set can be used as initial columns in additional iterations of the above methods (see FIG. 1). Addition means here a process of identifying one or more columns included in a set of columns. Providing a pointer to a data structure indicating a data structure representing a set of columns from a column, a flag indicating an containing element in a particular set, Including, but not limited to, simply associating the generated column (s) with the column, or simply devising rules that cause the generated column (s) to be included in the set .

Once one or more character strings are created, a selection criterion that determines whether or not the connection columns are included in the set of columns (e.g., as initial columns for the second feedback and / or as elements of the distributed data structure) Can be imposed. A wide variety of selection criteria can be used.

In one embodiment, a similarity index may be used as a selection criterion. Thus, the newly generated concatenated character strings may have a predefined specific similarity (e.g., greater than 10%, preferably greater than 20% or greater than 30%, more preferably greater than 40% or greater than 50%, and most preferably greater than 60% (Or coded molecules) and / or one or more " reference " columns with each other and / or at least 70%, 80%, or even 90% or more.

Although the identity of a sequence is very low, the use of an algorithm for evaluating " relatedness " can be included in the selection. These methods include " threading " algorithms and / or covariance measures.

It may be required that the molecule (s) represented by the columns connected by other selection criteria meet certain properties that are predicted in the operation. Thus, for example, the minimum or maximum molecular weight, the minimum or maximum free energy in a particular buffer system, the minimum or maximum contact surface with a particular target molecule or surface, the specific net charge in any buffer system, the predicted PK, PI, binding avidity, specific secondary or tertiary forms, and so on.

The molecule (s) represented by the connected columns may be required as another selection criterion to meet certain properties that are physically irradiated. Thus, for example, the activity of the target molecule and / or the activity of the target molecule can be measured with stability at any temperature, enzyme activity level, solution production at a specific pH, specific optimal temperature and / or pH, minimum or maximum solubility in a particular solvent system, And the like, may be a selection criterion that requires the molecules indicated by the connected columns. Making a physical property determination a particular selection criterion is generally necessary when synthesizing or isolating the molecule (s) represented by the associated column (s) (eg, chemically or by recombinant means).

The application of the above selection criteria in physical systems is known to those skilled in the art (see, for example, Stemmer et al. (1999, Tumor Targeting 4: 1-4) and Ness et al. (1999, Nature Biotechnology 17: 893-896) (1999, Nature Biotechnology 17: 793-797 ) and Minshull and Stemmer (1999, Current Opinion in Chemical Biology 3: 284-290) and the like Christians (1999, Nature Biotechnology 15: 436-438 ) and Zhang et al (1997, Proc .. Natl Acad Sci, USA, 94:.. 4504-4509 , and Patten, etc. (.. 1997, Curr Opin Biotech 8:. 724-733) , and Crameri, etc. (1996, Nature Med 2:. 100-103) , and Crameri (1996, Naure Biotechnology 14: 315-319) and Gates et al. (1996, J. Mol. Biol. 255: 373-386) and Stemmer (1996) and Crameri and Stemmer (1995, BioTechniques 18: 194-195) US Patents 5,605,793, 5,811,238, 5,830,721, 5,834,252, 5,837,458, WO 95/22625, WO 97/0078, WO 97/35966, WO 99/41402; WO 99/41383, WO 99/41369, WO 9941368, EP 0934999, EP 0932670 ; WO 9923107; WO 9921979; WO 9831837; WO 9827230 and WO 9813487)

VI. Introduction of additional variables

In some cases it is desirable to introduce additional variables into the above distribution. It is particularly preferred when the feedback of the evolutionary algorithm using the initial distribution generated by the methods of the present invention does not provide a solution to the modeled problem (e.g., no member fulfills the selection criteria)

Many methods can be used to introduce variables into the thermal distribution according to the methods of the present invention. You can introduce variables in the initial column (s) (input in method) or in connected column (s) (output). These variables are preferably introduced before the selection step, but in some cases, variables may be introduced after selection (e.g., before the second feedback).

In one approach, a stochastic operator that randomly / accidentally changes one or more sub-units containing encoded molecules is introduced into the algorithm. It is also known that variables can be introduced into the pre-encoding molecule (which is re-encoded into character strings) and / or direct variables can be introduced into the encoded string of characters. The guess operator generally requires two selection steps. One is the process of determining which subunit (s) to change and the other is the process of selecting / determining how to change the subunit (s). Both of these selection processes may be stochastic, but not both. Thus, for example, the selection of the subunit (s) to be " mutated " can be arbitrary / random, but mutation must always occur in the same new / alternative subunit. The specific subunits that would otherwise be mutated may be predetermined, but the mutated / resulting subunits may be random / contingent. In yet another embodiment, both the selection of the subunit to be mutated and the result of the mutagenization can be arbitrary / contingent.

In a preferred embodiment, the guess operator may be an input or parameter called " mutation frequency " which sets the " mutation " occurrence average frequency. Thus, for example, if the mutation frequency is set to 10%, the operator will allow only one mutation per 10 subunits contained in the initial columns. The frequency of mutation may be set to any range (eg, 5% -10%, etc.).

This " guess operator " is not necessarily applied to all initial columns or all sub-columns included in the initial column. Thus, in some embodiments, the application of the stochastic operator may be limited to certain initial columns and / or to specific sub-columns (e.g., regions) of one or more initial columns.

When the selection criterion of the estimation operator is fixed, the estimation operator is no longer stochastic, and therefore, "directed mutation" is introduced. This is like an operator that converts all encountered subunits "A" to subunits "B". This designated mutation operator can also be a parameter / attribute / input for the mutation frequency. As described above, the mutation frequency limits the number of subunits that the operator actually modifies, among the " met " subunits.

It will be appreciated that, as described above, the operator may change one or more encoded subunits. In some embodiments, this operator changes a plurality of encrypted sub-units or the entire sub-columns / regions.

You can also introduce variables by using insert or delete operators. The insertion or deletion operator is essentially a variant of the "degenerate mutation" operator. Instead of modifying one or more sub-units, the delete operator removes one or more sub-units, whereas the insert operator inserts one or more sub-units. There are two selection processes for delete and insert operators. Selecting a position to insert or delete is a process, and the other is to select a deletion size or insertion target. If the two selection processes are predetermined (not stochastic), the insertion or deletion operator becomes the specified insertion operator or the specified deletion operator. As in the case of the counting operator, the insertion operator or deletion operator can make the mutation frequency variable / attribute / input.

In another embodiment, the variable can be increased by adding one or more initial columns that are randomly or accidentally generated and have no inevitable relationship with the initial columns derived from the biological molecule (s). Variation-introducing initial string (s) may be generated entirely randomly or by chance, and in some embodiments, the variable-introducing column (s) E.g., the frequency of occurrence of certain sub-units, the minimum and / or maximum similarity with encoded columns, etc.). Variable-initialization columns need not be standard length columns, but may simply include one or more sub-columns. Columns or sub-columns of this nature can be used to reduce variables. Thus, if a particular molecular region is " favored " columns or a lower column (s), then this region may be encoded and added to the distribution of initial columns.

VII. Distributing Data Structures

In one embodiment, all connected column (s) according to the methods of the present invention are used to distribute data structures and / or are used as initial columns in the new feedback of the above-described methods. In another embodiment, a selection criterion is imposed as described above, and only the connected columns that meet this selection criterion are used as initial columns and / or used to distribute the data structure. It is possible to distribute the data structure as a concatenated representation of the encoded molecule (s) used in the above processes, or to deconvolve some of the connected columns and to reproduce a more simply encoded or direct representation of the encoded biological molecules And use these released columns to distribute the data structure.

In one embodiment, the data structure may be as simple as a collection of cards with a card listing connected columns or a card listing one or more connected columns. In a preferred embodiment, a data structure is disclosed on a medium (e.g., mechanical and / or optical and / or magnetic and / or electrical) capable of manipulation of a suitably designed computer-embedded data structure. In a particularly preferred embodiment, the data structure is formed in computer memory (e.g., dynamic, static, read only) and / or optical, magnetic or magneto-optical storage media.

Even in a computer-accessible form, a data structure can simply provide a list of connected columns. The data structure may be structured to preserve the relationship between the various " entries ". At a simple level, it is possible to maintain only the simple congestion and / or sequence of entries. More complex data structures are also available, and they may also provide an auxiliary structure for indexing and / or aligning and / or maintaining one or more entries in the data structure (e.g., connected columns). The data structure may additionally include a connection between an entry and an external data source with comments or entries relating to the entry. Preferred data structures include, but are not limited to, linked lists, tables, hash tables and other indexes, flat-file databases, relational databases, local or distributed computing systems. In a particularly preferred embodiment, the data structure is a data file stored in or stored in conventional (e.g., magnetic and / or optical) media.

VIII. Embodiment of Programmed Digital Device

The present invention includes logic instructions and / or data that includes data and / or data that distributes the data structure according to the method of the present invention when loaded into a suitably configured computing device (e.g., creating a pool / Media or transportable program element.

4 shows a digital device 700 that may be understood as a logical device capable of reading commands from media 717 and / or network terminal 719. [ The device 700 may use these instructions to command the encoding of biological molecules, the manipulation of the encoded representation (s) of the molecules, and the distribution of the data structure. One type of logic device that can present the invention includes a computer system 700 that includes a CPU 707, optional input media 709 and 711, a disk drive 715, and an optional monitor 705 ). The fixed media 717 can be used to program such a system and refers to optical media or magnetic media, or memory, in the form of a disk. The communication terminal 719 can be used to program such a system and includes any form of communication connection.

The present invention may also be initiated as an ASIC (application specific integrated circuit) or PLD (programmable logic device). In such a case, the present invention can be disclosed in a computer understandable descriptor language that can be used to generate an ASIC or PLD that operates as described above.

The present invention may also be disclosed by circuits or logical processing procedures of other digital devices such as cameras, displays, image editors, and the like.

IX. Examples on the website

The methods of the present invention may be disclosed in a local or distributed computing environment. In a distributed environment, the present methods can be implemented in a computer or a plurality of computers including a plurality of processors. Computers may be connected, for example, via a common bus, but it is even more desirable if the computer (s) is a node on the network. The network may be a general or professional, a regional network or a wide area network, and in some preferred embodiments the computers may be components of an intranet or the Internet.

In a preferred Internet embodiment, the client system is typically connected to a server computer that runs a web browser and acts as a web server. Web browsers are typically programs such as IBM's Web Explorer, or Netscape, or Mosaic. Web servers are typically programs like IBM's HTTP daemon or other WWW daemon, but this is not necessarily the case. The client computer is connected in both directions with a web site that provides access to the software that initiates the methods of the present invention either wired or wirelessly.

A user of a client computer connected to an intranet or the Internet may have a client computer request resources that are part of a web site hosting an application program providing the disclosure of the methods of the present invention. The server program (s) processes the request and returns the specified resources (if the resources are available). A standard naming convention known as a Uniform Resource Locator (URL) has been adopted. This protocol includes some types of local names, including sub-items such as http (Hypertext Transport Protocol), ftp (File Transport Protocol), gopher, and WAIS (Wide Area Information Service). When a resource is downloaded, it may also contain additional resources of the URL. Therefore, the user on the client side can easily recognize the existence of new resources that are not specifically requested.

The software that initiates the method (s) of the present invention may be executed by itself on a server hosting a website in a true client-server architecture. Thus, when client computer posts request a host server, the server executes the requested process itself and then downloads the result to the client side. The methods of the present invention may be disclosed in a " multi-tier " form in which the components of the method (s) are executed on their own at the client side. This may be initiated by downloading software from a server for a client-side request (e.g., a Java-based application) and initiated by software installed on the client-side.

In one embodiment, the application program (s) that disclose the methods of the present invention are frame-by-frame. In this case, it is helpful to look at the application as a collection of distinct frames or views rather than as a collection of features or functionality. For example, a typical application program includes a set of menu items, which are intended to invoke a particular frame in a form that clearly shows a certain function of the application in question. From this point of view, an application is seen as a set of applets or a bundle of functions, rather than just a chunk of code. From within the browser, the user can select a web page link and fetch a particular frame (sub-application) of the application in this manner. Thus, for example, one or more frames may provide the ability to input and / or code the biological molecule (s) into one or more character strings, while another frame may generate and / or generate a variance of the encoded character string Or &lt; / RTI &gt;

In addition to representing the application as a collection of frames, the application is represented in a place on the intranet and / or the Internet, which is the URL address of the application. Each URL preferably includes two features: content data for the URL (i.e. all data stored on the server) and data type or Multipurpose Internet Mail Extension (MIME) type. The data format helps the web browser determine how data received from the server should be converted (eg, .gif files are converted to bitmap images). In fact, data types provide guidance on how to handle data received from the browser. If you received a stream of binary data in HTML format, the browser displays this data in HTML page format. If you receive it as a bitmap type, the browser will display it in bitmap image format.

In Microsoft Windows, there are different techniques for registering that a host application handles a data object (i.e., a particular type of data). There is a way for the application to register interest in certain file extensions (eg .doc- "Microsoft Word Document") in Windows; This is the most commonly adopted technology for Windows-based applications. Another method adopted by Microsoft's Object Linking and Embedding (OLE) is to use a class Globally Unigue Identifier or GUID-16 byte identifier to load a specific application on the server (to host documents with GUIDs). When a class ID is linked to a specific DLL (Dynamic Link Library) or an application server, it is registered in a specific machine.

In one embodiment registering to handle only specified files, there is a method through the use of a MIME type in a technique for linking a host application with a document. MIME provides standardized techniques for packaging document objects. It contains a MIME header that indicates which application is eligible to host the document, and is included in a form suitable for transmission over the Internet.

In one preferred embodiment, the methods of the present invention are disclosed by partially using a MIME type specified for use in the methods of the present invention. The MIME type contains the information needed to generate the document itself (eg, a Microsoft ActiveX Document) on the client side, as well as information needed to find and download the program code that allows the document to be viewed when needed have. If the program code already exists on the client side, download it only for the purpose of updating its copy. It defines a new document type that contains information that supports a downloadable program that allows you to view the document.

The MIME type may be associated with an .APP file extension. The file with the .APP extension is an OLE document, so it is started by the OLE DocObject. Because the .APP file is a file, it can be linked to the server using HTML HREF. The .APP file preferably contains the following data: (1) This is the CLSID of an ActiveX object that is an OLE Document Viewer (Viewer), disclosed in one or more forms suitable for use with the methods of the present invention. (2) the URL of the codebase from which the code of the object can be found, and (3) the version number requested (optionally). .APP When the DocObject driver code is installed and the APP MIME type is registered, it can be used to download the .APP file to the user's web browser.

On the server side, because the .APP file is a real file, the server simply receives the request and sends it to the client. When the .APP file is downloaded, the .APP DocObject driver requests the operating system to download the codebase for the object specified in the .APP file. This system function is available on Windows via the GoGetClassObjectFromURL function. After the code base of the ActiveX object is downloaded, the .APP DocObject driver requests the browser to create a view on the browser, for example, by calling the ActiveMe method on the explorer document site. Internet Explorer then calls DocObject again to show the view in detail, and then creates an example ActiveX view object from the downloaded code. Once created, the ActiveX view object is activated in Internet Explorer and is in place, and Internet Explorer creates the appropriate format and ancillary controls.

Once the format is created, you can reconnect any remote server objects needed to perform the function. At this point, the user can interact with this format, which appears to be embedded in the Internet Explorer frame. When the user switches to another page, the browser ultimately has the right to terminate and destroy (and also abandon any special connections to the remote server).

In one preferred embodiment, from the end user's desktop, the entry point to the system will be the home page or the combined home page of another particular web site. Optionally, this page can contain various links in a conventional manner. When a user clicks on a particular link to an application page (e.g., a page that provides functionality of the methods of the present invention), the web browser connects the corresponding application page (file) on the server in response.

In one embodiment, when a user requests access to the methods of the present invention, the user may select a particular page type, e.g., for instant execution of an application (which initiates one or more elements of the methods of the present invention) It connects directly to the application (app document type) page. Because each application page is located using a URL, other pages can have a hyperlink to it. Multiple application pages can be grouped together by creating catalog pages that contain hyperlinks to application pages. When a user selects a hyperlink that points to an application page, the web browser downloads the application's code and launches the page in the browser.

When the browser downloads the application page, the browser (based on the defined MIME type) activates the local driver or the driver for that type of document. In particular, it is desirable to include in the application a GUID and codebase URL that identifies a remote (downloadable) application so that the application can host the document. Given the corresponding document object and GUID that arrived with the application page, the local driver examines the client side to see if the hosting application already exists by itself (eg, by checking the Windows 95 / NT registry). At this point, the local driver may activate the local copy (if local copy exists) or download the latest version of the host application.

Different models of downloading code are generally available. When the code is downloaded, it initially requests the "codebase" specific part (file) from the server. The code base itself can range from simple DLL files to cabinet files (Microsoft .cab files) that contain multiple compressed files. In addition, you can adopt information (eg Microsoft .inf) files to tell the client system how to install the downloaded application. These operating principles enable a variety of methods depending on what elements of the application are downloaded and when.

For the preferred embodiment, the device adopted for the actual downloading program code itself is based on standard Microsoft ActiveX application programming interface (API) -calls. Although this ActiveX API is not provided to support applications delivered over the Web, the ActiveX API can be used to find the correct version of the program code, copy the program code to the local device, verify the integrity, Enables registration to the system. Once this code has been downloaded, the driver proceeds to host the current application to run the document object (similar to how it can host the application through the registry, if it is already set up).

Now that the hosting application (OLE server) is on the client side, the client system can adopt the OLE document view architecture to execute the application correctly in the browser, add the menu of the application to the menu of the browser Includes the use of conventional OLE methods to precisely adjust the size of the application in accordance with browser sizing (as opposed to the conventional limitations of requiring the application to run only within a single ActiveX control rectangle). Once the application is running on the client side, applications can execute remote logic, such as using the Remote Procedure Call (RPC) method. In this way, the logic preferably disclosed as a remote procedure may still be used.

In certain preferred embodiments, the methods of the present invention are disclosed in one or more frames that provide the following functions. Encoding at least two of said biological molecules into character strings to provide a set of two or more different initial character strings each containing at least about ten or more sub-units of biological molecules therein; Selecting at least two lower columns from the character strings; The ability to concatenate sub-columns to form one or more generated columns that are approximately equal in length to one or more initial character columns; And the ability to add (place) the generating columns to the set of columns.

The ability to encode two or more biological molecules preferably provides one or more windows through which a user can insert an indication (s) of biological molecules. In addition, the encoding function optionally provides access to private and / or public databases accessible via the local network and / or intranet, which may input one or more sequences in the database into the methods of the present invention. Thus, for example, in one embodiment, if the end user enters a sequenced nucleic acid into the encoding function, he may optionally request a GenBank search and may code one or more sequences received by such a search and / Can be input.

Methods for initiating intranet and / or intranet implementations of operations and / or data access processes are well known to those skilled in the art and are documented in great detail (see Cluer et al. (1992). A General Framework for the Object-Oriented Queries , Proc SIGMOD International Conference on Management of Data, SanDiego, California, Jun. 2-5, SIGMOD Record, vol. 21, Issue 2, Jun., 1992, Stonebraker, M., Editor, ACM Press, pp. 383-392 ; Microsoft Corporation, "ODBC 2.0 Programmer's Reference and SDK Guide. The Microsoft," ISO-ANSI, Working Draft, "Information Technology-Database Language SQL," Jim Melton, Editor, International Organization for Standardization and American National Standards Institute, Open Database Standard for Microsoft Windows. ™ and Windows NT ™, Microsoft® Open Database Connectivity ™ ™ Software Development Kit ", 1992, 1993, 1994 Microsoft Press, pp. 3-30 and 41-56, ISO Working Draft, "Database Language SQL-Part 2: Foundation (SQL / Foundation) ", CD9075-2: 199.chi.SQL, Sep. 11, 1997, etc.)

Those skilled in the art will appreciate that many modifications may be made to the configuration of the present invention without departing from the scope of the present invention. For example, in the two-stage configuration, the server system performing the WWW gateway function may also perform the functions of the web server. For example, any of the above-described embodiments can be changed to receive a request from a user / user terminal in a form other than a URL. It may also include changes appropriate to the multi-administrator environment.

X. Including physical valuation and feedback loop

As described above, in some preferred embodiments, it may require selection criteria that the molecule (s) represented by the connected columns meet actual physical properties. To achieve this, it is necessary to obtain encoded molecules. To accomplish this, the molecule (s) represented by the connected column (s) may be physically synthesized (e.g., chemically or by recombinant means) Separated.

The physical synthesis of genes, proteins, polysaccharides encoded by the set (s) of character strings in accordance with the present invention is an important tool for creating a physical representation of the problem suitable for physical verification of one or more desired properties.

In a preferred embodiment, gene synthesis techniques are used to construct a library in a faithful and consistent manner to the sequence indications provided in the set of connected columns according to the methods of the present invention.

Preferred gene synthesis methods allow rapid construction of libraries with 10 ⁴ -10 ⁹ gene / protein parameters. Larger libraries are generally more suitable as screeing / selection protocols, since larger libraries are more difficult to create and maintain and sometimes can not be perfectly sampled by physical validation or selection methods. For example, existing physical verification methods in the art generally allow for sampling of variables less than 10 ⁹ by a particular screen of a particular library (e.g., including "life-and-death" selection methods) The verification method is limited to sampling about 10 ⁴ -10 ⁵ members. Thus, it is desirable to build several smaller libraries, since large libraries can not easily do complete sampling. However, larger libraries can be sampled, for example, using large-scale processing methods.

There are many ways to synthesize genes, polysaccharides, proteins, etc., with well-defined sequences, and these areas are growing very rapidly. For clarity of explanation, the following discussion will focus only on one of many known and available methods for the production of biological molecules.

A widely known and mature phosphoramidite chemical reaction that allows a person skilled in the art to effectively prepare oligonucleotides represents current technology in the synthesis of polynucleotides. Although it is possible to use this chemical reaction for routine synthesis of oligonucleotides that are considerably longer than 100 bp, it is somewhat unrealistic, in which case the yield of synthesis is reduced and the degree of purifica- tion required is increased. A " typical " 40-80 bp oligonucleotide can be obtained routinely and directly with high purity.

Oligonucleotides and even perfect synthetic (double stranded or single stranded) genes are available from The Midland Certified Reagent Company (mcrc@oligos.com), The Great American Gene Company (http://www.genco.com), ExpressGen, Inc. (www.expressgen.com), and Operon Technologies Inc. (alameda, CA). Similarly, peptides were purchased from PeptidoGenic (pkim@ccnet.com), HTI Bio-pro = Ducts, Inc. (http://www.htibio.com), BMA Biomedicals, Ltd (UK, Bio-Synthesis, You can order from a variety of sources.

Appropriate demonstration of total gene synthesis from small fragments already suitable for optimization, parallelism and high throughput was done by Dillon and Rosen (1990) Biotechniques , 9 (3): 298-300 . A simple and rapid PCR-based gene assembly process from a set of overlapping single-stranded nucleotides without the use of ligases is described. Some groups describe the successful application of variants of the same PCR-based gene assembly approach to a variety of gene syntheses, increasing in size, and the general applicability for the synthesis of live lyes of mutated genes Protein Engin. , 5 (8): 827-829, 1996), which has been proven to be a combinatorial nature (Sandhu et al. (1992) Biotechniques , 12 (10): 15-16, Prodomou and Pearl Chen et al. (1994) JACS, 1194 (11): 8799-8800, Hayashi et al. (1994) Biotechniques , 17: 310-314).

Recently, Stemmer et al. (1995) Gene 1645: 49-53 provided evidence that PCR-based combinatorial methods are useful for producing larger genes ranging from dozens or even hundreds of synthetic oligonucleotides of 40 bp to at least 2.7 kb . These authors used a "circular" combination PCR for the gene amplification process in four steps known as PCR-based gene synthesis protocols (oligonucleotide synthesis, gene combination, gene amplification and generally cloning) And can be omitted if used.

Once prepared, the gene (s) are inserted into vectors and the vectors transfect the host cells according to the usual methods well known to those skilled in the art and synthesize the encoded protein (s). Methods for cloning to achieve this purpose and sequencing methods for identifying sequences of nucleic acids are well known in the art. Examples of suitable cloning and sequencing techniques and instructions that are well-suited to those skilled in the art of many cloning training are described in Berger and Kimmel, Guide to Molecular Cloning Techniques , Methods in Enzymology Vol. 152 Academic Press, Inc., San Diego, CA (Berger); Sambrook et al. (1989) Molecular Cloning_A Laboratory Manual (2nd ed.) Vol. 1-3, Cold Spring Harbor Laboratory, Cold Spring Harbor Press, NY; And Current Protocols in Molecular Biology , FM Ausubel et al., Eds., Currrent Protocols, a joint venture between Greene Publishing Associates, Inc., and John Wiley & Sons, Inc., (1994 Supplement). Product information from producers of biological reagents and experimental equipment also provides useful information on known biological methods. Such producers include the SIGMA chemical company (Saint Louis, MO), R & D systems (Minneapolis, MN), Pharmacia LKB Biotechnology (Piscataway, NJ), CLONTECH Laboratories, Inc. (Palo Alto, Calif.), Chem Genes Corp., Aldrich Chemical Company (Milwaukee, WI), Glen Research, Inc., GIBCO BRL Life Technologies, Inc. (Gaithersberg, MD), Fluka Chemica Biochemika Analytika (Fuka Chemie AG, Buchs, Switzerland), Invitrogen, San Diego, CA and Applied Biosystems City, CA), and many other commercial sources well known to those skilled in the art.

Once synthesized physical molecules can be inspected for one or more properties, it can be determined whether they meet the selection criteria. Thereafter, the character strings that encode the molecules that meet the physical selection criteria are selected as described above. Actual properties (eg binding specificity and / or avidity, enzymatic activity, molecular weight, charge, thermal stability, temperature optima, optimum pH, (pH optima), etc.) are well known to those skilled in the art.

In some embodiments, actual molecules may encounter one or more " shuffling " procedures to create new molecules that can be encoded and processed according to the methods described above, Lt; / RTI &gt;

Various " shuffling methods " are known, including, for example, Stemmer, et al. (1994) Nature 370: 389-391, Stemmer (1994) Proc. Natl. Acad. Sci. USA, 91: 10747-10751, Stemmer, US Patent No. 5,603,793, Stemmer et al., US Patent No. 5,830,721, Stemmer et al., US Patent No. 5,811,238, Minshull et al., US Pat. No. 5,837,458, Crameri et al. , 2 (1): 100-103, PCT Publications WO 95/22625, WO 97/20078, WO 96/33207, WO 97/33957, WO 98/27230, WO 07/35966, WO 98/31837, 13487, WO 98/13485 and WO 98/42832, which are incorporated herein by reference. In addition, several applications that are currently filed describe important DNA shuffling methods (cf. US Patent Application Serial No. 09 / 116,188, filed July 15, 1998, USSN 60 / 102,362 and Seilfonov and Stemmer Methods for making character strings, polynucleotides & polypeptides having desiredcharacteristics filed 02/05/1999, USSN 60 / 118,854)

In addition, for subsequent physical testing procedures, the library members, including a plurality of genes, proteins, polysaccharides, etc., are each introduced into a parallel mode in which they are spatially separated in containers or container layers, The above-described methods can be performed in a poolwise manner in which all or a portion of the particles are synthesized in a single vessel. Many other synthetic schemes are known and one skilled in the art can easily see which of these is a relative advantage.

The discussed processes are also applicable to production methods using high-throughput systems. (Eg, Zymark Corp., Hopkinto, MA; Air Technical Industries, Mentor, OH; Beckman Instruments, Inc. Fullerton, Calif .; Precision Systems, Inc ., Natick, MA, et al.). These systems include the entire process, including all samples and final analysis of microplates in the detector (s) suitable for test pipetting, liquid dispensing, timed incubation and inspection. It is generally automated. Systems capable of this arrangement provide mass production and fast start-up in addition to high levels of flexibility and customization. Producers of these systems provide detailed protocols for various mass production. Thus, for example, Zymark Corp. provides technical bulletins describing how to use mass-production systems for cloning expression and testing of chemical or recombinant products.

XI. Use of the distribution (s) of generated columns

A) Use in genetic / evolutionary algorithms

In one embodiment, the methods of the present invention provide a distribution of character strings. Particularly desirable character strings denote encoded biological molecules and generally have some relevance because the encoded molecules reflect the level of the biological organism. Thus, the character strings generated by the methods of the present invention are more likely to represent organisms (e.g., genes, genes, entities, subspecies, etc.) found in nature than those that reflect random or accidental selection from a uniform sequence space. Etc.) that reflects a particular level of the relationship (or variable). Thus, sets of character strings (e.g., distributed data structures) according to the methods of the present invention provide a useful starting point for various evolutionary models and are convenient for use in evolutionary algorithms (evolutionary operations).

When used in such models, the distribution according to the methods of the present invention (the set of character strings) provides much more information than would be done based on any distribution in the evolutionary algorithm.

For example, if an evolutionary algorithm uses a random or random distribution of distributions, then the dynamics of this simulation will be from a given starting point to a specific solution (eg, a distribution of properties in the final distribution (s)) Reflect the process. This dynamics can not provide information related to the dynamics of the natural process / distribution, since the starting point is arbitrary and essentially irrelevant to the distribution generated by the natural change.

Conversely, the sets of character strings according to the methods of the present invention contain far more information than the randomly generated starting points used in conventional evolutionary algorithms. First, each member of the distribution contains considerable information regarding the molecular structure. Thus, each member is differentiated by the degree of association / similarity, rather than being simply distinguished by "other" (ie, allelic trait) with other members. Members of the distribution according to the methods of the present invention reflect varying degrees of covariation.

In addition, since the distribution according to the methods of the present invention reflects the microstructure characterizing the level of the biological organism encoded in the initial columns, the initial dynamics of the simulation run using the initial columns as a starting set are " real world " , And provides considerable insight into evolutionary processes.

Moreover, since members generated using the methods of the present invention represent particular molecules, the execution of evolutionary algorithms using these data structures provides substantial information about molecular evolution and / or the design of new and useful molecular properties.

B ) Use when indexing

In another embodiment, data structures according to the methods of the present invention can be used as tags (indexes) for indexing information, essentially regardless of the type. In this approach, information with more similarity is tagged using members of the data structure with more similarities (character strings), while information with lower similarity is tagged with data structures with less similarity Attach tags using members of. In a preferred embodiment, the similarity of character strings used in two different kinds of data reflects the similarity of the tagged information (proportional to similarity).

Once the search is performed, the initial hits are identified using traditional search techniques. When information with strong association is needed, similar members are retrieved from the data structure using any of the well-known similarity algorithms described above. This similarity algorithm is designed to provide a way to search huge data spaces perfectly, quickly and efficiently. Once the members (indexes) with the desired similarity are identified, they point to the tagged data and provide the user with the associated information.

C) Use as a reference object in database search

As a related application, data structures according to the inventive methods or members of these data structures (i.e., character strings) can be used as reference objects in database searches. For example, initially known information (e.g., molecular structures or index columns from a knowledge database such as those described above) is encoded and modified according to the methods described herein. This method creates a new data structure that shows the variables associated with the original encoded information but unclear.

The final information (e.g., members of the data structure) will be deconvolved and will identify the actual or theoretical molecule (s), so that this method can be used to search a common database for the same or related molecules. If the encoded information is from an index in the database, then members of the data structure may use the original or new database search for proper / associated information identification.

D) Identification of structural motifs that give properties to specific molecules

It is often the subject of interest to identify regions of molecules (e.g., proteins) that may be responsible for certain properties, such as, for example, the performance of a function. This identification has traditionally been done using structural information obtained by X-ray crystallography.

The sequences of naturally occurring enzymes that catalyze similar or even the same reactions can vary widely; The sequences may be only 50% identical or less. A set of enzymes with that sequence can catalyze the same reaction, while other properties of these enzymes can be quite different. These properties include temperature and stability to organic solvents, optimum pH, solubility, ability to retain activity when not dissolved in solution, and physical properties such as ease of gene expression in different host systems. The catalytic properties including activity (K _cat and K _m ), the range of accepting substrates and the range of chemical reactions. If the multifunctional dimensions can be encoded by " homology " sequences, the THE methods described herein can be used for non-catalytic proteins (e.g., ligands such as cytokines) and even nucleic acid sequences Such as a promoter that is induced by a promoter.

It is not always possible to accurately link each amino acid with a particular property, since there are various differences between enzymes with similar catalytic functions. There are too many differences in amino acids. However, according to the methods of the present invention, when a member of homologous natural sequences is encoded into initial columns, and thereafter, a data structure having variables encoded by selecting and connecting the lower-order columns is distributed, You can prepare libraries of variables from natural sequences.

It is possible to test the encoded or unwrapped variables for desired properties in an in silico manner and / or to decode the coded variables again and physically synthesize the corresponding molecules as described above. The synthesized molecule may be inspected for one or more desired properties.

Testing members of a data structure under specific conditions for a particular property can determine an optimal combination of sequences of data structures (or initial column sets) for these conditions. By changing only one parameter in these check conditions, it is possible to find an optimal performer among different entities of the library (data structure). Because the test conditions are very similar, most of the amino acids will remain in two sets of top performers (the highest performers of the initial set of columns (set 1) and the highest performers of the distributed data structure (set 2)). Comparing the sequences of the best enzymes under two different conditions, we can find differences in sequences that lead to differences in performance.

Principle component analysis (eg using Partek type software) is one of the many multi-variate tools available for this analysis.

E) Use in music production

In yet another embodiment, the methods of the present invention may be used to create music. Using one of the well-known programs, biological molecules (eg, DNA, proteins, etc.) can be encoded as musical scores. The method includes mapping a particular sub-unit to a particular score. The secondary structure in which the motif and / or subunit occurs determines the timing and sound quality of the music.

Thus, for example, the program SS-midi has been used to encode various nucleic acid and amino acid sequences. In the DNA Calypso approach, the purines are played at 3/2 times the pyrimidine, and the bases C, T, G, and A are converted to C, F, G, A of the keyboard, the first helix is played as a jazz orol The spiral is played on the bass. In another approach, when the note / subunit is in a spiral rather than in the beta-sheet, the note becomes longer. Of course other variables are also possible.

In the methods of the present invention, the biological molecules are encoded into columns as described above, and the lower columns are selected and concatenated to distribute the data structure. When you enter a distributed data structure into a program that converts it to music (eg, SS-MIDI), the program converts these new encoded sequences in the data structure to music. This data structure is redistributed using feedback as described above to generate variations of music phrases.

F) Utilization to drive synthesizer

As described above, the data structure according to the methods of the present invention can be used to drive an apparatus for chemical synthesis of encoded molecules (e.g., polypeptides, nucleic acids, polysaccharides, etc.). Using only a few initial sequences ("seed members"), the methods of the present invention can provide tens, hundreds, thousands, tens of thousands, hundreds of thousands, or even millions of different encoded molecules, literally. When using the final data structure or members of the structure for chemical (or recombinant) synthesis, it is possible to prepare "genetically recombined" libraries of desired molecules of virtually any size. Many "genetically modified" libraries are needed to provide an inspectable system for therapeutic agents, industrial process molecules, specific enzymes, and the like.

Yes (EXAMPLES)

The following examples are provided by way of illustration and not by way of limitation of the claims of the present invention.

Example 1: Subtilisin Family Model

The nucleic acid sequences are aligned (codon cryptanalysis can be optimized for retrotranslation for the desired (gene) expression system, and the number of oligonucleotides to synthesize is minimized). A dot-plot of all possible pairwise arrangements from seven parents is shown (Figures 5, 6, 7). Pairs 6 and 7 show a percent identity of 95% per window above 7aa, while all other pairs show a percent identity of 80% per window above 7aa. The strictness of the alignment (and subsequent indication of intersection between parents) can be handled separately for each pair, so it can represent a low homology crossover due to parents with high homology. No structural biases or biases of activity are included in this model.

Example 2: Design of crossover oligonucleotides for the synthesis of chimerical polynucleotides

First, in order to apply the crossover operator to the sub-columns in the chimeric junction, the sub-columns are identified and selected in the parent (initial) columns. This is accomplished as follows: a) identifying all or some of the homology regions in pairs between all the character sequences, b) identifying the identified pairs in order to index at least one or more intersections within each of the homologous regions of the selected pair Selecting all or a portion of the homologous region of the identified pair to index at least one or more intersections within each of the selected pairs of non-heterologous regions; The "c" may be omitted and structure-activity based elitism is applied based on structure-activity), and thus the location of the parent character strings that are more suitable for selecting the intersection - Provides a description of a set of indexed regions / regions (sub-columns).

Second, we further select the intersection points inside each of the sub-columns of the set of sub-columns selected in Part 1. These processes include: a) randomly selecting at least one of the intersection points in each selected sub-column, and / or b) selecting one or more annealing simulation- To determine a probability of the crossover point selection within each of the selected sub-columns, and / or c) selecting at least one of the intersections of each of the selected sub- Extracting one intersection to create a set of paired intersections where each intersection is indexed according to the corresponding character positions of the parent columns from the chimeric junction of the intersection.

Third, perform optional codon usage adjustments. Depending on the methods used to determine homology (columns that code DNA or AA), the process may vary. For example, if a DNA sequence is used: a) perform codon adjustments for the expression system selected for all parent sequences, and b) adjust the codons between the parents to standardize the codon cryptanalysis for all given amino acids at all corresponding positions Can be performed. This process is particularly useful in cases where the total number of oligonucleotides for gene library synthesis can be significantly reduced and the AA homology level is higher than the DNA homology level or is a family of highly homologous genes (eg 80% + same) It is advantageous.

In essence, this option is an indication of only a few of the elitism mutation operators that must be run carefully. Therefore, you should consider the benefit of reducing the cost of oligonucleotides versus the benefit of introducing this option, as the latter can lead to undesirable results. Most commonly, a codon is used to encode an AA at a given location of multiple parents.

If the AA sequence is used: a) retrotranslate the sequence to degenerate the DNA; b) Define and / or define degenerate nucleotides using position comparisons based on codon cryptanalysis in the original DNA (of a large number of parents or corresponding parents) or codon adjustments to the selected expression system in which the physical test is to be performed .

This step can also be used to introduce prohibited regions in the encoded portions of the gene for subsequent identification / QA / deconvolution / manipulation of the entries in the library.

Fourth, oligonucleotide sequences can be selected for gene combinations. This process involves several decision-making steps:

A uniform 40-60 mer oligonucleotide is commonly used (longer oligonucleotides reduce the number of oligonucleotides that make up the parent, so additional dedicated oligonucleotides are needed to provide a close cross / use).

Select whether shorter or longer oligonucleotides are allowed (i.e. yes / no?). Deciding "yes" will reduce the total number of oligonucleotides for genes with high homology to different lengths, especially 1-2aa, with gaps (deletions / insertions).

Determine the overlap length (typically 15-20 bases, symmetrical or asymmetric).

Select whether degenerate oligonucleotides are allowed (yes / no?). It is another powerful cost reduction item and a powerful way to get additional sequence diversity. Some degenerative schemes and minimized degeneracy schemes are particularly useful for creating libraries that are easy to mutate.

If you use software tools for this task, you can run some variation of parameters to maximize library complexity and minimize cost. Performing a complex combination scheme using oligonucleotides of varying lengths complicates the combination of indexing processes and subsequent, library-encoded parallel or some pooled forms of libraries. If this is possible without complex software, a simple and consistent scheme (eg, all oligonucleotides with 40 base lengths and 20 base overlaps) can be used.

Fifth, "convenience sequences" are designed before and after parent sequences. The same set created at the end of every library entry is ideal. The sequence of accesses includes forbidden regions, a primer sequence to identify that they were generated in combination, RBS, leader peptides, and other special or desired features. In principle, you can define a convenience sequence at a later stage and use the "dummy" set of the appropriate length at this stage. For example, sub-columns of easily recognizable forbidden characters.

In Part 6, an indexed matrix of oligonucleotide columns to create a parent is generated according to the selected scheme. The index of all oligonucleotides includes: a parent identifier (parent ID), an indication of a coding or ancillary chain, and a position number. The intersection points are determined for all indexed coding strings of all the parents with the head and tail subscripts. A secondary chain of all columns is created. Select all coding columns as selected in the combination PCR scheme (eg increase of 40 bp) of part 4. All auxiliary columns are separated according to the same scheme (eg 40 bp with 20 bp shift).

In Part 7, an indexed matrix of oligonucleotides is generated for all pairwise crossover operations. First, all oligonucleotides with paired cross-marking are determined. Second, all sets of all oligonucleotides that are the same position and the same parent crossing pair (four per crossing) are determined. Third, there are all sets of 4 oligonucleotide columns with the same crossover designation, and a 4-chimeric oligo (which includes characters encoding 2 coding and 2 auxiliary chains (eg, with a 20 bp shift in the 20 = 20 plan) A derived set of nucleotides is created. Two coding columns are possible, with the parent's lower column sequence forward endpoint followed by the lower column backward endpoint of the second parent after the intersection. Since the secondary columns are designed in the same way, a complete list of indexed columns of oligonucleotides encoding PCR-compatible gene library combinations is obtained.

Optionally, counting values in the " abundance = amount " field in each oligonucleotide sequence index can be used to find redundant oligonucleotides, count their number, and remove them from the list to further refine the invention. have. This method can be a very useful step as it reduces the total number of oligonucleotides in the library synthesis, especially when the parent sequences are highly homologous.

It will be apparent to those skilled in the art that changes may be made in the above methods and materials without departing from the spirit and scope of the invention as set forth in the claims,

Use of a comprehensive system to generate shuffled nucleic acids included in the iterative process and / or test shuffled nucleic acids

An inspection site, kit or system using any of the above-described selection strategies, ashes, elements, methods or substrates. The kit optionally additionally includes instructions for performing the methods or tests, one or more containers containing packaged material, an inspection station, a device or system components, and the like.

In a further aspect, the invention provides a kit embodying the methods and apparatus described above. The kit of the present invention optionally includes one or more of the following: (1) a shuffled element as described above; (2) instructions for performing the above-described method and / (3) one or more test elements, (4) containers containing nucleic acids or enzymes, other nucleic acids, transgenic plants, animals, cells, etc. (5) 6) Software that executes the above process and / or decision step

Furthermore, the present invention is provided for use of the above-described element or kit, the method or the execution of the test, and / or the use of an apparatus or kit for performing the test or method.

The foregoing examples and embodiments are for purposes of illustration only and various changes and modifications thereto will be apparent to those skilled in the art and are intended to be within the spirit and scope of the present application and the scope of the appended claims. All publications, patents, and patent applications cited herein are included as a reference only.

Claims (41)

A method for distributing a data structure with a plurality of character strings, i) encoding two or more biological molecules, each containing at least about 10 subunits, into the character strings to provide two or more different sets of initial character strings; ii) selecting at least two substrings from the character strings; iii) concatenating the sub-columns to form one or more product strings having substantially the same length as one or more of the initial character strings; iv) adding the generated columns to a set of columns; And v) selectively repeating from step i) or ii) to step iv) using one or more of the generated columns as an initial column in the set of initial character strings, Wherein the data structure comprises a plurality of data structures. The method according to claim 1, Wherein the encoding step comprises encoding one or more nucleic acid sequences into the character strings. 3. The method of claim 2, Wherein the one or more nucleic acid sequences comprise a nucleic acid sequence encoding a known protein. The method according to claim 1, Wherein the encoding step comprises encoding one or more amino acid sequences into the character strings. 5. The method of claim 4, Wherein the one or more amino acid sequences comprise a nucleic acid sequence encoding a known protein. The method according to claim 1, Wherein the biological molecules have a sequence identity of at least 30%. The method according to claim 1, Wherein the sub-column selection step comprises the steps of: selecting, in a column region composed of about 3 to about 20 characters having high sequence identity with the corresponding regions of the other columns among the initial character strings than the overall sequence identity of the same two columns, And selecting the sub-columns so that a point occurs. The method according to claim 1, Wherein the selecting of the sub-columns comprises selecting the sub-columns such that the end points of the sub-columns occur within a predefined motif of about 4 to about 8 characters. &Lt; RTI ID = 0.0 &gt; Way. The method according to claim 1, Wherein the selecting and concatenating sub-columns comprises concatenating sub-columns selected from two different initial columns, wherein the concatenation is performed by using two different initial values of the two different initial sequences, Lt; RTI ID = 0.0 &gt; 3 &lt; / RTI &gt; to about 20 characters having higher sequence identity between columns. The method according to claim 1, Wherein the step of selecting a lower column comprises the steps of sorting two or more of the initial character strings to maximize a pairwise identity between two or more lower columns of the character strings, The method comprising the steps of: The method according to claim 1, Wherein the generated columns are added to the set only when there is at least 30% sequence identity with the initial columns. The method according to claim 1, Further comprising: randomly modifying one or more characters of the character strings. 13. The method of claim 12, Further comprising the step of randomly selecting and changing the appearance frequency of one or more specific characters pre-selected in the character strings. In a computer program product, i) encoding two or more biological molecules, each comprising at least about 10 subunits, into character strings, thereby providing a set of two or more different initial character strings; ii) selecting at least two sub-columns from the character strings; iii) connecting the sub-columns to form one or more generated columns having substantially the same length as at least one of the initial character strings; iv) adding the generated columns to a set of columns; And v) selectively repeating from step (i) or (ii) to step (iv) using one or more of the generated columns as an initial column in the initial set of character strings Computer code &Lt; / RTI &gt; 15. The method of claim 14, Wherein the at least two biological molecules are nucleic acid sequences. 15. The method of claim 14, Wherein the at least two biological molecules are nucleic acid sequences of known proteins. 15. The method of claim 14, Characterized in that the two or more biological molecules are amino acid sequences. 15. The method of claim 14, Wherein said biological molecules have at least 30% sequence identity. 15. The method of claim 14, The code is arranged to cause the lower-column endpoint to occur in a column region comprised of about 3 to about 20 characters having a higher sequence identity with the corresponding region of the other of the initial character strings than the overall sequence identity of the same two columns And selects the sub-columns. 15. The method of claim 14, Wherein the code selects the lower columns so that the end points of the lower columns occur within a predefined motif of about 4 to about 8 characters. 15. The method of claim 14, Wherein the code is arranged so that a connection occurs within an area of about three to about twenty characters having a higher sequence identity in the two different initial states than the overall sequence identity between the two different initial strings Selecting and connecting the lower columns from the other two initial columns. 15. The method of claim 14, The code may be arranged to align two or more of the initial character strings to maximize pairwise identity between two or more lower rows of the character strings and to select a character that is a member of the aligned pair as an end point of one lower row, The computer program comprising: 15. The method of claim 14, Wherein the generated columns are added to the set only when there is at least 30% sequence identity with the initial columns. 15. The method of claim 14, The method further comprising randomly changing one or more characters of the character strings. 25. The method of claim 24, Wherein the method further comprises randomly selecting and modifying one or more occurrences of a pre-selected character in the character strings. 15. The method of claim 14, Wherein the code is stored in a medium selected from the group consisting of a magnetic medium, an optical medium, and a magneto-optical medium. 15. The method of claim 14, Wherein the code is in a dynamic or static memory of the computer. A label generation system for generating a plurality of associated labels, An encoder for encoding two or more initial columns from biological molecules; An isolator for identifying and selecting sub-columns from the two or more columns; A concatenator for connecting the lower columns; A data structure for storing the connected lower-order columns as a set of columns; A comparator for measuring the number and variability of the set of columns and determining if sufficient rows are present in the set of columns; And A command register for writing the set of columns to a raw string file The label generation system comprising: 29. The method of claim 28, Wherein the isolator comprises a comparator for aligning and determining the same areas between the two or more initial columns. 29. The method of claim 28, Wherein the encoder includes means for encoding a nucleic acid sequence into a character string. 29. The method of claim 28, Wherein the encoder includes means for encoding an amino acid sequence into a character string. 29. The method of claim 28, Wherein the comparator comprises means for computing sequence identity. &Lt; RTI ID = 0.0 &gt; 8. &lt; / RTI &gt; 29. The method of claim 28, The isolator is configured to cause an endpoint of the lower column to occur in a column region comprised of about 3 to about 100 characters having a higher sequence identity with the corresponding region of the other column of the initial character strings than the overall sequence identity of the same two columns And selecting the sub-columns. 29. The method of claim 28, Wherein the isolator selects the sub-columns so that the end points of the sub-columns occur within a predefined motif of about 4 to about 8 characters. 29. The method of claim 28, The isolator and the coupler coupling the selected lower columns individually or in combination to each other from two different initial columns, wherein the connection comprises two different initials of the two different initial columns, And in an area made up of about 3 to about 100 characters with higher sequence identity in the thermosyphon. 29. The method of claim 28, Wherein the isolator comprises: aligning two or more of the initial character strings to maximize pairwise identity between two or more sub-columns of the character strings; and selecting a character that is a member of the ordered pair of character strings as the endpoint of one sub-column Features of Label Generation System 29. The method of claim 28, Wherein the comparator adds the columns to the data structure only when there is at least 30% sequence identity with the initial columns. 29. The method of claim 28, Further comprising an operator to randomly change one or more characters of the character strings. 39. The method of claim 38, Wherein the operator randomly selects and changes the occurrence frequency of one or more predetermined characters of the pre-selected character strings of the character strings. 29. The method of claim 28, Wherein the data structure is a data structure that stores encoded nucleic acid sequences. 29. The method of claim 28, Wherein the data structure is a data structure for storing encoded amino acid sequences.