DE10238057A1 - Comparison of a number of parameter sequences, for the design and formation of biological molecules, uses matrix elements with arithmetical logic computing units for faster complex computations of data sets - Google Patents

Abstract

To compare a number of parameter sequences, the parameters contained in them are such that a part of them are combined into parameter combinations by a defined rule. Each parameter combination is assigned a value according to a defined value classification for the characteristics to be measured. The parameter combinations form a multi-dimensional matrix with arithmetical logic computing units. The matrix element (200) has inputs (208,209) for the elements in the parameter sequences (A,B). An intermediate memory (207) stores the results.

Description

The invention relates to a method to compare n parameter sequences, some of the parameters of all Sequences of parameters according to a previously defined regulation can be combined to form parameter combinations and each parameter combination a first according to a previously defined first evaluation rule Value is assigned, and the result of the valuation rule one accessible to a measurement Property corresponds. Moreover The present invention relates to the use of the method according to the invention for the design, formation, design of / or for the selection of substances.

In the field of bio-informatics and materials science fall in large quantities genetic, biochemical as well as substance-specific data. This data, which is made up of many Research efforts result from their common origin connected: the properties of biological and inorganic Substances or molecules.

This requires the two aforementioned Areas large Computer services to catalog this individual information, organize and structure them in meaningful structures.

Generally these are requirements on computers with conventional Systems no longer manageable.

Have been in the past therefore looking for ways to structure the enormous flow of data in a meaningful way, special hardware and software configurations are used were.

For example, from the EP 1094607A1 FPGA (Field Programmable Gate Arrays) cells are known which have user-programmed connection fields. These cells have an array of logic elements and wiring sections that consist of several thousand or even hundreds of thousands of programmable connections, as a result of which FPGAs can be programmed by a user as an integrated circuit for defined functions. Each programmable connection can connect or interrupt a large number of circuit nodes of the integrated circuit as an FPGA cell, as a result of which functions of logic elements of the FPGA can be set in a user-specific manner. By shortening a channel width of channel areas of a switching transistor of an FPGA cell, a smaller space requirement and lower write / read voltages are made possible for the programming of FPGA cells.

Next are from the DE 19654595A1 and memory bus systems for modules with two- or multi-dimensional programmable cell structures, the bus system being produced by bundling several individual lines or buses or sub-buses within a module of the genus DFP, FPGA, DPGA, and all modules with two or more dimensional programmable cell structures, and Via which the modules can be combined into several and / or memory and / or peripheral devices can be connected.

Likewise, the DE 19654846A1 A method for the dynamic configuration of configurable modules with a two- or multi-dimensional cell arrangement, for example FPGAs, DPGAs, DFPs or the like, is available, which has one or more switching tables, consisting of one or more controllers, and one or more configuration memories which blocks are integrated or connected to. Configuration words are transferred from a switching table to a configurable element or several configurable elements of the block or block transfer that set a valid configuration. This means that a programmable module can be reconfigured much more quickly and that various configurations of a programmable module can be used flexibly at runtime without impairing or stopping the programmable module's ability to work. Changes to the configuration of the block are made at the same time and are therefore available very quickly without, under certain circumstances, having to transfer large configuration data. This removes the static restrictions of conventional building blocks and improves the use of existing configurable elements.

From the DE 19651527 A1 Furthermore, a computer arrangement and a method for executing a sequence of program instructions are known, wherein in the computer arrangement a programmable logic module, which is coupled to a processor with a limited instruction set, the logic module expanding the processor or the limited instruction set by at least one instruction. The command that is not contained in the command set of the processor is implemented in the programmable logic module by logic functions. The processing time and the required resources can thus be further reduced in various fields of application, for example in the approximation of function values of arbitrarily continuous functions, in flow arithmetic, in particular also in processors with integer format or in the case of lossless or lossy data compression.

All of the aforementioned systems and processes However, the state of the art had in common that the computing times to process a variety of data was very high.

This is a major disadvantage especially in the field of bioinformatics when evaluating, for example, genetic analyzes, the structure elucidation of proteins, etc., since the results of the evaluation are quick are desired.

From the EP 1136932 A1 For example, a method for designing primers on bio-chips is known, wherein DNA nucleotide sequences are obtained from a database consisting of a plurality of different DNA nucleotide sequences, and wherein the nucleotide sequences of primers are capable of are to bind specifically in the hybridized DNA thus obtained. A large number of primers which are able to bind specifically to different DNAs can be designed in this way.

Bio chips are especially useful Tools in the context of drug development. The biggest advantage consists of expression profiling. Here are DNA microarrays because of their ability the measurement of gene activity in a tissue in a massively parallel manner already unrivaled today. Also in areas other than DNA chips are used, for example, for the duplication of known sequences (Polymerase Chain Reaction PCR) so-called primers are used. at a primer (oligonucleotide) is a short oligonucleotide sequence, which are synthetic in any combination (A, C, G, T, U, with the capital letters for the corresponding bases adenine, cytosine, guanine, thymine and uracil in the DNA or in the RNA) can be created. The primer are usually between 15 and 100 base pairs long.

The term bio-chip or microarray denotes the systematic arrangement of biomolecular probes, such as nucleic acids, (Oligonucleotides, for example cDNA, DNA, RNA, LNA or chimeras thereof) antibodies Peptides or proteins on solid surfaces made of glass, metals or Plastics. The basic principle of such biochip-based methods is miniaturized working in parallel through probe arrays Analysis systems on one if possible small area to get the simultaneous investigation of a large number of parameters.

Gene analysis using oligonucleotide chips is based on ability for example of single strands DNA to form a double helix with a complementary DNA fragment. This process, called hybridization, allows the sequence-specific one Detection of a DNA segment by a probe oligonucleotide (primer), that on a surface is fixed. There will be a bundle of the same primers on one Dot / matrix cell applied. This point / cell is called as a spot. A DNA chip is made up of many different probes, which enables detection of several thousand DNA sections.

Hybridization on a DNA chip is detected, for example, with a fluorescence microscope, in which the examining DNA (or the desired DNA strand) with fluorescent dyes (primer marker) is marked.

So far there are only a few programs for the calculation of optimal primers. This is also disadvantageous the enormous time currently required to execute such programs.

Likewise for the analysis of proteins and (poly) peptides require extensive computing power. Peptide- or protein chips, with the help of thousands of peptides or proteins can be characterized in parallel are currently the only ones Possibility, to the task of peptide or protein characterization in a manageable Time horizon to master. This requires an even greater computing power than, for example, when analyzing nucleic acids or oligonucleotides, because during the nucleic acids are very similar in chemical and molecular properties, there is a multitude of extremely heterogeneous Peptides and proteins.

The function in particular of the proteins supports on their 3-dimensional structure. This structure is sometimes extremely sensitive when the conditions under which the respective proteins naturally are changed become. About that proteins also have enormous differences in size. While it for example, DNA fragments of the same size are possible to the carrier materials socialize, this is for enlightenment the task that the protein performs not useful as this is for that be intact and in the correct conformation.

So protein chips are far more higher Requirements placed on DNA chips. With the currently available Protein arrays are predominantly around antibody arrays, where the specific capture molecules are analogous the DNA microarrays in rows and columns on carrier materials in a very confined space to fish out defined proteins from a pool of proteins and analyze. For the analytics require enormous computing power. However, these are currently so that the analysis of defined proteins takes days. at all proteins in the protein pool are specifically radioactive in the analysis, marked with fluorescent dyes or with biotin and on the Microarray in contact with the capture molecules brought. With appropriate detection methods, the bound to the capture molecules labeled proteins are detected.

Therefore, the preparation of the experiment, especially the design of the experiment made a big contribution on the value of the entire experiment. When designing biochips there it is therefore a big one Need for specialized computers or computing power.

When designing the experiment, large and different databases must be screened with computer support in order to determine the chip content. Biochips can be used, for example, to analyze peptides and / or DNA sequences. Here, for example, is the search for exactly that Of central importance are ligands (oligonucleotides, cDNA molecules, antibodies) which, after being immobilized on the chip, bind their molecular partner precisely from the patient's sample without competing too much with other molecules on the chip to create a partner. As many structural details as possible must therefore be included in the analysis so that the correct chip content can be selected and incorrect results avoided.

Through computer-aided preparation of the experiment, the experimental conditions and especially the selection of primers depending on the type of biochip optimize. Experiments can therefore be carried out optimally in a reasonable time be prepared and a basis can be created from based on a correct interpretation of the measuring points allows becomes.

For example, when browsing of databases in general target properties with the content compared to the database. Also in the optimization of Experiments to make comparisons. With such comparisons different combinations of parameters are usually formed and subjected these combinations to different evaluation steps.

The object of the present invention was, therefore, to provide a method that takes the time shortened even further when comparing n-parameter sequences, see above that simple and complex calculations of a variety of data done quickly can be.

This task is accomplished through a process solved for the comparison of n-parameter sequences, some of the parameters all parameter sequences according to a previously defined regulation can be combined to form parameter combinations and each parameter combination a first according to a previously defined first evaluation rule Value is assigned, and the result of the valuation rule one accessible to a measurement Property corresponds, the combinations of the parameters of the n parameter sequences form and form an m-dimensional matrix Part of this m-dimensional matrix corresponds to a matrix that is arithmetic includes logical processing units.

For a better understanding of the present invention, the essential terms used according to the invention are defined below:
A “previously defined rule” in the sense of the invention means, for example, predetermined instructions for the formation of the parameter combinations, which may be in the form of a calculation rule within a computer program or as part of the computer architecture in the form of integrated circuits. Furthermore, the instructions for the formation of the parameter combinations may be present be predetermined biologically, chemically, physically, or be of a random nature, or combinations thereof, the pre-defined rule generally being present before the parameter combinations are formed.

A "previously defined first evaluation rule" in the sense of the invention means that the evaluation rule in general before performing the assessment exists, and the assessment rule for each of the potential Parameter combinations can be the same or different. The valuation rule causes one or more parameter combinations each one or more values can be assigned. Especially with combinations Assigning multiple values can be useful from more than two parameters. The evaluation rule can take the form of evaluation instructions within a computing program or as part of the computer architecture are in the form of integrated circuits. Furthermore can the valuation rule for the evaluation of the combinations of parameters biological, chemical, or be physically predetermined or be of a random nature or as Combinations of these can be specified. For example, the Evaluation rule coded in a biological and / or chemical system his. In such a system, the evaluation is through the structure and type of molecules coded and the assessment rule by mutual influence of the molecules executed.

Under the term "result" is understood according to the invention the Assigned values to parameter combinations. For example, that Result of the assessment rule a measure for the matching deliver the parameters in the individual parameter sequences. These the parameters are, for example, bases of oligonucleotide sequences, So the result of evaluating the base combinations can be a measure of the bond strength of the include each base combination. On the other hand, become parameters combined with each other, the parts of molecules (atoms or functional Groups), the molecules being, for example, oligonucleotides and / or proteins, the result of the evaluation, depending on the evaluation regulation, a measure of the ability to bind be in a combination between the parameters or, for example, also a measure of agreement be the parameter. In another non-limiting one embodiment In the field of image processing, parameter sequences that Contain strings, compared with each other by means of the inventive method. Such strings can For example, display image sections or word or word sequences (for example, the parameters then correspond to gray or color levels). In image processing, the comparison of character strings provides as a result, for example, a measure of the match and thus can a property is assigned to the result, which states that a certain parameter set corresponds to an image section, the meaning such as street or house.

A "property accessible to a measurement" in the sense of the invention means that with the aid of a Measurement method and suitable systems, one or more measurement results are obtained which, after suitable manipulations, correspond to a property of the result of the invention. The measurement method can be of a biological, chemical or physical nature. For example, the result of the first evaluation rule in the case of an example of a method for selecting primers corresponds to the bond strengths between the base pairs formed by the combination. This means that the property accessible to a measurement is the probability of forming a chemical bond or a measure of the strength of the chemical bond formed, or it can be the probability of the occurrence of the paired oligonucleotide sequences corresponding to the parameter combinations. Such occurrence probabilities for bond formation can be demonstrated, for example, using gel electrophoresis or resonance methods (NMR, ESR, μ-SR, etc.). The measurement results corresponding to the probabilities of occurrence are obtained by comparing (for example forming a difference) the measurement results of systems with bond formation with reference systems without bond formation. In the case of image processing, the result, such as the probability of the presence of a certain object (for example a house), corresponds to various properties, such as temperature etc. This property is accessible to suitable measurement methods, such as thermal imaging camera recordings.

An "m-dimensional matrix" in the The meaning of the invention means that in general the formed Display parameter combinations as a matrix or part of a matrix let, respectively, that in the formation of the parameter combinations a matrix or part of a matrix is created. Each represents Matrix element of the resulting matrix or part a matrix represents a combination of parameters. The dimension m of the Matrix usually exceeds not the number n of parameter sequences.

An "arithmetic-logical computing unit" In the sense of the invention, a matrix or a processing element means which is capable, for example, of any comparative, logical or perform arithmetic operations. Non-limiting embodiments for arithmetic-logic according to the invention Computing units are listed in the description below. The Processing element can be biological, chemical or physical Nature or combinations thereof. The arithmetic-logical also perform Computing units of course also the evaluation of the parameter combination formed.

A “matrix, the arithmetic logical computing units includes " according to the invention means a logic unit, which is preferably designed for parallel data processing. Not restrictive embodiments for matrices according to the invention, the arithmetic-logic arithmetic units are included in the following Description listed.

By the method according to the invention let yourself the speed of the evaluation, for example when searching for optimal physical properties of a sought oligonucleotide, a peptide or the like Accelerate materials by a factor of 1000 compared to conventional processes.

It is preferred if the formation of all or part of the parameter combinations at the same time, for example in parallel, in so-called pipelines (in a computer pipeline an instruction execution divided into several processing steps, each of one for that certain piece Hardware are processed and all run in parallel. The pipeline corresponds to an assembly line, one instruction is completed in each clock cycle can) be carried out will, that is the pipelined data are processed in parallel. Because of the engagement of pipeline, acceleration factors between 10 and 100 im Comparison to the use of conventional Procedure reached.

In a further preferred embodiment of the method according to the invention all or part of the parameter combinations are evaluated also simultaneously, for example in parallel in pipelines. Thereby can speed up the process until you get a result also by acceleration factors between 100 and 1000 be increased.

The evaluation of the combinations of parameters formed by the arithmetic logical Processing units. Any arithmetic logical arithmetic unit execute an individual evaluation rule and the parameter combinations can depending on the type or physical meaning of the parameters individually be sensibly evaluated.

Advantageously, the first values for all parameter combinations from the n parameter sequences after one further assessment rule can be processed further. So that can the result of the first evaluations by means of another evaluation regulation, the example instructions for Totaling or extreme value searches contains, are processed further and reduced to a simpler second result, for example become. This result can then be processed further or, for example, already correspond to a molecule that the desired Properties that are appropriately encoded in the valuation rules are, owns.

Each individual and / or several combinations of the parameters is particularly preferably formed and / or evaluated in one or more logical arithmetic units, for example in differently shaped pipelines (one pipeline, for example, makes a sum, another carries out comparisons, etc.). This will the speed increased by a factor of 100-1000 compared to the use of conventional methods.

Advantageously, n is a whole Number that is greater or is equal to 2. So can two parameter sequences or even more parameter sequences with each other be compared.

In a further advantageous embodiment In the method, each sequence of parameters consists of a sequence of discrete parameters. This allows any combination of parameters directly by combining the discrete parameters from the parameter sequences be formed.

Sequences preferably include the same and / or a different number of parameters. This can also Consequences, for example, different substances or different molecules or parts of molecules correspond to be compared with each other.

Advantageously, the consequences a certain predefined arrangement of the parameters within of the consequences. For example, substances or molecules are in it Structure defined.

The parameters preferably have a accessible to a measurement Property on. This can, for example the parameter properties of measured values (e.g. temperature, Pressure) and / or also whole or partial biological Forms such as cells correspond and / or parts of Correspond to substances such as the bases of primers.

The can particularly preferably Values from the first assignment of values (first valuation rule) subject to further assessment requirements. So that can Result from the first evaluation are processed further, whereby there can be any number of other interim results until finally one Final result available is provided. In the further evaluation steps, different Selection criteria for the design, formation of / or the selection of substances are included.

The result advantageously shows a measurement accessible Property on. For example, the result can be one or more molecules include which, for example, have certain desired properties and / or, for example, properties associated with the molecule (s) in Are related.

The method is preferably used for Comparison of n parameter sequences for the design, formation, design of / or for the selection of substances. This enables parameter sequences, for example from substance databases that contain substance data through suitable evaluation steps with regard to desired Properties are analyzed, for example substances selected or designed or newly formed or redesigned can.

The fabrics are advantageous biological molecules. This can be used, for example, to design suitable biochips be evaluated, or for example also biological properties Gene sequences can be assigned.

The molecules are preferably oligonucleotides. This means that, for example, primers are simply designed or be selected.

Particularly preferably, the Parameters in the parameter sequences of the steps of the procedure the bases of oligonucleotides. As a result, the parameter combinations correspond Combinations of easily accessible and identifiable bases.

The parameter combinations are advantageous formed by two parameter sequences, the n parameter sequences to each other part of all possible Arrays go through, and the arrays by displacement around a discrete parameter. An arrangement In the sense of the invention, a spatial arrangement of the parameters, as well as any permutation of the parameters in n-dimensional real or virtual spaces mean. This allows for example two primers each with a certain arrangement interact so that it is to combination can come from bases or other properties. By the Moving the primer by a discrete parameter can all sensible orders.

The parameter combinations preferably comprise from the part of all possible Arrangements of the parameter sequences base pairs. This can, for example chemical interactions such as hydrogen bonds between the Bases of a base pair are evaluated.

The base pairs are particularly preferred assigned a hierarchizable value. For example, chemical Interactions with regard to the stability of the bond that may be formed be rated.

Advantageously, a part the parameter combinations formed simultaneously and this part and / or part of these combinations formed at the same time Time a hierarchizable value is assigned. This will make the speed by factors of 10–100 compared to the use of conventional Process increased.

The assigned one preferably corresponds Binding strength value the chemical bond between the complementary bases between primer and an oligonucleotide sequence. This allows the bond strength as base for possible further calculations, the selection of, for example, oligonucleotides or Serve primers, are used.

Those are particularly preferred bond strengths corresponding values are subjected to further calculation methods, so that the result is one or more selection criteria for one or represents several oligonucleotides. This allows oligonucleotides that the desired Binding properties correspond to be selected.

The object of the present invention is further by a device for performing the method according to the invention solved, the device comprising a processor and a hardware accelerator for parallel data processing and a memory that with the Processor and / or the hardware accelerator is coupled, includes, to carry out the method or steps of the method according to the invention. In order to can a variety of commands to perform the inventive method be swapped out in the hardware accelerator what the speed data processing significantly increased.

The special hardware structure allows thus the parallel, that is simultaneous implementation from many arithmetic operations to one step, which also means here the speed of processing the data increased accordingly becomes.

The memory preferably has one Part of the program instructions for executing the method and / or for the Operation of the device on, making the process direct and without delay be carried out can and therefore the speed of processing the Data can be increased accordingly.

The hardware accelerator is advantageous coupled to the processor. By coupling the hardware accelerator with the CPU you are able to run computationally intensive processes on the Outsource hardware accelerators. A close coupling is necessary for a fast data exchange between CPU and hardware accelerator perform.

The hardware accelerator particularly preferably contains a logic module for parallel data processing. By the The use of a logic module is used to carry out the calculations / The procedure is coded directly with the logic module and taking into account a parallel and pipelined execution of the operation will Execution speed by a factor of 100-1000 compared to the use of conventional Procedure reached.

The logic module is preferably a programmable logic module. This gives a special flexibility in the Assessment rules for the different assessment steps reachable.

It is preferably programmable Logic module a field programmable gate array (FPGA). The FPGA has a particular flexibility with regard to the selection of the valuation rule and is therefore able to do this in only change in a few milliseconds. In addition, the internal structure of the FPGA is particularly suitable for the processing matrix and the Execute valuation rule in parallel and pipelined. from that this results in a speed factor of 100-1000.

The logic module is preferably a ASIC. Execution as ASIC is especially one that doesn't change any further This is an advantage because an ASIC uses a higher processing speed can be achieved and less because of the higher packing density silicon area is needed.

The device particularly preferably contains a computer readable storage device or a computer readable storage medium.

These can both be in a host computer and / or be arranged in the hardware accelerator. By the When the memory is used, the data to be processed are saved and can during the Calculation instructions quickly and without great delay directly for the calculations be used. The memory on the host processor contains besides the data also the program instructions and can be there without delays work.

The storage unit advantageously comprises or data of the parameter sequences recorded on the storage medium of the procedure. The advantage of storing the Data of the parameter sequence is, on the one hand, the direct and not delayed Access to the data. On the other hand, the memory on the hardware accelerator as well as the data to be processed and at the same time for the result data be used. This memory is therefore used twice.

It is understood that the above not only mentioned and the features to be explained below in the specified combination, but also in others Combinations or alone can be used without the frame to leave the present invention.

Advantageous, non-limiting, Embodiments of the invention are further in the drawings and the associated Description explained. Here show:

1 a schematic representation of the device according to the invention;

2 the construction of a processing element (matrix cell);

3 a schematic representation of the device according to the invention and the sequence of the method according to the invention therein;

4 a flowchart to illustrate the sequence of the method according to the invention;

5a a section of the schematic process flow;

5b a matrix of the device according to the invention and the method running therein when comparing two oligonucleotide chains.

1 shows a schematic representation of the device according to the invention 100 , The device according to the invention 100 includes a combination of a CPU (central processing unit) 101 in combination with a hardware accelerator 102 , where these two components 101 and 102 via an interface 103 are interconnected.

The CPU 101 can be located in a so-called host computer, not shown. The host computer can be, for example, a PC, a workstation, an embedded processor or a server, or else in peripheral devices, for example. Analyzers are available. The host computer comprises components such as CPU, memory, input / output devices and / or further peripheral devices known to the person skilled in the art, as well as buses and interfaces. An application sequence with the device according to the invention 100 takes place as follows: Data is entered into the host computer by a user and / or read from already existing files. The data entered there can be stored on the host computer in the CPU 101 be preprocessed or alternatively in the hardware accelerator 102 The preprocessed data is then sent over the interface 103 to the hardware accelerator 102 transfer. On the hardware accelerator 102 this data is calculated using one or more in 1 Logic units not shown or in one in 1 parallel structure for parallel data processing, also not shown. After the calculation is finished, the result data is sent via the interface 103 to the host computer / CPU 101 transferred back. There, the data is post-processed and the results are displayed to a user on a screen and preferably stored in a file.

The components of the device according to the invention 101 are further explained below:

CPU 101 :

CPU is understood to mean a “central processing unit”, that is to say a central processing unit. The CPU 101 executes programs loaded into main memory. The CPU 101 retrieves the instructions of the programs, checks them and executes them one after the other. The CPU 101 may include various components such as a control unit, an arithmetic logic unit (ALU) and registers. The components are interconnected via a bus. It consists of several parallel lines for the transmission of addresses, data and control signals. Buses can also be outside the CPU and connect them to the memory and various input / output devices. The CPU 101 can preferably also have standardized interfaces to device components such as a hardware accelerator. The CPU 101 can be a conventional CPU that resides on a single conventional CPU chip, such as an INTEL Pentium I / II / III / IV processor chip, Intel PowerPC, embedded processor strongARM from ARM.

interface 103 :

Next is in the device according to the invention 1 an interface 103 shown. the interface 103 has the task of enabling bidirectional data transmission. Alternatively, two unidirectional connections are of course also possible. In the context of the invention, "bidirectional data transmission" means that both data from the host computer / CPU 101 on the hardware accelerator 102 , as well as hardware accelerators 102 to the host computer / CPU 101 can be transferred.

interfaces 103 In the sense of the invention, for example, a PCI bus or they can also be part of the CPU 101 of the host computer or part of the parallel computing unit in the hardware accelerator 102 be, but are not limited to. A PCI bus is understood to be a so-called "peripheral component interconnect" bus. In the device according to the invention 100 this bus becomes the communication from CPU 101 and hardware accelerators 102 used. Additional devices can also be connected to the PCI bus. In addition, other such buses can be included in the device, which also serve for communication between other device components. The PCI bus is a very popular bus that can be found in practically every Intel-based computer since the Pentium. The PCI bus is described in detail in Shanley, T. and Anderson, D .: PCI System Architecture, 3rd edition, Reading, MA, Addison-Wesley, 1995b and Solari E. and Willse, G .: PCI Hardware and Software Architecture and Design, 4th ed. San Diego, CA, Annabooks 1998. The PCI bus runs at approximately 32/33 or 64/66 MHz, which corresponds to a cycle time of 15 ns. It handles 32 or 64 bit transfers, which means that 32 or 64 bits are requested per cycle. It has a very high bandwidth of 528 Mbyte / s in total.

Other possible interfaces can be, for example, an ISA bus (ISA means "Industry Standard Architecture ") or an EISA bus (EISA means" Extended ISA "), USB, PCI-X, Fire Wire, PCMCIA, a bus system within a systems-on-a-chip, connection network on the chip / die. The interfaces can be part of a CPU or a processor for parallel data processing.

hardware accelerator 102 :

Next is in the device according to the invention 100 according to 1 a hardware accelerator 102 shown. The hardware accelerator 102 , which can also be referred to by the term “coprocessor”, can comprise a multiplicity of components. Core of the hardware accelerator 102 is one in 1 Logic unit, not shown, for parallel data processing. This logic unit can for example consist of one or more programmable FPGA chips (FPGA means “Field Programmable Gate Array, see also The Programmable Logic Data Book, 1999; Xilinx Inc. 2100 Logic Drive, San Jose, California 95124, USA), one or more hybrid FPGA chips, one or more ASIC chips, logic modules, analog circuits or CPU clusters or be composed of combinations thereof. A hybrid chip is a combination of a "traditional" CPU and an FPGA module. These two processor elements are housed in one housing. The data exchange between the CPU and the FPGA core is carried out via appropriate interconnects. (Xilinx Virtex II Pro Data Book http://www.xilinx.com/publications/products/v2pro/ds pdf / d083.htm)

If in the hardware accelerator FPGA chip is used, so are for the operation of the hardware accelerator the following components are typically, but not exclusively, necessary: an FPGA module, a RAM module, a clock generator, a PCI interface module, a PCI card, a programmable control logic unit and an operating system. With other hardware accelerator architectures, for example when using an ASIC or a CPU cluster different modules are not, or not in the configuration or other modules required.

The parallelism in the device according to the invention 100 can be introduced at different levels. At the instruction level (instructions), for example, pipelining (parallel processing in pipelines and parallel pipelining) can be used. See Agerwala, T. and Cocke, J .: High Performance Induced Instruction Set Processors, IBM TJ Watson Research Center Technical Report RC12434, 1987. With a so-called "pipelined" design, the performance of the computer can be reduced by approximately a factor compared to a purely sequential design In order to be able to achieve an increase in performance by a factor of 100 up to several thousand, however, a multiplicity of instruction pipelines must be used in parallel, all of which must work efficiently with one another In particular, a parallelism of data processing in the pipelines is preferably used at the instruction level, whereby the parallelism of data processing can be achieved by simultaneous operation of many ALUs that are either on a chip, such as an FPGA chip, and / or, as is the case with multiprocessor systems or multiprocessor systems the case is on v Many chips are distributed. Such multi-processor or multi-computer systems have several independent CPUs that work as part of a larger system.

Data transfer from the CPU 101 to the hardware accelerator 102 over the interface 103 depends on the direction of the transmission indicated by the arrows in 1 between the CPU 101 and the hardware accelerator 102 are shown and comprise two data transfer paths described below, which, however, are to be understood only as examples, but not as restrictive. As an alternative to the transmission of the data as data words, the transmission of the data can also take place bit-serially. The data can be transmitted as an ASCII (standardized character set) character stream, as a binary coded bit stream or using another suitable coding. A transmission with encrypted data must also be included.

Data transfer 1: The data transfer from the CPU 101 to the hardware accelerator 102 uses an in 1 Data packet, not shown, by the CPU 101 on the hardware accelerator 102 is transmitted. The data packet includes, for example, a so-called header, which consists of two data words and defines the number of subsequent data and the offset position from which the data are stored in the first RAM. The subsequent data is stored in RAM in ascending order. Of course, any other structure equivalent to this and known to the person skilled in the art is also suitable for the data transfer described above.

Data transfer 2: the data transfer from the hardware accelerator 102 to the CPU 101 requests the data by writing a data packet that contains only one header. The data is then from the CPU 101 read directly and stored in the memory of an associated host computer. Of course, any other structure equivalent to this and known to the person skilled in the art is also suitable for the data transfer described above.

Advantageously, the data between the host computer and the hardware accelerator are transmitted in a burst using DMA mode in order to achieve a minimum data transmission time, of course other transmission methods known per se to the person skilled in the art can also be used according to the invention.

2 shows the structure of a matrix element 200 that is part of an in 2 is not shown matrix. This matrix in turn is part of an in 2 Hardware accelerator, not shown, for example a hardware accelerator 102 according to 1 , The arrows in 2 schematically show the sequence of the method according to the invention in such a matrix element 200 , A matrix element 200 defines a processing element within a processor unit in the hardware accelerator. The matrix or processing element in a special embodiment is, for example, an 8-bit multiplier (arithmetic logic unit), but it can also be any arithmetic and / or logic unit, or a CPU, several cells, an ASIC or a cluster of different ones or the same processors. For example, it can also be a hybrid chip. A hybrid chip is a combination of a "traditional" CPU and an FPGA module. These two processor elements are housed in one housing. The data exchange between the CPU and the FPGA core is carried out via appropriate interconnects (see, for example, Xilinx Virtex II Pro Data Book http://www.xilinx.com/publications/products/v2pro/ds pdf / ds083.htm) A processing element can consist of a group of registers (1 to 32 bits), which form a local memory, and one arithmetic logic circuit called ALU. The ALU can perform simple arithmetic operations. The registers are connected to the ALU, which is the data path through which the data flows. As a basic operation, the data path selects one or two registers. The data path continues to consist of several buses connecting these parts, the ALU itself carries out additions, subtractions and other simple operations the inputs it receives and thus delivers a result, for example in the output register. The result can also be saved in another memory. These arithmetic arithmetic operations are implemented by logic circuits. These circuits are tiny switching elements that are contained in integrated switching chips, for example the chip of the matrix, which can be, for example, an FPGA chip, individually or in combination. These switching elements, which are also called gates, are usually AND, EXOR, OR, NAND, NOR and NOT. AND, EXOR, OR, NAND and NOT are symbols of Boolean algebra. Simple circuits can be implemented by combining individual gates. The components of memories can be flip-flop circuits or latches. These circuits can be combined to form multiple and also more complex memories. The various components, such as circuits for arithmetic operations and memories, are connected via buses.

The arrow A in 2 places the i-th element of a first in 2 Parameter sequence not shown 1 In a special embodiment, the i-th element is, for example, a base of an oligonucleotide, such as a DNA / RNA / LNA or chimeras thereof. The arrow B in 2 also places the jth element of a second in 2 Parameter sequence not shown 2 j and i can be the same or different. In a special embodiment, the jth element is, for example, a base, an oligonucleotide, such as, for example, a DNA / RNA / LNA or chimeras thereof.

The parameter sequences are sent to the two inputs 208 for the parameter sequence 1 and 209 for the parameter sequence 2 the matrix. The structure of the data processing is designed, for example, in a comparison such that a data word can be fed into the matrix with each cycle. The comparisons for a complementary match are carried out within the individual cells of the matrix. This comparison is carried out via a look-up table (LUT), which outputs the weighting factor of the match as a result. A LUT (LookUp Table) corresponds to a ROM (Read Only Memory) or a RAM (Random Access Memory), which has stored user-specific values. When comparing several possible input parameters, one is able to determine a match or a complementary match within a cycle and output it as a result. The parameters to be compared are created as addresses on the LUT and the addressed value that is stored for this address in the LUT corresponds to the result of the comparison.

In the particular embodiment of the matrix mentioned above, the parameter sequences are 1 and 2 Bases of an oligonucleotide, such as a DNA / RNA / LNA or chimeras thereof. The individual bases of the parameter sequences 1 and 2 coded with two bits each and to the matrix cell 200 created. The comparator is designed as a LookUp table, which corresponds to ROM (Read Only Memory) or RAM (Random Access Memory). The two inputs of the two parameter elements i and j are used as the address of the LookUp table. The result is encoded in the addressed entry, which is then immediately forwarded to the output. The weighting function is thus directly integrated with the comparison in the LookUp table.

In general, the comparison can and the subsequent one Weighting also by any arithmetic functions such as addition, Multiplication, etc., or by combinations of these arise. The weighting of the output can also be more complex Represent function, for example, by additional input signals can be influenced.

Every matrix cell 200 determines the result in parallel and makes it available to the next level supply. The registry 207 to cache the results is optional.

3 shows a detailed representation of the device according to the invention 300 , It is the components involved within the host computer 301 , especially the host processor (CPU) 306 , the interface 304 and the hardware accelerator 302 shown. Further illustrated 3 the sequence of the method according to the invention, in particular the data flow in the hardware components of the device according to the invention 300 ,

On the host processor side 306 shows 3 a workstation / host computer 301 with a conventional equipment known per se to the person skilled in the art. This equipment includes the host computer 301 , Input devices such as mouse and keyboard 308 , a monitor 307 as a display device and a network card 309 and other optional common hardware components 310 , Such hardware components 310 can be peripheral devices such as a CD-ROM drive, a floppy disk drive, video card, graphics accelerator, and the like. When represented in 3 is a possible configuration. A host computer is also conceivable 301 with only one network card, which is then used “remotely”, that is to say by remote control, via the network from a second computer. Likewise, so-called “embedded processing” by means of embedded systems (embedded systems / processors), for example in peripheral analysis devices possible. On the hardware accelerator side 302 show the 3 a hardware accelerator 302 with an FPGA module 303 is equipped and with the necessary components. Of course, there are also several FPGA modules in a device according to the invention 302 used. The task and functionality of the components are explained below:

PCI interface module 322 and PCI bus 304 :

With the PCI bus 304 is a medium over which several cards / devices exchange data. The PCI interface module 322 has the task of transferring data over the PCI bus 304 to manage and only those for the hardware accelerator 302 relevant data to those on the hardware accelerator 302 forward connected blocks.

control logic 320 :

The control logic 320 has the task of providing basic functionality for operating the hardware accelerator 302 provide. This functionality includes the configuration of the FPGA module 303 , This basic functionality can act as a "quasi operating system" for the hardware accelerator 302 be seen. The control logic 320 is, for example, from the host computer 301 from or directly from the hardware accelerator 302 driven. It should be noted that this control logic 320 is particularly necessary when using FPGA technology. In the hardware accelerator according to the invention 303 a programmable local or external (host library) control logic is preferred, 320 used. When using a configuration memory, for example an EEPROM, which can be located both outside and inside the FPGA, the control logic is not completely necessary and can also be omitted completely in these cases.

clock generator 321 :

For operating, in particular for synchronous operation, the blocks on the hardware accelerator 302 a clock generator is necessary. This can be adjusted in frequency. The clock generator 321 is host computer 301 checked out. Alternatively, a fixed clock generator can be used 321 are used. The clock generator 321 serves the synchronization of digital circuits. With the help of the clock generator 321 Time relations can be defined, for example, to determine the chronological order in which events are to happen or to synchronize the simultaneity of events.

RAM modules 305 :

With the help of the RAM modules 305 data is saved. The RAM modules 305 can be present both inside the processor element and externally. Their number is arbitrary and will be chosen according to the calculation requirements.

Processor element (FPGA) 303 :

The matrix 325 in the hardware accelerator 302 In a special embodiment of the invention, an FPGA module, which is defined as a processor element, can be used 303 his. An FPGA module or processor belongs to the class of array processors. An array processor is based on the basic concept that a Control unit for steering many matrix elements, which are also defined as processing elements, provides signals, that is, it sends instructions. Each processing element consists of a CPU or an extended ALU and can have local memory. Since all parts are controlled by a control unit, the processing elements march in tightly closed sections.

In the in 3 The illustrated embodiment is an FPGA processor 303 shown. The FPGA module used in the exemplary embodiment has processing elements which are referred to as a configurable logic block (CLB configurable logic cells) and which have one or more 4-bit look-up tables, one or more 1-bit registers and further basic logic circuits. The physical matrix size of the CLB is typically between 10 × 10 and 10 ⁶ × 10 ^6. Further, non-limiting examples of the matrix of processing elements according to the invention (FPGA modules) are given in Table 1 below:

Table 1: Examples of processing elements and their matrix size.

A matrix element has 4 × 4 bit LUTs (The Programmable Logic Data Book 2000 ; Xilinx Inc.) The processing elements from Table 1 are available from Xilinx. It goes without saying that other processing elements with different, for example even larger, matrices can also be used according to the invention.

By interconnecting a number of CLBs, a processing matrix can be built up within the FPGA whose physical matrix size is between 1 × 1 and 10 ⁶ × 10 ⁶ , preferably between 16 × 16 and 30 × 30. The size of the processing matrix and the individual matrix elements themselves are preferably defined in advance, but are also defined in a variable manner. Logical comparisons are carried out within the cells of the processing matrix using a LUT and the two values applied. Of course, any logical or arithmetic operation, such as multiplication, is conceivable within a cell of the processing matrix and can be achieved by interconnecting two or more CLBs of the FPGA module.

In an FPGA processor 303 are the processing elements within a matrix 325 arranged and are interconnected in a complex manner. Such processors are particularly suitable for processing two-dimensional problems and are particularly suitable for matrices. They can also be scaled up well by adding additional processors to the processors present in the hardware accelerator. This increases the computing power, which means that significantly more parameters can be processed at the same time. The hardware can thus be adapted to the problem: Due to the number and arrangement of the processors used, higher-dimensional matrix problems can also be dealt with, such as when comparing more than two parameter sequences at the same time. In addition, longer parameter sequences can be processed or compared with a larger number of processors. In the data flow processors according to the invention, either the control unit can determine which instructions are to be carried out, or each processing element 303 itself ent decide whether it wants to execute an instruction or not, mostly on the basis of local data such as condition code bits. In the embodiment in 3 is inside the processor element 303 a sequence controller 323 available. This controls the data flow in the processor element 303 , It controls the processing elements and storage elements 305 that are both inside the processor 303 can also be present externally.

The arrows symbolize the course of the method according to the invention in a device according to the invention 300 ,

The method according to the invention is further illustrated of a method for determining primer sequences as an example illustrated without including it a limitation of the method according to the invention should be understood.

For the determination of the primers will initially be two sequence areas selected from each sequence to be detected (target sequence). This Areas are usually longer as the optimal primer to be found for each target sequence. additionally be for the determination of the primers takes other parameters into account (e.g. primer length, temperature Etc.). These parameters determine the selection criteria for the evaluation function. The potential primer candidates run through in the calculation for any given Target sequence several calculation methods. One of these assessment procedures is the one-to-one comparison of individual base pairs. The partial results are combined into one result in an overall evaluation.

The entire calculation is divided yourself in two stages. In the first stage, the individual primers evaluated separately and the optimal primers determined. In the second Level is the interaction between the primers of each one Target sequence examined with the primers of all other target sequences.

The following is the first stage described in the calculation. These calculations are further subdivided in the areas a) generation of primers, b) calculation of the parameters of the primer c) evaluation of the determined values. These three areas a), b) and c) are explained in more detail in the following sections.

The primer generation, that is to say the combination of the primers, is carried out as follows: Individual primers are to be extracted from a predetermined DNA sequence and are used for the calculation. The primers are extracted on the basis of the given DNA sequence and the length specification for the primers. A predeterminable number of primers is generated for each length. The number is calculated by:
Number of primers = (DNA sequence length) - (primer length) + 1

Condition: the DNA sequence is longer, i.e. has more nucleoside units than the primer.

Starting at the first sequence position the primers are determined. This process is given for each primer length repeated.

und soll die Primerlänge bei 10–11 Basen liegen, so werden folgende Primer ermittelt: 10 Basen besitzen sind folgenden Primer:

und 11 Basen besitzen die folgenden Primer:

For example, if the DNA sequence is:

and if the primer length is 10–11 bases, the following primers are determined: 10 bases have the following primers:

and 11 bases have the following primers:

Now the parameter sets for the optimal Primer set can be determined. There are the following important boundary conditions: The primers are allowed not bind with yourself, but also not with the others the chip. The primers are allowed also do not bind with the markers. The first and second boundary conditions apply also for Marker.

When calculating all possible Combinations of the primer (which are generated by the first stage "primer generation" are determined) with the reverse primer.

The parameters to be calculated are: a) Self Annealing (SA), b) Self End Annealing (SEA), c) Further calculations (Additional Features such as temperature and GC ratio).

The calculation of the SA values is carried out, to study binding with the same primer. If there is a bond with itself, the bond with the Prevented sequence to be searched and an incorrect test result is produced.

There is the following calculation rule: The calculation is carried out by determining all possible combinations of the overlay. When determining the SA value, only the complementary matches (A⟺T and C⟺G) are added together. When adding up, it does not matter where the matches are. Only the existence of a match is relevant. The weighting the combination found is different (A? T = 2; C? G = 4). It goes without saying that other weightings are also possible within the scope of the invention. Due to the biological properties, the primer only has to be tested in reverse order against the primer. For example, the primer to be examined with the 4 bases AGTC. tested against the reverse primer CTGA as follows: There are 7 overlays to calculate SA. In the example, the first two overlays to be evaluated are shown, the other 5 overlays are by shifting the reverse primer relative to the primer to be examined in order to form a base. The first overlay is:

The total calculations to be carried out for the example with a length of 4 bases are shown in the table below: Table 1: Table with the evaluations to be carried out for the 4 base example in the SA calculation

When calculating the SEA value the binding of the individual primers to themselves is also tested, to determine the applicability of the primer. For the calculation the SEA values comes a very similar one Calculation method as in the case of determining the SA values for Application. For the determination of the SEA values only the primer combinations are interesting, that start at the end of the primer. That is, only those are for the calculation To consider primer combinations, where the last base interact with a base of the reverse primer can be found until the first occurrence of a mismatch. All subsequent matches are not added.

For example, as in the case of the SA value calculation, the primer to be tested with the 4 bases AGTC is tested against the reverse primer CTGA as follows: There are 4 superimpositions for the calculation of SEA. In the example, the first two overlays to be evaluated are shown, the other 2 overlays are by shifting the reverse primer relative to the primer to be examined in order to form a base. The first overlay is:

The second overlay is:

In contrast to the determination of values in the SA calculation, only the matches in the SEA calculation added up, starting from the last position in the primer until the first mismatch occurs. matches after this position are not added.

The weighting of the matches found is identical to that for the SA calculation.

To clarify this calculation are the resulting calculations in the table below summarized.

Table 2: Table with the evaluations to be carried out for the 4 base example in the SEA calculation

For For each primer determined, further calculations are carried out for the latter Overall rating of the primer can be consulted.

The evaluation of the determined values done for every primer generated in the first stage. The determined values for the SA and SEA and for the further calculations are each based on a weighting factor merged into an overall result. In a special embodiment only the maximum received is taken over as SA / SEA value and with the weighting factor added. It goes without saying that a different weighting and / or Calculation rule require corresponding modifications that the specialist works without inventive step to be able to implement immediately.

In addition to determining the Overall results are the individual results with the transferred Compared parameters. The parameters describe an area in which the results are valid. If one of these areas is violated, the calculated primer is used discarded and considered invalid classified.

All valid values become the best primer determined and for the processing is cached in the second stage.

Below is the second stage described in the calculation.

Interaction between primers of the individual spots, between primers and primers and between to evaluate the markers, again come the calculation methods SA and SEA to wear.

In this stage, however, the same primers are not tested against themselves, but one primer (corresponds to a result from the first stage) is compared against another primer. It will So a pairwise comparison of all possible primer combinations was carried out.

The parameters to be calculated are a) Pair Annealing (PA) and b) Pair End Annealing (PEA)

The calculation methods for PA and PEA essentially correspond to the procedures in the determination of the SA and the SEA value, although obviously also deviations fall within the scope of the present invention. Details of the Calculation are explained above. The calculation methods are basically the same, but this can Calculation procedure for the PA and PEA calculation, for example, also primers with different Process length.

For for each primer determined, further calculations are carried out, which for the later overall evaluation of the primer.

This process sequence is described below using the device according to the invention 300 carried out. In the specific, non-limiting exemplary embodiment, the special method of determining the primer is described using 3 explained. In the exemplary embodiment described below, the special method for primer calculation was implemented on a PC system (Pentium III 500 MHz) and an FPGA processor (microEnable 2/2 × 1 Mbyte RAM). This exemplary embodiment describes an implementation as an example. When other components are used, the method described below naturally changes without departing from the scope of the invention. The process is divided into five steps, which are described below.

Step 1:

On the computer 301 , or the host computer, a program is running that accepts and / or reads the data to be processed. The entered data is then compressed and converted into a data format suitable for transmission. After the data format has been created, the data is transferred via the interface 304 to the hardware accelerator 302 transferred and there via the interface module 322 and the optional drain controller 323 , which can also be replaced by suitable software in a RAM module 305 cached. The sequence controller 323 controls the reading of the primer data from the RAM module 305 , This RAM can be both inside the processor element 303 as well as an external RAM module. This step is represented by the arrows marked with a "1". This transmission also includes the transmission of parameter data which are required for the later calculation.

Step 2:

After the transfer, the processing of the data on the hardware accelerator starts 302 , In this second step, the individual primers are generated from the sequence data and as input data 324 to the matrix 325 handed over for calculation. Within the matrix 325 the values for SA and SEA are calculated and then after the evaluation procedure 328 passed. In parallel, further calculations 326 . 327 carried out on the basis of the primer data and also the evaluation method 328 fed. These calculations are in 3 as a calculation 1 (326) to calculation N ( 327 ). The best 64 results E are then in a second RAM module 305 (external or internal). This calculation is carried out for each of the transferred DNA sequences. This step is shown with the arrows marked with a "2".

Step 3:

After calculating the individual primers, the best pairs of two successive primers are determined. The primer pair data of an even and an odd primer are determined (P1 + P2; P3 + P4; P5 + P6; etc.). The result data (from step 2) become from the second RAM 305 read. In parallel, the sequence data from the first RAM 305 read. The processing of this data takes over the same unit of the matrix 325 , whereby the calculations carried out in parallel are not taken into account in the evaluation. The partial results of the primers from the first stage are then combined with the results determined in this stage. The best 5 primer pairs of a combination (even with odd primers) are then stored in the second RAM. This step is shown with the arrows marked with a "3".

Step 4:

In the fourth step of the processing, the data are read from the second RAM and sent to the host processor 306 transfer. Both the results from step 2 and step 3 are read out. This step is represented by the arrows marked with a “4”.

Step 5:

Once the data is transferred to the host processor 306 the results are subjected to post-processing. During the postprocessing, the sequences found are selected and, together with the determined results, shown to the user on the monitor 307 shown and written to a file.

In the special embodiment of the primer determination of the method sequence according to the invention in 3 the data is used in special data formats.

The data is inside the host computer 301 preprocessed. This preprocessing converts the input data into the subsequent data format. This data format is stored in the computer's memory 301 prepared. Data is transferred via DMA access. The data formats for storing the data in the two RAM modules differ due to the data required for the calculation. The formats for the two RAM modules are defined in the following sections.

The data format of the sequence data and parameter data according to which this data is stored in RAM bank 1 305 are described below.

The memory is divided into 1024 blocks 64 words of 32 bits each. Each of these blocks stores a sequence, from which the respective primers are extracted. Following the 1024 blocks there is another block attached which is the parameter data for contains the second part of the calculation.

It goes without saying that the limitation to 1024 blocks and 64 words per block is not a basic limitation, but a freely chosen one Limit for the special embodiment and can be freely selected depending on the intended application can.

In the block with the parameter data for the second calculation is two 32 bit words for each Primer pair that is calculated. Within the two words the parameter data for the PA and PEA calculations are saved. The in the two words saved parameters are: PA minimum, PA maximum and PA optimum, as well as PEA minimum, PEA maximum and PEA Optimum.

The sequence is saved one block with 64 addresses of 32 bits each. This block divided continue in an area that contains the parameters necessary for the block contains and a block with the sequence data. From this division results yourself a maximum length of 944 bases per sequence.

The sequence data is structured in such a way that 16 bases are encoded for each data word. The sequence controller 323 reads in the data as required and generates the individual primers for the calculation.

The parameters for the calculation of the first step are stored in the lowest 5 data words. These parameters are used by the sequence controller at the beginning of each calculation 323 read in and saved in the evaluation function.

The data format that the result data stores from the first and second step is described below.

The RAM bank 2 is divided into blocks with 256 entries each per sequence. The entire area consists exclusively of Packets of 256 words each.

128 words are required to temporarily store the results from the first step, because each result is coded in two data words. These results are within the block in descending order from the address 127 stored.

The area between the block address 128 and 256 is reserved for the results of the second step.

Based on the calculation one Primer pairs (odd and subsequent even primers) are created for them two blocks only one result at a time. This result is only within the odd blocks saved.

The following non-limiting embodiment of the inventive method shows the acceleration when calculating primers against one Sequential execution method of process steps:

embodiment

The measurements of the software execution were executed on a Pentium III 500 MHz / 128 MB RAM. The The total duration of the procedure was 1920 s.

The measurements on the hardware accelerator were on a microEnable II system with a Virtex 400 FPGA executed at 50 MHz. The total duration of the process according to the invention was 3.41 s. to execution a host computer system was used for the measurements following parameters: Intel Celeron 500MHz / 128Mbyte.

The resulting acceleration factor of the method according to the invention compared to a conventional one Procedure is 563.05.

4 shows the sequence of the method according to the invention 400 in a hardware accelerator. The Process sequence according to the invention 400 is illustrated in more detail using a procedure for determining primer sequences. Furthermore, the flow chart shown is 400 specifically for the processing of parameter sequences according to the invention on FPGAs. Individual parts of the processing are different or unnecessary when using other processor technologies. 4 illustrates the process of the entire calculation and shows the program sequences in the software and on the hardware accelerator in detail.

The procedure 400 within the hardware accelerator 401 reduces to the representation in 4 , At the procedural step 402 the hardware accelerator is waiting 401 until he gets data from that in 4 host computer not shown gets transferred. As soon as this data is transferred from the host computer, this data is read in in step 403 and stored in the first RAM bank. Immediately after saving, the calculation of all individual primers of each sequence starts. In step 404, the primers are generated and then fed to the processing components. In step 405, the SA and SEA values in the matrix are calculated. Step 406 runs parallel to step 405, in which further calculations are carried out. In step 407, the results are determined using the evaluation function. In step 408, the best results are collected. Step 409 involves querying whether the last primer in the sequence has been calculated. In the event of a no to this question, the procedural steps are repeated 404 to 409 run through. In the event of a yes to the query in step 409, that is to say after all primers have been calculated, in step 410 the best results are stored in the second memory, namely in the RAM bank 2 stored. In step 411 the next sequence is addressed. Step 412 includes the query whether the last sequence with the associated calculated primers has run through. In the event of a no to this question, the procedural steps are repeated 404 to 412 run through. In the event of a yes to the query in step 412, step 413 is carried out. In step 413, the second stage for determining the PA and PEA values that are in 4 is not shown in detail. After the second stage has been completed, the data is read back from the host computer in step 414 and displayed.

5a shows the process flow according to the invention 500 in a matrix 503 , The illustration illustrates a particular aspect of the invention, namely the structure of a matrix 503 from the individual combinations of the m parameters from the n parameter sequences, in this case the parameter sequences 501 and the parameter sequence 502 that should be compared. Both parameter sequences have 4 parameters. It goes without saying that, of course, also parameter sequences with more than 4 parameters can only be selected in each case or together 4 parameters without going outside the scope of the invention. The number m of parameters to be compared can be selected as desired and is determined by the logic resources available, for example ALUs. This matrix structure of the matrix 503 finds its correspondence in the matrix of a parallel processing system within a device according to the invention. The matrix 503 has 16 matrix elements 507 which comprise at least one arithmetic logic arithmetic unit. In the matrix elements 507, the calculation of the individual combinations of parameters takes place in parallel, that is to say simultaneously. This simultaneous processing of the individual combinations accelerates the entire process by several orders of magnitude.

The processing of the parameter data when comparing the first parameter sequence 501 (also parameter sequence 1 called) with the second sequence of parameters 502 (also parameter sequence 2 ) is in three stages, which in 5a with the digits 1 . 2 and 3 are shown. Both parameter sequences 501 and 502 have the same number of parameters, namely 4. The matrix 503 becomes from the individual combinations of the parameters from the two parameter sequences 501 and 502 built up. It is important in connection with the present invention that all conceivable possible combinations of the m parameters of the n parameter sequences to be compared are formed at the same time, although other processing options can of course also be used within the scope of the invention. Denote the parameter combinations with (i, k), where i is the i-th parameter of the parameter sequence 501 and k is the kth parameter of the parameter sequence 502 is, so is the matrix 503 composed of elements (i, k), in which case i the values 1 to 4 passes through and also k the values 1 to 4 passes. The parameter combinations (i, k) are the comparison cells, that is, the matrix elements 507 the matrix 503 assigned to the parallel processing system. The matrix built up 503 with the comparison cells 507 is in 5a seen in the 1st stage of the calculation. In the comparison cells 507 In the 1st stage of the calculation there is a simultaneous evaluation of each parameter combination (i, k). This assessment is based on a 1st assessment rule. The 1st assessment rule can be used for each comparison cell 507 be the same, but it can also be the same for every comparison cell 507 effect an individual evaluation, whereby these individual evaluations can be the same or different from one another, or can be partly identical or partly different from one another. The evaluation of the comparison cells 507 provides the first results in 5a as arrows 508 that started in every comparison cell 507 have are shown.

These first results can optionally be based on a second evaluation rule 504 are combined in step 2, whereby all or part of the first results can be combined with one another. Each individual 1st result can also be changed individually, with the 2nd evaluation rule for each 1. Result may be the same or different, or may be partially the same or different. The first results can also remain unchanged in their value. In 5a causes the 2nd assessment rule 504 a combination of the comparison cells 507 in the diagonals of the matrix 503 , This combination is done according to the 2nd assessment rule 504 and can be a combination, for example, by an arbitrary arithmetic operation, such as addition, subtraction, multiplication, division. Logarithmic evaluation, etc. or by using arithmetic operations. The second results formed in this way are in 5a as arrows 505 shown.

The second results 505 can optionally be processed according to further optional downstream assessment rules. The second results can optionally be based on a third and further evaluation rules 506 in stage 3 can be combined with one another, whereby all or part of the second results can be combined with one another. Each individual second result can also be changed individually, whereby the third and further evaluation rules for every second result can be the same or different, or can be partially the same or different. The value of the second results can also remain unchanged. The 3rd and other evaluation regulations 506 in stage 3 alone or in any combination with one another ultimately lead to the result 509 which can be read as result E by the user.

In the special embodiment of the primer determination, the task of the matrix is 503 the calculation of the Self Annealing (SA) and the Self End Annealing (SEA) value. Due to the functional equality in the calculation, the matrix 503 in a slightly modified form can also be used for the calculation of the pair annealing and pair end annealing value.

5a explains the structure of the matrix 503 out 5a for the special embodiment of the primer determination. All possible combinations of overlays of two primers are to be evaluated and the weighted matches have to be added up, depending on the calculation of annealing or end annealing.

The first sequence of parameters 551 and the second sequence of parameters 552 correspond to the first and second primer. In the case of the calculation of the SA and SEA value as explained above, the second primer has the exactly opposite base sequence of the first primer. As explained above, the primers are different in the case of PA and PEA value calculation. In every comparison cell 554 the matrix 550 a base combination of a base of the 1st and 2nd primer is evaluated according to its binding strength, as explained above according to a 1st evaluation rule. In the second stage, these values are for each diagonal 555 the matrix 550 , formed from the individual diagonally arranged matrix elements or comparison cells 554 according to a second assessment rule 553 (respectively. 504 in 5a ) added up. The result ( 505 in 5a ) is the sum of the weighted matches in the respective diagonal 555 have been determined. The number of values per diagonal 555 to be added depends on the position of the diagonal 555 in the matrix 550 , Per diagonal 555 the totalized value is passed on to the subsequent third stage (step 3). In the third stage, the results of the individual diagonals 555 compared in pairs. In this special embodiment of the method, the maximum value that results for a pair of primers is determined. Of course, the values can also be obtained by addition subtraction or other mathematical arithmetic operations. Table 3 shown below shows all operations that occur within the matrix 550 run in parallel.

Table 3: Supplementary example for the calculation the maximum value when performing the SA calculation in the matrix structure working in parallel. The overlying base pairs will be again carried out using the primer with 4 bases (AGTC).

Another embodiment for use of the method according to the invention and the device according to the invention provides homology searches in databases or identity comparisons in other bioinformatics applications.

Because the rate of structure elucidation via X-ray crystallography or NMR is much lower than the number of new DNA or protein sequences, that become known every day becomes an alternative predictable fairly reliable Approach to structure determination needed. The goal is to create key macromolecules (i.e. proteins) identify which cause pathological events and potential ones Inhibitors for these macromolecules propose. To the molecule to understand and so possible To suggest interactions with its substrate or other substances to be able you have to know the structure of the macromolecule. The biggest obstacle is often the lack of structural data about the relevant molecule. If the examined macromolecules are proteins, one can use homologous proteins of other species whose structure is known is. Modeling unknown protein structures based on their homologues is as homology-based structural modeling known.

Called homologous proteins one generally uses polypeptides that have a similar amino acid composition have in common. In most cases, the proteins are included a relatively high degree of identity also structurally and functionally homologous. amendments the amino acid sequence of a protein a change the 3-D structure cause. It is this relationship between the amino acid sequence of one Protein and its three-dimensional structure that allows you to Proteins, for which have no NMR or X-ray crystal structures gives to compare their structure homologues, their structure one knows.

The sequence homologues with a known structure make it possible to calculate the structure of the homologous sequences, the structure of which is unknown, by means of comparative modeling and thus allow an insight into the protein function. In homology-based protein modeling, the experimentally determined structures are generally referred to as matrices and the sequence homologue (that is, a new chain of nucleotides that has been identified, for example, in an ongoing genome project) is called the target sequence. The homology-based approach to building models involves four consecutive steps. The first is to identify known structures that have a sequence related to the target sequence. This is typically achieved using software tools such as BLAST, which you can search for serve matrices. In the second step, the potential matrices are compared to the target sequence in order to identify the most closely related template. In the third step, a model of the target sequence is calculated, starting from the most suitable template of the second step. The fourth step is finally to evaluate the model of the target sequence using a number of criteria such as energetics.

The method according to the invention and the device according to the invention can now support the calculation of the first and second step. in the Compared to conventional sequential computing methods can the computing time by the invention in parallel processing matrix approach by a factor of, for example, 1000 shortened become.

The ideal case is the amino acid sequence of the unknown protein quite similar to that of its structural homologue and there is, for example, in the PDP protein database (Sussman, J.L. et al. Protein Data Bank (PDB): database of three-dimensional structural information of biological macromolecules. In: Acta. Crystallogr. D. Biol. Crystallogr. 54 (1998) pages 1078-1084) more than one known Homologues from other species. The goal is now these well-known homologues to find.

The program BLAST of the NCBI (old school, S. F. et al. Basic local alignment search tool. In: J. Mol Biol. 215 (1990) pp. 403-410) allows to find these well-known homologues. So that the invention in parallel processing matrix approach within the BLAST program an essential However, adjustments can be made to speed up the calculation process of the calculation method necessary. In the example of homology search can the matrix according to the invention can be constructed from the combinations of two parameter sequences. there the two parameter sequences are generally to be compared with theirs Unequal length parameters. A parameter sequence can be the primary sequence (amino acid sequence) the target sequence and the other parameter sequence is a protein sequence be in a given database. The matrix can be remarkable Take sizes so that it may be more appropriate depending on the number of parallel matrices, or the number of the parallel processing matrix elements, the matrix into several Subdivide sub-matrices. With such a method, for example, any single sub-matrix for processed in parallel. By forming meaningful overlays of the two parameter sequences and appropriate evaluation of the formed Parameter combinations as well as suitable subsequent evaluation regulations can the closest sequence homologues are selected.

Other applications of the invention in parallel processing matrix concern the second step of homology search namely the comparative alignment of the potential matrices with the Target sequence. Other applications are sequence comparisons, evaluation of sequences or, for example, when determining / calculating of DNAs. The matrix according to the invention also accelerates also searching databases, for example substance databases.

Often takes place within such Searches of databases comparative formations take place in the case of substance databases, for example of sought substance properties and substances in the database with their specific properties. The matrix according to the invention For example, a sequence of parameters, whose parameters are the desired ones Contains properties with parameter sequences, the parameters of which the substances with their substance properties contains from the database to compare. This comparison is made by the matrix according to the invention carried out in parallel and leads thus to a significantly accelerated database research in substance databases.

Claims (48)

Method for comparing n parameter sequences, where each parameter sequence contains parameters and a part of the parameters of all n parameter sequences are combined with one another to form parameter combinations according to a previously defined regulation and a first value is assigned to each parameter combination according to a previously defined first evaluation regulation, and the result of the Evaluation rule corresponds to a property accessible to a measurement, characterized in that the combinations of the parameters of the n parameter sequences form an m-dimensional matrix and a part of this m-dimensional matrix corresponds to a matrix which comprises arithmetic logic computing units. The method of claim 1, wherein the arithmetic logic Computing units the evaluation of the parameter combinations formed carry out. The method of claim 1 or 2, wherein the formation of all or of part of the parameter combinations is carried out simultaneously. Method according to one of the preceding claims, wherein the evaluation of all or part of the parameter combinations performed simultaneously becomes. Method according to one of claims 1 to 4, wherein the first Values for all parameter combinations from the n parameter sequences after one further assessment rule can be processed Method according to one of the preceding claims, wherein each individual and / or several combinations of the parameters in one or several logical computing units are formed and / or evaluated becomes. Method according to one of the preceding claims, characterized characterized in that n is an integer that is greater than or is 2 and that m is an integer equal to n or is different from n. Method according to one of the preceding claims, wherein any sequence of parameters from a sequence of discrete parameters consists. The method of claim 8, wherein the sequences are the same and / or include a different number of parameters. The method of claim 9, wherein the sequences pre-determine a particular one have a defined arrangement of the parameters within the sequences. The method of any of claims 8-10, wherein the parameters are one accessible to a measurement Feature. Method according to one of the preceding claims, wherein the values from the 1st assignment of values to further valuation rules can be subjected. The method of claim 12, wherein the result is a measurement accessible Has property. Method according to one of the preceding claims for Creation, formation, design of / or for the selection of substances. The method of claim 14, wherein the substances are biological molecules. The method of claim 15, wherein the molecules are oligonucleotides. The method of claim 16, wherein the parameters in the parameter sequences of the steps of the method according to any one of claims 1 to 15, the bases of Include oligonucleotides. The method of claim 17, wherein the parameter combinations are formed by two parameter sequences, the n parameter sequences to each other go through part of all possible arrangements, and wherein the arrays are shifted one discrete at a time Parameters come about. The method of claim 18, wherein the parameter combinations from the part of all possible Arrangements of the parameter sequences include base pairs. The method of claim 19, wherein the base pairs are hierarchical Value is assigned. 21. The method of claim 20, wherein a portion of the parameter combinations is formed simultaneously and this part and / or part of this Combinations formed at the same time can be hierarchized Value is assigned. 22. The method of claim 21, wherein the associated value corresponds to the bond strength. The method of claim 22, wherein the ones corresponding to the bond strengths Values are subjected to further calculation methods so that the Result one or more selection criteria for one or more oligonucleotides represents Use of the steps of the method according to one of the preceding Expectations for the design, formation, design of / or for the selection of substances. Use according to claim 24, wherein the substances are biological molecules. Use according to claim 25, wherein the molecules are oligonucleotide sequences are. Use according to claim 26, wherein the parameters in the parameter sequences the steps of the method according to any one of claims 1-23, the bases C, G, T, A, U of the oligonucleotide sequences. Use according to claim 27, wherein the parameter combinations are formed by two parameter sequences, the n parameter sequences to each other go through part of all possible arrangements, the arrangements being shifted by a discrete one at a time Parameters come about. Use according to claim 28, wherein the parameter combinations from all or part of all arrangements of the parameter sequences Include base pairs. Use according to claim 29, wherein the base pairs are hierarchical Numerical value is assigned. Use according to any one of claims 27-30, wherein part of the parameter combinations is formed simultaneously and this part or part of this combinations formed simultaneously all at the same time Value is assigned. Use according to claim 30 and / or 31, wherein the associated Binding strength value equivalent. Use according to claim 32, wherein the ones corresponding to the bond strengths Values are subjected to further calculation methods so that the result one or more selection criteria for one or more oligonucleotides represents Use according to claim 33, wherein one or more selection criteria one or more molecular designs correspond. Implementation device of the method according to one of the preceding claims, comprising a Processor and a hardware accelerator for parallel data processing and a memory associated with the processor and / or the hardware accelerator is coupled to execute the steps of the method according to one of claims 1 to 23. 36. The apparatus of claim 35, wherein the memory is a portion of the program instructions for executing the Method according to one of the claims 1 to 23 and / or for has the operation of the device. Apparatus according to claim 35 and / or 36, wherein the hardware accelerator is coupled to the processor. 38. The apparatus of claim 37, wherein the hardware accelerator contains a logic module for parallel data processing. 39. The apparatus of claim 38, wherein the logic device is a programmable Logic module is. 39. The apparatus of claim 39, wherein the programmable logic device is a field programmable gate array (FPGA). 39. The apparatus of claim 38, wherein the logic device is an ASIC is. Device according to one of the preceding claims, the a computer readable storage device or a computer readable storage medium contains. 43. The apparatus of claim 42, wherein the storage unit or the storage medium recorded data of the parameter sequences of the Method according to one of the claims 1 to 23 includes. Method for carrying out a sequence of program instructions with a device according to one of the Claims 35-43. 45. The method of claim 44, wherein providing, transmitting and receiving data about a network can take place. Method according to one of claims 1 to 23 and / or 44 to 45 on a computer readable storage medium or in a computer readable storage unit is stored. Software program product with programming instructions for executing the Steps of the method according to one of claims 1 to 23 and / or 44 to 45th The software program product of claim 47, which is on a computer readable Storage medium or stored in a computer-readable storage unit is.