JP2016502162A - Primary analysis driven by a database of raw sequencing data - Google Patents

Abstract

The present invention relates to a method for identifying a source of a biosequence-containing sample from a raw sequencing lead. Using this method, sources of unknown DNA can be identified and used for diagnostics, bioterrorism defense, food safety and quality, and hygiene applications. In another aspect, the invention relates to a database of reference sequences that can be used in the methods of the invention. The method relies on a system for scoring an incoming query set of biological sequences, such as a collection of pre-indexed reference sequences, reads from sequencing equipment, and a system for submitting portions of the query set.

Description

  The present invention relates to a method for identifying a likely source of a biological sequence. In a further aspect, the present invention relates to a database adapted to be used for this purpose.

  DNA sequencing is an experimental process that identifies the sequence of a base (A, T, C or G). Currently, there are no techniques that can sequence the entire molecule of DNA beyond thousands of bases, and most techniques sequence between 100 and 200 bases. The bacterial genome can contain millions of bases. Over the past few years, sequencing costs have been greatly reduced, which makes it increasingly common to sample large-scale DNA from samples for purposes such as human health, food quality control or microbial community studies It was a typical one. In order to individualize treatment as much as possible, it is envisaged that sequencing of the entire human genome is used more frequently in therapy and routine sequencing is used to manage the presence or absence of specific organisms. it can. Rapid identification of probable source DNA as a goal in itself or as a quality control step in sequencing data before starting to work on more complex data analysis or more expensive analysis It is becoming necessary for

  Primary analysis aligns the sequence with the reference genome (requires that the sequence of the reference species is known) or attempts to reconstruct the jigsaw without a model (de-novo assembly of so-called sequencing tags) -Identification of the contents of the unknown sample (indentifying would require additional steps) and consists of elucidating relatively short sequences (called short reads) resulting from sequencing. Alignment to reference is considered a computationally easier task than de novo assembly.

  Prior to the availability of non-specific or whole-genome sequencing, specific regions were first carefully sequenced and assembled to identify the putative regions of interest. The simplest method is an interval defined by an initiation codon (ATG / AUG) for translating RNA into protein and one of the termination codons (TAG / UAG, TAA / UAA, TGA / UGA) to terminate translation Search for an open reading frame (ORF). The ORF was then aligned against any known gene list. Methods for alignment include alignment algorithms and programs such as the Smith-Waterman algorithm, BLAST algorithm and program, SSAHA and BLAT. These goals are to find the best alignment in the indexed sequence database and find the best match and therefore the most likely function in the query sequence by ranking the scores against any alignment. Increasing the number of similar matches with different biological functions expands the principle by building a “group of best matching genes” or orthologous gene clusters (COG) for the purpose of functional annotation Bring. As complete genomes have become increasingly accessible, Mummer algorithms were designed to align complete genome pairs and visualize how the overall genome structure is compared between genetically related species.

  Due to the number of sequences currently available in the database, the alignment of new sequences to a vast pool of known sequences can take a relatively long time, and BLAST found previous algorithms while finding near optimal results. It was a breakthrough in the sense that it was accelerated. However, in an era where web-based search engines can return search results almost immediately, searching for any known sequence is still relatively time consuming.

  Ning et al., 2001 (Genome: 11: 1752-1729) is an algorithm for performing fast alignment in databases containing DNA of several gigabases, SSAHA (sequence search and alignment with a hashing algorithm). and alignment by hashing algorithm)). SSAHA is an aligner; therefore, for each complete query sequence, it has the task of reporting where it matches each entry in the collection of reference sequences and how much it matches. The SSAHA method is for finding as many matches as possible over the entire length of the query sequence. Sequences in the database are obtained by cutting them into consecutive k-tuples of k adjacent bases and then using a hash table to store the location of each occurrence of each k-tuple. Preprocessed. The query sequence search in the database is performed by obtaining “hits” for every k sets in the query sequence from the hash table, and then performing a selection on the results. The SSAHA algorithm is used for high-throughput single nucleotide polymorphism detection and very large sequence assembly. In SSAHA, the presence and location of each k set is stored in the same lookup structure, which is loaded into the memory of the computer system.

  Known mapping or alignment algorithms and programs include methods such as Erland, Corona, BFAST, Bowtie, BWA, NovoAlign. These goals are to find the position of the lead in the known reference. Consequently, reads that fail to find a match can be flagged as not originating from this sequence. These programs and algorithms evaluate all sequences in the query set, i.e. all sequencing reads, and all of them have an optimal alignment, often referred to as alignment when working with short reads. It also has a long search time weakness, both by trying to find it. Interestingly, all of the above programs use heuristics that trade strictness for speed, so the results you find will be different.

  US2006286565 discloses a method of using k-mer to detect mutations. The method includes detecting an apparent mutation in the target nucleic acid sequence by comparing a portion of the target nucleic acid sequence with a second sequence segment and detecting a match to the portion of the target nucleic acid sequence.

  US201204031 discloses a system and method that can characterize a population of organisms in a sample based on matching short strings of sequence information to identify a genome derived from a reference genome database. This patent application does not disclose a method in which the presence of a short string is searched in one collection of short strings in the reference sequence and the position is searched in another collection of positions in the reference sequence.

US Patent Application Publication No. 2006/286656 US Patent Application Publication No. 2012/000411

Ning et al. 2001, Genome: 11: 1752-1729.

  The present invention provides a novel method for identifying sources of raw sequences such as DNA reads (or short reads) obtained from sequencing instruments or protein sequences obtained from N- or C-terminal sequencing or mass spectrometry To do. The method relies on a system for scoring an incoming query set of biological sequences, such as a collection of pre-indexed reference sequences, reads from sequencing equipment, and a system for submitting portions of the query set. This can be done by using a client-server based approach, where the server entity maintains a collection of references and performs scoring, while the client submits a subset of the query sequence.

  The approach provided by the present invention allows for the rapid determination of different sources of DNA found in a sample and does not rely on knowledge of the complete sequence of a given gene in the source sequence or reference sequence.

  A short lead retains the characteristic signal of the reference, even though it does not represent the complete reference from which it is derived. Short reads can be further broken down into subsequences (called k-mers or k-tuples), such k-mers are indexed to identify the source of raw sequencing data. Search in a collection of k-mers.

In a first aspect, the present invention is a method for identifying a likely source of a biological sequence comprising:
a) sampling a sequence or a subset of short reads from a source;
b) fragmenting sequences from the subset into k-mers;
c) querying a k-mer from said subset against a database containing the k-mer of the reference sequence;
d) determining which references contain k-mers;
e) returning a description of a likely source reference.

  The method focuses on the alignment of the complete query set, and thus traditional alignment and mapping that requires transfer of the entire sequence from an input device (such as a client) to a database and scoring unit (such as a server) that can perform the alignment. Has several advantages over algorithms. In the present invention, only a subset of the sequences are subjected to fragmentation and interrogation, thereby minimizing the need for data transmission. The transmitted subset can be, for example, a fixed size random subset, a filtered subset, adaptive sampling, an iterative synchronous or asynchronous dialog between input and scoring entities, or any combination thereof. However, it is not limited to these.

  Compared to methods based on sequencing read assembly or genome construction followed by search, or mapping every read across a collection of references, the method does not attempt to perform a complete alignment, but rather by working on a subset of the data. , Requiring considerably less computer processing power, so that results can be obtained within seconds. Thus, the method of the present invention can be run using a client-server approach using, for example, a tablet or portable device (eg, a mobile phone, etc.) having low computer processing power as a client. Since results can be obtained relatively quickly for a subset of data, the time required to retrieve the additional subset of data is significantly reduced. Thus, the identity of different sources of DNA in a sample can be determined in a significantly reduced period compared to conventional methods based on whole sequence alignment.

  In its broadest aspect, the present invention relates to queries only for presence in a database. However, in a preferred embodiment, the database is also queried for the position of the k-mer in the reference sequence, thus allowing calculation of the continuity of the source k-mer, making the assessment more accurate. Organisms are often genetically related to each other and the present invention can also find close parents in a collection of reference sequences.

Compiling data in two separate databases or collections decouples the search for the presence of a k-mer in a reference from a location search and can search as much as possible into memory, which can be faster than a persistent store. It makes it possible to consider optimization such as caching of existing searches. If it is found that a k-mer exists, and if there is sufficient time, a search for a location at a given reference can be performed in a supplemental optimization step. Thus, a preferred embodiment of the present invention is a method for identifying a likely source of a biological sequence comprising:
a) sampling a subset of the sequence from the source;
b) fragmenting sequences from the subset into k-mers;
c) querying a k-mer from said subset against a first collection containing a k-mer of a reference sequence;
d) querying a k-mer from said subset against a second collection containing the position of the k-mer in the reference sequence;
e) determining which references contain k-mers;
f) returning a description of a likely source reference, wherein the collection containing the k-mer of the reference sequence is separate from the collection containing the position of the k-mer in the reference sequence.

Thus, a preferred embodiment of the present invention is a method for identifying a likely source of a biological sequence comprising:
a) sampling a sequence or a subset of short reads from a source;
b) fragmenting sequences from the subset into k-mers;
c) querying a k-mer from said subset against a first collection containing a k-mer of a reference sequence;
d) querying a k-mer from said subset against a second collection containing the position of the k-mer in the reference sequence;
e) determining which references contain k-mers;
f) returning a description of a likely source reference, wherein the collection containing the k-mer of the reference sequence is separate from the collection containing the position of the k-mer in the reference sequence.

  One notable feature of the present invention is that once a likely reference is identified, information about the likely reference is returned to the user. The returned information can be, for example, information about the likely species and its origin or source, and / or the complete genome sequence of the likely species. This allows the user to use a state-of-the-art alignment or genome construction algorithm to identify minor variations such as mutations and insertions, and to use the remaining raw reads from unknown samples relative to the reference sequence. Can be aligned.

In a further aspect, the present invention is a database comprising a k-mer of reference sequences comprising:
a) a first collection of k-mers from a reference sequence;
b) relates to a database comprising a second collection of each k-mer position in the reference sequence.

  Compiling data in two separate databases or collections decouples the search for the presence of a k-mer in a reference from a location search and can search as much as possible into memory, which can be faster than a persistent store. It makes it possible to consider optimization such as caching of existing searches. If it is found that a k-mer exists, and if there is sufficient time, a search for a location at a given reference can be performed in a supplemental optimization step.

  In a third aspect, the present invention is a data processing system for identifying a likely source of a source array, preferably including an input device, a central processing unit, a memory, and an output device. The data processing system stores data representing an instruction sequence for executing the method of the present invention when the data processing system is executed, and the memory further includes a database according to the present invention.

  FIG. 3 illustrates the main points of one embodiment of the system of the present invention. The point is that sampling is done at the “client” so that a minimum amount of information is communicated. The most likely use of reference descriptors is not illustrated in this figure.

  Devices (input, output, memory, CPU) can be portable, fixed, cloud and / or online based.

  Preferably, the database is stored on a server, the input and output devices are one or more clients, the client and server are connected via a data communication connection, and server sharing is a collection of references Centralization and the distribution of computing power on servers across clients when running in separate processes or even separate devices. In such embodiments, the client can include a sequence of instructions that allows the client to sample a subset of the source array, fragment them into k-mers, and communicate them to the server.

  The client interacts with the server to adapt or interfere with the sampling procedure, or perform assembly of the source array into one or more larger arrays based on the array communicated from the server to the client It may further include an instruction sequence that allows

  In one implementation, the system is connected to the sequencing device via a data connection.

  In a further aspect, the present invention relates to a computer software product containing an instruction sequence that when executed causes the method of the invention to be performed, and an integrated circuit product containing an instruction sequence that when executed causes the method of the invention to be performed.

FIG. 1 is a diagram showing the construction of a “present” and “location” database. FIG. 2 shows the scoring of a set of query DNA fragments, which are typically raw reads from sequencing. FIG. 2 shows the scoring of a set of query DNA fragments, which are typically raw reads from sequencing. FIG. 3 is a diagram showing an overview of the architecture of the system of the present invention. FIG. 4 shows the average rank (x-axis) and standard deviation (y-axis) of 747 bacterial genomes in the database used as a query, according to varying read size (row) and random replacement rate (column). FIG. FIG. 4 shows the average rank (x-axis) and standard deviation (y-axis) of 747 bacterial genomes in the database used as a query, according to varying read size (row) and random replacement rate (column). FIG. FIG. 5 shows an overview of a specific example of an indexing and scoring procedure that is also used in Examples 1 and 2. (A) In indexing a collection of reference sequences, non-overlapping k-mers are indexed into two separate key value stores, one of which is the reference and k-mer where the k-mer was found. ("Existence"), and the other associates the position in the reference where the k-mer was found with the k-mer ("position"). (B) In processing sequencing reads in the query set, duplicate k-mers looked up in the “presence” store. The use of overlapping k-mers allows for a relatively quick elimination of misalignment between the beginning of the read and the beginning of the reference sequence (dashed line). In this figure, only a subset of k-mers are in phase with the indexing step, so only these can be found “existing”. (C) For a given lead, the threshold is applied only to hold references that may match enough leads. The situation where very large references contain disjoint scattered k-mers, such as bacterial leads to the mammalian genome, uses, for example, the highest concentration of k-mer within the minimum region in the reference. In the last step, the “location” storage is queried. FIG. 6 is a diagram showing bacterial leads. For each bacterial genome in a set of 747 genomes, we have several read lengths (50 nucleotides (nt), 75 nt, 100 nt, 150 nt, 200 nt, 250 nt) and several substitution error rates (0% 1%, 5%, 10%). 100 random reads were used in each query and the distribution of the correct reference rank in the list was recorded; a rank of 1 means that the correct reference was at the top of the list. The returned list of hits was set to a maximum length of 25, and Applicants counted the reference as “missing” if none existed in the list. The percentage of the correct test bacterial genome is represented by a nested bar on the right side of each panel. The figure shows that, as expected, the performance degrades as the error rate increases, but also shows that the 50-length lead appears to have a relatively reduced performance. Increasing the read length beyond 100 nucleotides results in only a slight improvement compared to 100 nucleotide reads and has a limited compensation effect on error rate. FIG. 6 is a diagram showing bacterial leads. For each bacterial genome in a set of 747 genomes, we have several read lengths (50 nucleotides (nt), 75 nt, 100 nt, 150 nt, 200 nt, 250 nt) and several substitution error rates (0% 1%, 5%, 10%). 100 random reads were used in each query and the distribution of the correct reference rank in the list was recorded; a rank of 1 means that the correct reference was at the top of the list. The returned list of hits was set to a maximum length of 25, and Applicants counted the reference as “missing” if none existed in the list. The percentage of the correct test bacterial genome is represented by a nested bar on the right side of each panel. The figure shows that, as expected, the performance degrades as the error rate increases, but also shows that the 50-length lead appears to have a relatively reduced performance. Increasing the read length beyond 100 nucleotides results in only a slight improvement compared to 100 nucleotide reads and has a limited compensation effect on error rate. FIG. 7 is a diagram showing bacterial leads (number of leads). For each bacterial genome in a set of 747 genomes, we have several read lengths (50 nt, 75 nt, 100 nt, 150 nt, 200 nt, 250 nt) and several substitution error rates (0%, 1%, 5%, 10%) was simulated. 100, 200 or 300 random reads were used in each query and the distribution of the correct reference rank in the list was recorded; a rank of 1 means that the correct reference was at the top of the list. The curve displays 100, 200 and 300 leads. It can be seen that increasing the number of leads in random samples from 100 to 300 leads leads to a relatively slight increase in performance. The error rate or lead length had an even stronger effect. FIG. 7 is a diagram showing bacterial leads (number of leads). For each bacterial genome in a set of 747 genomes, we have several read lengths (50 nt, 75 nt, 100 nt, 150 nt, 200 nt, 250 nt) and several substitution error rates (0%, 1%, 5%, 10%) was simulated. 100, 200 or 300 random reads were used in each query and the distribution of the correct reference rank in the list was recorded; a rank of 1 means that the correct reference was at the top of the list. The curve displays 100, 200 and 300 leads. It can be seen that increasing the number of leads in random samples from 100 to 300 leads leads to a relatively slight increase in performance. The error rate or lead length had an even stronger effect. FIG. 8 is a diagram showing the variability of bacterial leads and performance. Average rank (rank, x-axis) of true references and standard deviation of rank (S-rank, y-axis) when one iteration of the 747 test bacterial genome identification procedure was performed 5 times. When the average rank is closest to 1, it is closest to perfect performance, and when the standard deviation of rank is the smallest, the rationality for the sampling effect is the lowest. In order to increase clarity when multiple bacterial genomes examined produce equal or approximate coordinates in the scatter, we use hexagonal binning and respond accordingly. Color the area. The vertical bar on the right side of each scatter plot indicates the number of test genomes that are not within the top 25 matches and is colored on the same scale as the hexagonal binning. Different lead sizes (rows) and error rates (random substitutions, columns) are tried, resulting in a scatter plot matrix. FIG. 8 is a diagram showing the variability of bacterial leads and performance. Average rank (rank, x-axis) of true references and standard deviation of rank (S-rank, y-axis) when one iteration of the 747 test bacterial genome identification procedure was performed 5 times. When the average rank is closest to 1, it is closest to perfect performance, and when the standard deviation of rank is the smallest, the rationality for the sampling effect is the lowest. In order to increase clarity when multiple bacterial genomes examined produce equal or approximate coordinates in the scatter, we use hexagonal binning and respond accordingly. Color the area. The vertical bar on the right side of each scatter plot indicates the number of test genomes that are not within the top 25 matches and is colored on the same scale as the hexagonal binning. Different lead sizes (rows) and error rates (random substitutions, columns) are tried, resulting in a scatter plot matrix. FIG. 9 is a diagram showing bacterial leads, the same species. The percentage of matches is the correct species, i.e. not the exact exact same reference shown in FIG. 7, but the reference in our collection belonging to the same species of bacteria and the percentage of cases where the correct species is not in the top 25 matches. Bring. The performance of the shorter lead (50 nt) is relatively low and the noise further reduces it (bar plot in the first row), which is much better from 100 nt and remains robust to noise. FIG. 9 is a diagram showing bacterial leads, the same species. The percentage of matches is the correct species, i.e. not the exact exact same reference shown in FIG. 7, but the reference in our collection belonging to the same species of bacteria and the percentage of cases where the correct species is not in the top 25 matches. Bring. The performance of the shorter lead (50 nt) is relatively low and the noise further reduces it (bar plot in the first row), which is much better from 100 nt and remains robust to noise.

  The present invention balances the speed and accuracy in performing identification of a likely source of biological sequence information derived from protein, DNA or RNA present in a sample.

  The sequence information to be used in the methods of the invention can be, for example, a raw lead from a nucleic acid sequencing instrument, or from a C or N-terminal sequencing of a protein, or from mass spectrometry protein sequencing. Thus, the word, sample array in the context of the present invention refers to such raw leads, also called short leads.

In one particular embodiment, the invention described in FIG. 2 can:
Create a database with reference DNA (see Figure 1). The database is in two parts: 1) a database of k-mers of any reference DNA indexed with reference, and 2) a database of associations between k-mers from database 1 and positions in the reference sequence . Thus, the reference k-mer ID and location are stored in two different databases.

  FIG. 1 illustrates one embodiment of database construction. Input data for creating the database is DNA derived from a public or proprietary database. These are then divided into K-mers which can preferably be non-overlapping to save space. The k-mer can be further bit-packed to 2 bits, meaning that each base occupies only 2 bits of memory. In order to accelerate the storage of k-mers, they are preferably screened before insertion in the database. Furthermore, the name in the reference sequence from which the k-mer is derived and the position in the sequence can be stored in separate databases.

  • Search for a selection of reads resolved into a k-mer query sequence from the source against a reference database.

  A major score is calculated from the number of k-mers derived from the query sequence that can be found in a given reference sequence in the database.

  • Suggested sequences are returned to the user and can be used for more traditional and analytical analysis (more heavy and traditional analysis).

The features of this implementation of the invention are as follows.
Only the exact match of k-mer is registered in the search.
The query lead is broken down into a number of k-mers of length 16, for example. The starting point for each k-mer is incremented by one.
A de novo alignment or mapping method that is not “traditional”.

  FIG. 2 illustrates one type of possible algorithm for searching the k-mer database. The lead is divided into k-mers using a sliding window with a step size of 1. If a k-mer has already been encountered in the current search, the next k-mer is selected. Next, the k-mer is looked up in the k-mer database. If this is present in the database, information is searched for the identity of the reference sequence and its position in the sequence. Next, the approximate continuity of the lead is calculated and if the largest consecutive segment exceeds the threshold, the hit count is increased. Repeat this for every k-mer in the lead. For each read, the score is calculated as the number of hits divided by the length of the query sequence (hit count), and then the hit count divided by the length of the matching reference sequence is calculated. This is repeated for a large number of leads and can be defined a priori or dynamically depending on the score obtained. Screen the score and return the best match to the user.

  An exact match is not made at the lead level. Scoring allows missed k-mer matches along the lead (thus ensuring robustness against sequencing errors and mutations in biological samples).

The whole system is shown below.
• Index any known reference DNA sequence to the k-mer, preserving the reference (eg, species) and position in the reference sequence. This step is preferably performed only when the reference DNA sequence has been updated by the addition of new sequences or additional sequence information.
Clients that can store short sequences of DNA by dividing the sequence into k-mers, matching against the database, counting the number of hits in the reference sequence, and preferably refining the matching by location information .

The resulting reference can then be used for the following purposes.
Remove leads that match the reference and find if there is less abundance of DNA from another different reference.
Perform better alignment than de-novo assembly by performing alignment on the reference, or iteratively constructing larger fragments using references in the database and leveraging previously assembled references In addition, performance will increase as the size of the database increases and more assembled references are added.
Identify the likely presence of various organisms or genes (eg, relevant for diagnostic purposes).

  Since only a sub-sample of raw leads is required, this can reduce the amount of data that is transferred to make an initial diagnosis, such as identification of an infectious agent. For smaller array experiments, this also allows part of the analysis to be performed by the client in the product hardware.

  With the development of low-throughput desktop sequencers (or disposable sequencing units) and the emergence of cheaper GPU or FPGA units, the technique enables real-time or near real-time primary analysis of sequencing data. .

Algorithm In one aspect, the present invention is a method for identifying a likely source of a biological sequence comprising:
a) sampling a sequence or a subset of short reads from a source;
b) fragmenting sequences from the subset into k-mers;
c) querying a k-mer from said subset against a database containing the k-mer of the reference sequence;
d) determining which references contain k-mers;
e) returning a description of a likely source reference.

  The term “sequence from a source” is used to indicate a sequence obtained from a sample containing a biological sequence. The sample can be an environmental sample, a sample derived from a subject such as a patient, a sample derived from a crime scene, a food sample, a water sample, or the like. Samples are subjected to state-of-the-art DNA / RNA or protein isolation and sequencing methods. The result is a set of sequences (also called reads) characteristic of the sample. The sequence is typically a random length within a particular interval. The sequences are also typically overlapping randomly. Each of the sequences derived from the sample called the source sequence can be subjected to the method of the present invention.

  The term “reference” in the present invention includes an array descriptor stored in a database. A typical example of a reference is the complete genomic sequence of a particular species or variety or isolate. A reference can also consist of a transcriptome or proteome of a particular species or a particular state of a species. Species transcriptomes and proteomes can change over time in response to age and environmental conditions, for example, species genomic sequences remain constant over time, to varying degrees. The database can store additional information about the reference.

  The method of the present invention can be applied to any biological sequence information such as amino acid sequences and nucleotide sequences such as DNA and RNA sequences. In a preferred embodiment, the sequence is a DNA sequence.

  In its broadest aspect, the present invention relies solely on the identification of the presence of a k-mer derived from a query or source sequence. In this case, the output from the algorithm is a reference and a list of corresponding numbers of hits identified in the reference. However, because of the size of some genomes, such as the human genome and especially some plant genomes, many k-mers can coincide by chance in these very large genomes. Thus, in a preferred embodiment, the query further comprises determining the position of the k-mer in the reference sequence. This allows the presence and position to be used to determine the continuity of the query k-mer in the reference sequence. This makes the query more accurate as a score based on both presence and locality, or the approximate continuity of k-mers in the reference can be used.

Thus, a preferred embodiment of the present invention is a method for identifying a likely source of a biological sequence comprising:
a) sampling a sequence or a subset of short reads from a source;
b) fragmenting sequences from the subset into k-mers;
c) interrogating one or more k-mers from said subset against a first collection comprising k-mers of a reference sequence;
d) interrogating one or more k-mers from the subset against a second collection that includes the position of the k-mer in the reference sequence;
e) determining which references contain k-mers;
f) returning a description of a likely source reference, wherein the collection containing the k-mer of the reference sequence is separate from the collection containing the position of the k-mer in the reference sequence.

  In an even more preferred embodiment of the present invention, the query for the second collection containing the position of the k-mer in the reference sequence finds the given k-mer in the first collection containing the k-mer of the reference sequence. Only if it is (ie, exists) (see FIG. 2).

In the preferred embodiment of the present invention, if steps a) to f) above are used, the presence and location of a given k-mer is determined prior to subsequent k-mer queries. Thus, a preferred embodiment of the present invention is a method for identifying a likely source of a biological sequence comprising:
a) sampling a sequence or a subset of short reads from a source;
b) fragmenting sequences from the subset into k-mers;
c) querying a k-mer from said subset against a first collection containing a k-mer of a reference sequence;
d) querying the k-mer from the subset against a second collection containing the position of the k-mer in a reference sequence;
e) determining which references contain k-mers;
f) returning a description of a likely source reference, wherein the collection containing the k-mer of the reference sequence is separate from the collection containing the position of the k-mer in the reference sequence.

  One notable feature of the present invention is that only a subset of sequences obtained from sequencing is used for database queries. This configuration minimizes data migration that can be the rate-limiting step when very large genomes are sequenced and queried. Thus, a subset of sequences is at least 1%, such as at least 2%, such as at least 4%, such as at least 5%, such as at least 6%, such as at least 7.5%, such as at least 10%, such as , At least 15%, such as at least 25%, such as at least 30%, such as at least 35%, such as at least 40%, such as at least 50%.

  One feature of the present invention is that the k-mer query includes determining an exact match between the query and the reference k-mer.

  When a source sequence or short lead is queried, preferably the query includes any k-mer query derived from at least one source sequence. This configuration allows the best calculation of continuity or approximate continuity. Preferably, at least 50 source arrays, such as at least 100, such as at least 150, such as at least 200, such as at least 250, such as at least 300, such as at least 400, such as at least 500, such as at least 750. Any k-mer from, for example, at least 1000, such as at least 1500, such as at least 2000, such as at least 2500, such as at least 5000 sequences, is queried. The exact number of source sequences queried is determined, inter alia, by the network and computational power, time constraints, statistical requirements and the size of the complete source sequence and the relationship of the source to different references.

  As demonstrated in the examples, each source sequence is preferably of a predetermined minimum length to provide a characteristic fingerprint of the source organism, variant, variety or isolate. In the case of a source sequence that is a nucleotide sequence, the source sequence is preferably at least 50 nucleotide bases, more preferably at least 75 nucleotide bases, such as 75-200 nucleotide bases, such as 75 nucleotide bases to 100 nucleotide bases. Or 100 nucleotide bases to 125 nucleotide bases or 125 nucleotide bases to 150 nucleotide bases or 150 nucleotide bases to 175 nucleotide bases or 175 nucleotide bases to 200 nucleotide bases, even more preferably, for example, at least 100 nucleotide bases, such as 100 to 300. Nucleotide bases, such as 100 nucleotide bases to 150 nucleotide bases or 150 nucleotide bases to 200 nucleotide bases or 2 0 nucleotide bases to 250 nucleotide bases or 250 nucleotide bases to 300 nucleotide bases, such as at least 100 nucleotide bases such as 100 nucleotide bases such as 200 nucleotide bases, such as at least 250 nucleotide bases such as 300 nucleotide bases such as 400 nucleotide bases, at least 500 or more nucleotide bases.

  In many practical implementations, a subset of an array is queried first. If this is not sufficient to determine a reference with a sufficiently high certainty, the method comprises selecting one or more further subsets of the sequence and these comprising steps a) to e) of the method of the invention or a) to f) may be further included.

  In principle, the method allows the use of any size k-mer or k-tuple. However, in a preferred embodiment, the k-mer size can be divided by four. Thus, a k-mer can be of size 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64 or more. More preferably, the k-mer can be of a length between 16 and 64, more preferably between 16 and 32. A longer k-mer makes the method more sensitive to sequencing errors, and a shorter k-mer increases the number of random hits, thereby producing noise.

  In one embodiment, the k-mers are contiguous, preferably the k-mers stored in the database are contiguous to cover the entire reference sequence.

  Preferably, the k-mers from the source sequence are overlapping and are at least 1, such as at least 2, such as at least 3, such as at least 4, such as at least 5, such as at least 6 bases or Gradually increase amino acids. This corresponds to sliding a window of width k across the array. The window can be slid by 1, 2 or more bases / amino acids across the sequence. For example, by creating an overlapping incremental k-mer from the source sequence, the method will determine the sequencing since a k-mer on either side of the single nucleotide mutation / error could be identified in the query. Less sensitive to errors or point mutations. Therefore, continuity can be calculated with higher accuracy.

  It is also possible to use disjoint k-mers due to concatenation of disjoint subsequences in the source array.

  Preferably, in the method, a k-mer derived from a given sequence is queried against a database to determine the presence of a k-mer in one or more reference sequences and the one or more reference sequences. Determine the position of the k-mer. To optimize database usage, the location is preferably queried only if k-mers are present in the database.

  To allow quantitative evaluation of the query, the method includes calculating a score for the identified reference sequence, the score being derived from one or more sequences found in the given reference sequence. Correlates to the number of k-mers. This score can be divided, for example, by the length of the source sequence. A further score for the identified reference can be calculated, which correlates to the continuity of the k-mer from one or more sequences found in the reference sequence. For example, the score can be the percentage of the longest sequence of k-mers from one source sequence found in the database and the k-mer found in one reference sequence in the database.

  Similarly, for each identified reference sequence, a score for the identified reference can be calculated, which is the number of k-mers in the reference sequence that are also present in the subset of k-mers from the source. Correlate with An example can be the percentage of k-mers from one reference in the database found in the source sequence. In many practical applications, hundreds of source sequences are queried and scored to obtain satisfactory certainty. This score may also include a score based on the continuity of the identified k-mer.

  These scores are preferably calculated for each separate source sequence, for example, any k-mer from one source sequence is queried and one or more scores for the source sequence are calculated. Is done. Preferably, the method further comprises any k-mer query derived from a second source sequence, preferably a third source sequence or the like. The scores of different source sequences can be combined, for example, by weighing them according to the length of the source sequence.

  In one embodiment of the present invention, once every k-mer created for a lead has been processed, the number of close positions matched in the reference is used to span the largest cluster of matches, i.e. every matching reference. Isolate the highest concentration of matching k-mer originating from the same lead. For each such cluster, the count is calculated by adding the number of k-mers in the cluster to the count of a given reference sequence. If the method is repeated over two or more reads from a given sample, update the count by adding the number of k-mers in the cluster to the reference sequence count obtained from the previous read. Can do. That is, the count can be updated by adding the number of reference k-mers, and the list of already counted k-mers is updated. Subsequently, the next array or read can be processed. A list of references associated with the k-mer counts found to match is obtained. For each pair <reference, count>, divide the count by the number of unique k-mers in the query set to get a rough score of the amount of DNA in the queried subset matched by a given reference. If the queried subset exactly matches the sequence, the score will be 1, otherwise it will be smaller; for example, if the queried subset is a mixture of equal proportions of the two references , Both reference scores will be around 0.5. The count can also be divided by the size of the reference (or the number of unique k-mers in the reference sequence) to obtain a rough score for the fraction of the reference represented by the queried subset; the second score Helps to select matching references and avoid bias to the largest reference. The final score is, for example, a weighted sum of these two scores, using an equal weight for each score.

  In one embodiment of the present invention, a preselected number of source arrays are queried and the results are returned. However, in other embodiments, the database query can be stopped once the reference organism has been identified with a defined statistical probability. Similarly, if a defined fraction of k-mer is not found in the database, or is extended by additional source sequences, or the score is calculated by the relaxation parameter, the database query can be aborted. This can occur in the case of junk sequences, sequences with many sequencing errors, or completely unknown sequences.

  The output from the query process can be a list of likely source references ranked according to one or more of the score or scores. Other examples of database output include one or more of the following information about one or more likely references: the taxonomic name of the likely reference, of the likely reference Relatedness, source of the reference, genetic linkage information, information about SNPs, gene location and annotation in the sequence.

  In certain embodiments, the database outputs the most likely reference sequence, and preferably the database outputs the complete genome sequence of the most likely reference species. This allows the user to align the source sequence with the most likely species complete genome sequence using a state-of-the-art alignment algorithm and present mutations or insertions or chromosomal abnormalities, abnormalities or anomalies You can investigate further. However, in one embodiment of the present invention, the method of the present invention is, for example, a Smith-Waterman algorithm [14], BLAST [1], BLAT [5], Bowtie, BWA, SHRiMP [16] or known to those skilled in the art. It does not include the use of alignment algorithms for sequence data, such as other alignment algorithms, for example, alignment algorithms that use a scoring matrix.

  In many cases, such as when microbial sequences are queried, a database can contain many closely related sequences, eg, sequences from different isolates of the same species. In such cases, the results from references with very similar sequences can be grouped in the output. This can also allow the user to more easily identify small pieces of inserted DNA from another species or a different species present in smaller amounts.

  In many cases, the sample contains a mixed population of species, and whole genome sequencing will result in a mixture of genomic DNA from multiple species. In such cases, the method may include performing several iterations of the method, such as identifying the most abundant reference in the first iteration. In the second iteration, sequences from the most abundant species can be removed from the source sequence prior to querying the database, or the method can include ignoring further results from the species.

  Alternatively, the output from a single iteration of the method of the invention can include information and scores for all identified references. The score in this case can include a percentage distribution between different references.

  This embodiment can also be used to identify insertion references, such as viral insertions, transgenes or insertions from another bacterial species.

  In many embodiments, the user first knows that a sequence or short read from one reference is present in the sample, and the subsequent task is any other sequence present in the sample or This will identify references that are likely to be short leads. This can be the case for diagnostics where the sample contains both human DNA and DNA from potential pathogens. Other examples include the identification of harmful bacteria in food samples known to contain DNA from food sources (eg, salads, tomatoes, cucumbers, meat from certain species), The task is to identify the presence and identity of any contaminating DNA. In such a method, the method can include first removing a source sequence that aligns with a sequence derived from a defined reference. Alternatively, the method may include ignoring k-mers from one or more predefined references.

  In one embodiment, the method includes sampling and querying raw leads obtained from a nucleic acid sequencer.

  If we have a query set of DNA data to identify, such as short or raw leads from a sequencer for diagnostic purposes, Applicants will be responsible for the total mapping or alignment of any lead to a comprehensive reference database. Consider the brute-force approach to have two major disadvantages: first, hundreds of megabytes or as many as several gigabytes of data being transferred from the sequencing facility to the computing center; In addition, the computational resources required to execute the task are significant. The reference collection has 10,000 E.C. E. coli-sized bacteria, and optimized aligners such as BWA and bowtie2 have a raw sequencing data of 250 M bases (if the genome is 4 M bases in size, the average coverage is about 60 × Assuming that it takes 30 seconds to process), this would take three and a half days on the CPU, but it can be trivially parallelized on multiple CPUs. Such genome ligation can be refined, but with an ever-increasing amount of memory, post-processing calculations to assign mapping positions to the first reference genome, and short read aligners often do not settle The cost of multiple matches that are inevitable when the genome is referenced. The time complexity of positioning n occurrences of a string of length p in a reference of size u using an FM-index has an upper bound O (p + n log ε u), which is calculated by a term in log ε The amount means increasing gradually as the size of the reference increases, but increasing linearly with the number of highly similar genomes. Applicants' approach encompasses an enormous reference database perspective and does not attempt to maintain it in the entire RAM of a single computer.

Database In one aspect, the present invention is a database comprising a k-mer of reference sequences comprising:
a. A first collection of k-mers from a reference sequence;
b. And a second collection of each k-mer position in the reference sequence.

  The database architecture, as illustrated in the accompanying examples, allows a very quick query of k-mers from the source sequence, demonstrating that results can be returned in seconds.

  The database may further include information about a full-length sequence associated with a given reference, and / or a source of the reference and / or one or more taxonomic descriptors of the reference. Additional information that can be stored is information about genes that are annotated in the DNA sequence.

  When building a database, a k-mer can be attached to a hash function that assigns a unique key to each unique k-mer. Other possibilities include search trees or hash functions and search tree combinations. A unique key may relate to information about these references where the k-mer exists.

  In the second collection, each unique k-mer in the second collection can also be used as a key, and if present by a hash table, search tree, or combination thereof, the k-mer in each reference. Can also be associated with information about the location of This collection can contain further information about the location where the k-mer is located, such as the coding sequence, regulatory sequences, etc., the association of the sequence to any annotation.

  Sequence, coding sequence, association to any of the regulatory sequences, the taxonomic name of the likely reference, the closeness of the likely reference, the source of the reference, a group of further related references, Information about where the reference was obtained (soil, sea, intestine, sewer, etc.), when the reference sequence was obtained, taxonomic classification, related species, and database where the reference sequence was downloaded (eg NCBI, EBI / Sanger) or other information, such as one or more additional information about the reference sequence in which a given k-mer exists, is additionally used for information retrieval of information about the reference sequence according to the present invention, such as an SQL database. It can also be stored in a separate database.

  By terminology “an additional group of related sequences” means sequences derived from samples taken in similar environments, such as soil, sea, intestines, sewers, and the like.

Thus, in one embodiment of the present invention, the database containing the k-mer of the reference sequence is
a) a first collection of k-mers from a reference sequence;
b) A second collection of each k-mer position in the reference sequence.
c) Reference identifier and description line, source of data, taxonomic name of the likely reference, proximity of the likely reference, source of the reference, further related reference Information about the group, where the reference was obtained (soil, sea, intestine, sewer, etc.), when the reference sequence was obtained, taxonomic classification, related species, information about the database where the reference sequence was downloaded (eg , NCBI, EBI / Sanger or other databases) and a third collection or database having one or more information selected from the group consisting of:

  In the preferred embodiment, as shown in FIG. 1, the first collection of k-mers is a key value store that associates each k-mer (key in the database) with a list of identifiers corresponding to references having that k-mer. Or it is a NoSQL database (for example, KyotoCabinet). A second collection of k-mer positions in the reference sequence can also be stored in a key value store or a NoSQL database, eg, KyotoCabinet (see FIG. 1). Information portions such as associations between references, identifiers and description lines and sources of data are stored in separate SQL databases.

  The length of the k-mer in the database assumes an appropriate lookup, but preferably matches the length of the k-mer in the source sequence. However, the k-mers in the database are preferably non-overlapping. The use of duplicate k-mers will increase data processing time.

  In the present invention, the indexed k-mer of the reference sequence in the database can be duplicated or non-duplicated. In a preferred embodiment, the k-mer of the indexed reference sequence is non-overlapping. One skilled in the art will recognize that similar scoring principles can be used for indexed databases of non-overlapping or overlapping k-mers in the reference sequence.

  The time complexity of positioning n occurrences of a string of length p in a reference of size u indexed by k-mer is O (p + n log) if a tree or hash is used for k indexing and lookup. u) or O (p + n).

  This does not exclude embodiments where the k-mers overlap and are progressively advanced by at least 1, such as at least 2, such as at least 3, such as at least 4, such as at least 5, such as at least 6 bases or amino acids.

  In a preferred embodiment, the complete genomic sequence of a given reference is fragmented into k-mers and uploaded to a database. It is also conceivable to build a database based solely on a given reference transcriptome or given reference proteome.

  If the goal is simply to identify a likely reference for a source sequence, the database need not be complete. It may be sufficient to provide a random selection of genomic DNA from a particular reference. The selection can also be non-random, for example, excluding repetitive DNA and so-called junk DNA stretches.

  One type of database containing all available information can be constructed for each type of biological sequence, protein, RNA, DNA. In other embodiments, specialized databases can be constructed for specialized purposes, such as when the purpose is simply to identify the presence or absence of a given reference sequence derived from a source sequence. For example, the database can include sequence information from humans, animals, mammals, birds, fish, fungi, insects, plants, bacteria, archaea, viruses and / or plasmids. If no matching reference is found with a sufficiently high score, the database network can also be built with requests for one or several other leads sent by one server.

  In order to make optimal use of hardware resources without compromising speed, the database can be divided into sub-databases that are stored on several different servers.

  In other embodiments, the database is one or more taxonomic descriptors selected from gates, classes, eyes, families, genera and species, or one such as source, distribution, origin and normal search frequency. Organized into sub-databases according to species or multiple environmental descriptors.

  The database can be constructed as described in FIG. 1 and stored using a database engine known as key value storage (eg, BSDDB, KyotoCabinet, LevelDB, MongoDB, etc.). Thus, in one embodiment of the present invention, the database is stored using key value storage selected from the group consisting of BSDDB, KyotoCabinet, LevelDB, and MongoDB.

Algorithm Applications The methods and systems of the present invention can be used in many applications where it is necessary to identify a likely source of DNA found in a sample.

Diagnosis In medical treatment, it is necessary to quickly identify sources that are likely to be infected. This can be done using the method according to the invention. This allows the selection of a suitable treatment that will treat the infection with minimal side effects in the most effective manner.

  Yet another diagnostic application relates to the identification of viral insertions in cancer cells. In this application, it may be advantageous to filter the complete human sequence from the sequence obtained in the raw reads, or simply ignore any human hits identified in the database. This will allow the identification of relatively small viral insertions in the human genome.

Bioterrorism defense In bioterrorism defense applications, there is a need for fast and reliable identification of species of infectious or virulence factors encountered. The present invention provides the possibility of rapid identification of a source without prior knowledge of the source. The method of the present invention allows species identification without prior knowledge of the species of the pathogen.

  Further applications in bioterrorism defense include, for example, the identification of transgenic pathogens into which a toxic transgene has been inserted. The database advantageously also contains sequence information derived from state-of-the-art plasmids. This allows easy identification of adjacent regions of insertion. If the transgene is derived from an organism found in the database, it is also possible to identify the source of the transgene. In such a case, the database can return the name of the pathogen, the name of the organism from which the transgene is derived, the gene encoded by the transgene and the plasmid used to insert the transgene.

Food safety and quality Current methods for identifying potentially harmful infections in food are time consuming (based on the isolation and growth of infectious organisms) or require prior knowledge of the source of the infection (PCR-based method). This method does not require any of them, and the raw lead into a system where authorized persons and manufacturers can simply isolate genomic DNA, sequence the DNA, and operate the method of the present invention. Allows you to upload.

  When looking for bacteria, fungi or viruses in a sample of food, it can be advantageous to query the fraction of the database that contains only sequences derived from bacteria, fungi or viruses. In this way, any genomic sequence derived from food (vegetables, fruits, meat) will be identified as not present in the database, thereby improving the performance of the method.

  Another application is quality control. One possible application is the identification of meat species such as minced meat, patties, cooked meals, and instant foods. There are numerous examples of fraud attempts where expensive meat such as beef or lamb has been replaced or “diluted” by cheaper meat such as pork.

  Other possible quality control applications include the determination of plant varieties such as grapes, apples and potatoes.

  Yet another possibility is water quality management.

Hygiene and prevention methods The present invention provides the possibility of hygiene management by allowing rapid identification of the source of DNA in a sample taken in connection with a cleaning procedure. Further applications include the identification of sources that are likely to be contaminated, thereby allowing the application of hygienic techniques that are best suited for elimination of specific infectious agents.

Items The present invention will now be described as optionally numbered items 1 through 56, which should be considered as embodiments of the present invention. The invention is further defined with reference to the appended claims.

1. A method for identifying a likely source of a biological sequence comprising:
a) sampling a sequence or a subset of short reads from a source;
b) fragmenting sequences from the subset into k-mers;
c) querying a k-mer from said subset against a database containing the k-mer of the reference sequence;
d) determining which references contain k-mers;
e) returning a description of the likely source reference.

2. Item 2. The method according to Item 1, wherein the biological sequence or the short read is an amino acid sequence.

3. Item 2. The method according to Item 1, wherein the biological sequence or the short read is a DNA or RNA sequence.

4). The method of any preceding item, wherein the k-mer query comprises determining an exact match between the query and the reference k-mer.

5. The method according to any of the preceding items, wherein the querying step further comprises the step of determining the position of the k-mer in the reference sequence.

6). A method according to any of the preceding items, wherein presence and position are used to determine the continuity of the query k-mer in the reference sequence.

7). The query is at least one source sequence or short lead, preferably at least 50, such as at least 100, such as at least 150, such as at least 200, such as at least 250, such as at least 300, such as at least 400, For example, including any k-mer query derived from at least 500, such as at least 750, such as at least 1000, such as at least 1500, such as at least 2000, such as at least 2500, such as at least 5000 sequences. A method according to any of the preceding items.

8). The source sequence is at least 50 bases, preferably at least 100 bases, such as at least 150 bases, such as at least 200 bases, such as at least 250 bases, such as at least 300 bases, such as at least 400, at least 500 bases. The method according to any one of the preceding items, wherein the nucleotide sequence is:

9. A subset of sequences is at least 1%, such as at least 2%, such as at least 4%, such as at least 5%, such as at least 6%, such as at least 7.5%, such as at least 10%, such as at least The method according to any of the preceding items, comprising 15%, such as at least 25%, such as at least 30%, such as at least 35%, such as at least 40%, such as at least 50%, discrete sequences.

10. A method according to any of the preceding items, further comprising selecting one or more additional subsets of the sequence and subjecting them to steps a) -e) of item 1.

11. The method according to any of the preceding items, wherein the subset is random or filtered.

12 Any of the preceding items wherein the k-mer is of size 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64 or greater the method of.

13. The method according to any of the preceding items, wherein the k-mers are continuous.

14 Any of the preceding items, wherein the k-mers are overlapping and gradually increase by at least 1, such as at least 2, such as at least 3, such as at least 4, such as at least 5, such as at least 6 bases or amino acids. The method of crab.

15. The method according to any one of the preceding items, wherein k-mer is a disjoint partial sequence.

16. A k-mer from a given sequence is queried against a database to determine the presence of the k-mer in one or more reference sequences and the position of the k-mer in the one or more reference sequences. A method according to any of the preceding items.

17. Item 17. The method of item 16, wherein the location is queried only if k-mer is present.

18. A method according to any of the preceding items, wherein a score of the returned reference is calculated.

19. A method according to any of the preceding items, wherein a score for the identified reference sequence is calculated and the score correlates with the number of k-mers from one or more sequences found in a given reference sequence.

20. A score for the identified reference is calculated and the score correlates to an average or continuous continuity of local concentrations of k-mers from one or more sequences found in the reference sequence The method according to any one.

21. A method according to any of the preceding items, wherein a score for the identified reference is calculated and the score correlates to the number of k-mers in the reference sequence that are also present in the subset of k-mers from the source.

22. 22. A method according to any of items 18-21, wherein the likely source references are ranked according to the score or scores.

23. A method according to any of the preceding items, wherein every k-mer from one source sequence or short read is queried and one or more scores of said source sequence or short lead are calculated. .

24. 24. The method of item 23, further comprising interrogating any k-mer derived from a second source sequence or short lead, preferably a third source sequence or short lead.

25. The method according to any of the preceding items, wherein the database query can be aborted once the reference organism has been identified with a defined statistical probability.

26. A method according to any of the preceding items, wherein the database query can be aborted if a defined fraction of k-mer is not found in the database.

27. The database includes the following information about one or more likely references: taxonomic names of likely references, close relatives of the likely references, sources of the references, further relevant references The method according to any of the preceding items, wherein one or more of the groups are output.

28. A method according to any of the preceding items, wherein the database outputs the most likely reference sequence, preferably the database outputs the complete genomic sequence of the most likely reference species.

29. The method according to any of the preceding items, wherein results from references having very similar sequences or results from further related references are grouped in the output.

30. In any of the preceding items, several iterations of the method are performed, such as identifying the most abundant reference in the first iteration and removing the sequence from the most abundant reference from the source sequence or short read. The method of crab.

31. 31. The method of item 30, further comprising identifying in the second iteration the second most abundant reference, removing sequences from the second most abundant reference, and the like.

32. 32. The method of item 30, further comprising identifying a reference with a high probability of insertion in a second iteration.

33. The method of any preceding item, further comprising first removing a source sequence that aligns with a sequence derived from a defined reference.

34. Including ignoring a k-mer from a source sequence or short lead if a defined number of k-mers from a source sequence or short read is not present in the database. The method according to any one.

35. The method according to any of the preceding items, wherein the query comprises ignoring k-mers from one or more predefined references.

36. A method according to any of the preceding items, wherein the raw sequence is queried when obtained from a nucleic acid sequencer.

37. A database containing k-mers of reference sequences,
a. A first collection of k-mers from a reference sequence;
b. A database including a second collection of each k-mer position in the reference sequence.

38. 38. The database of item 37, further comprising information about a full-length sequence associated with a given reference, and / or a source of the reference, and / or one or more taxonomic descriptors of the reference.

39. 39. The database according to any of items 37 to 38, wherein a k-mer in the database is attached to a hash function that assigns a unique key to each unique k-mer.

40. 40. The database of any of items 37-39, wherein each unique k-mer in the first collection is related by a vector to information about those references in which the k-mer exists.

41. 41. The database of any of items 37-40, wherein each unique k-mer in the second collection, if present, is related by a vector to information about its location in each reference.

42. Any of items 37-41, wherein the k-mer has a length of 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64 or more The database described in Crab.

43. The database according to any of items 37 to 42, wherein k-mers are non-overlapping.

44. Any of Items 37-43, wherein the k-mers overlap and are gradually increased by at least 1, such as at least 2, such as at least 3, such as at least 4, such as at least 5, such as at least 6 bases or amino acids. The database described in.

45. 45. A database according to any of items 37 to 44, comprising a k-mer derived from the complete sequence of each reference.

46. 47. Database according to any of items 37 to 46, comprising sequence information derived from humans, animals, mammals, birds, fish, fungi, insects, plants, bacteria, archaea, viruses and / or plasmids.

47. 47. A database according to any of items 37 to 46, divided into sub-databases stored on several different servers.

48. According to one or more taxonomic descriptors selected from gates, classes, eyes, families, genera and species, or one or more environmental descriptors such as source, distribution, origin and past query frequency 48. A database according to any of items 37-47, organized into a sub-database.

49. A data processing system for identifying a likely source of a source arrangement comprising an input device, a central processing unit, a memory, and an output device, wherein the data processing system is executed 50. A data processing system in which data representing an instruction sequence for performing the method according to items 1 to 36 is stored internally, and the memory further includes a database according to any of items 37 to 49.

50. 50. The system of item 49, wherein the database is stored on a server, the input and output devices are clients, and the client and server are connected via a data communication connection.

51. 51. The system according to any one of items 49 to 50, wherein the client is selected from a portable computing device such as a personal computer, a fixed type PC, a portable PC, and a smartphone.

52. 51. A client according to any of items 49-51, wherein the client comprises a sequence of instructions that allows the client to sample a subset of the source array, fragment them into k-mers and communicate them to the server. system.

53. Item 49 further comprising an instruction sequence that allows the client to perform assembly of the source array into one or more larger arrays based on the sequences communicated from the server to the client. The system according to -52.

54. 54. A system according to any of items 49 to 53, connected to the sequencing device via a data connection.

55. A computer software product containing a sequence of instructions that, when executed, causes the method of items 1-36 to be performed.

56. An integrated circuit product containing a sequence of instructions that, when executed, causes the method of items 1-36 to be performed.

Rapid identification of sequences by k-mer Thus, applicants can quickly point to a likely source of DNA or RNA and work directly on raw reads obtained from DNA sequencers. A new method, Tapir, is presented. Applicants' system resides in a server that references known DNA and a client that has DNA data to be certified. To demonstrate use, Applicants have along with thousands of bacterial genomes, phage genomes, phages and plasmids, as well as human genomes, mouse genomes, A.I. Reference was made to various sequences derived from thaliana and fungi, archaea. Applicants also run a client that can run in a web browser, which can process gigabase data from a portable computing device. The method relies on k-mer indexing and migration of a limited amount of data to the server. It can perform its task within seconds from an Android smartphone, consumes a moderate amount of bandwidth to communicate with the server, and to the best of Applicants' knowledge, differs from any existing tool Brings simplicity to use. This is used in Applicants' core facility for routine immediate quality inspection in sequencing runs and is available at http://tapir.cbs.dtu.dk.

Preface DNA sequencing has become increasingly affordable over the past decade to the point that it is an all-or-nothing comment in itself [13]. Today's high-end sequencers have the capacity to process several human genomes or hundreds of bacterial equivalents, and the next generation of sequencers is already available, which is the initial required Less investment and flexibility over the sequencing volume. Sequencing a complete bacterial isolate is a day-to-day task, but will soon be a few hours of work. Recent announcements on nanopore sequencing [12] show that USB powered devices with an unprecedented low level of capital investment that can sequence DNA directly, making the sequencing device disposable. Presented. Oxford Nanopore, a company behind this future product, announced its release in 2012 [8]. DNA extraction is a relatively simple procedure and it can be foreseen that DNA sequencing will soon be a routine and inexpensive procedure in molecular biology. Patients are routinely sequenced, infectious pathogen pandemics will be followed by their DNA, and water and food quality will also be monitored by DNA sequencing.

  In analytical aspects, local alignment of sequences with pioneering tools such as the Smith-Waterman algorithm [14] was the cornerstone of bioinformatics. When applied during a collection of queries and references, this allows alignment ranking and allows researchers to derive the origin of newly sequenced DNA or RNA from its similarity to already existing sequences. And infer function. Although this methodology has sometimes been criticized for being inaccurate [2, 11], its popularity remains unquestionable, and numerous functional annotations in public databases are “by sequence homology”. And have a reference. However, alignment of existing references stored in the database with newly obtained DNA remains a relatively demanding computational task. BLAST [1] and later BLAT [5] have improved speed, but due to the number of sequences currently available, searching for a new sequence against a pool of known sequences will result in web search engines almost immediately. It can take a relatively long time to return. New tools designed for short read sequencing have since been developed, such as Bowtie [6] and BWA [7], to name just two, but these tools have been Designed to align any sequencing read with respect to. In order to achieve speed, such tools load a reference index into memory, thereby limiting the amount of reference DNA that can be handled.

  Applicants quickly identify a task that computationally requires finding the absolute best alignment between a collection of query sequences and a reference, and a reference that matches most from the set of query sequences A gap was observed between them. To the best of our knowledge, such as taking a set of short DNA or RNA sequences, such as reads coming out of a DNA sequencer, returning a list of references to either the complete genome or individual genes that the set represents, There is no simple tool. To do this, Applicants have identified alignment seeds in both BLAT and SSAHA [9, 10] and kUSCLLE [3] in order to identify the source of DNA sequences somewhat accurately within seconds. We propose to use k-mer in a manner separate from -mer counting.

Materials and Methods Published genomes, contigs, plasmids and individual genes available from EBI and NCBI were downloaded to our reference DNA. Each reference sequence is divided into overlapping k-mers, and for every k-mer across every reference, a key value store or NoSQL database (Applicants used KyotoCabinet [4]) is created, and each k-mer A list of identifiers corresponding to references having the k-mer is associated with mer (key in the database) (FIG. 1). Applicants called this the presence database. Similarly, the position in the reference where the k-mer was found was stored in a location that we called the position database (FIG. 1). Associations between reference identifiers and information, such as description lines and data sources, were stored in separate SQL databases.

  To score a short query sequence or set of reads, Applicants iterate through their random samples (Figure 2). For each array, Applicants iterate over successive k-mers, obtained by sliding a window of width k across the array. For each k-mer, if this has not been previously counted and is found in the presence database, Applicants query the location of the reference. Once every k-mer of a lead has been processed, Applicants examine the number of adjacent positions matched in the reference and are the highest concentration of matching k-mer that originates from the same lead across every matching reference Only consider the largest cluster of matches. For each such cluster, Applicants will update the list of already counted k-mers, perhaps adding the number of k-mers to the number previously added to the reference. Subsequently, the next array or read is processed. Applicants obtain a list of references with associated k-mer counts found to match. For each pair <reference, count>, the count is divided by the number of unique k-mers in the query set to get a rough score of the amount of DNA in the query matched by a given reference. If the query set exactly matches the sequence, the score will be 1, otherwise it will be smaller; for example, the query set is a mixture of equal proportions of the two references In that case, the score of both references would be around 0.5. The count is also divided by the size of the reference (the number of unique k-mers in the reference sequence) to get a rough score of the fraction of the reference represented by the query; this second score is the matching reference Helps avoid screening and bias to maximum reference. The final score is a weighted sum of these two scores, and the default is equal weight. If the query set is large, for example, if we consider every read obtained from a DNA sequencing run, only use a random sample of that set.

  To facilitate the use of the service, an HTML5 / Javascript® client running as a page in a web browser was run. At the time of export, Firefox 15.0 is the only browser that performs all the required features, and Applicants have been using Linux (R), Mac OS X, Microsoft Windows (R), and Android. Tested to work at 4.0.

  To benchmark Applicants' system originally designed to identify bacteria in sequencing data, Applicants are available from EBI at the beginning of 2012, which is a 747 bacterial genome Any sequence derived from bacteria was collected repeatedly. To simulate reads from a DNA sequencer, for each genome, Applicants created random, possibly overlapping subsequences from the genomic sequence; portions of length 50, 100, 150, 200 and 250 bases An array was used. Applicants have identified 0% (no errors), 1%, 5% and 10% to simulate both the class of sequencing errors and the presence of punctual mutations in real samples. A uniform random substitution of the base with a rate of Random samples of 100 partial sequences or reads were taken for each genome, length, and replacement rate, and this sampling was repeated 10 times.

Results For each bacterial genome, we collect 100 random simulated reads and include these bacterial genomes from among other references using our method. These are scored against the database and the rank of the query genome in the list of 25 best scores is recorded. The average rank and the standard deviation of the rank are shown in FIG.

  The closer the average rank is to 1, the better the scoring, and the smaller the standard deviation of the rank, the less rational the sampling effect. The number of missed ranks written out in each individual panel corresponds to the number of genomes that were not present in the 25 highest scores.

  With a 50 base long read, the performance is less than optimal, but with a query genome between 97% and 99% in the top 5 species with low substitution rates and in the top 15 species with higher substitution rates, Already there is a dramatic improvement with 100 base reads. Increasing lead lengths up to 250 bases helped compensate for the negative effects of higher substitution rates in the average rank.

  The length and substitution rate ranges used by the Applicants are Illumina (100 bases with about 0.1-1% error rate), Life Technologies' SOLiD 5500 (75 nt read with 0.01% error rate) , Ion Torrent PGM (200-300 bases with 1% error rate), or Pacific Bioscience (3,000 bases with 15% error rate), comparable to the range obtained from next generation sequencing platforms. Applicants' method has shown superior performance within these ranges, and Applicants have used paired-end sequencing, a technique used to provide longer lead substitutions. It is believed that further performance will be implemented by adding support. Applicants 'method appears to be relatively insensitive to sequencing errors, such as base substitutions, and the low rank expected for Applicants' test queries is minimized as the substitution rate increases. Affected.

  Thanks to the use of the NoSQL database, Applicants anticipate scaling up as genomic data becomes increasingly rich, indexing increasingly large collections of references in relatively affordable computer systems and Inquiries continue to be possible.

  To facilitate the use of Applicants' method, Applicants have developed a browser-based client. Applicants examined by size of raw FASTQ file up to 2Gb and monitored it, using only over 200Mb in RAM and returning results in less than 20 seconds.

Conclusion The concept underlying TAPIR is somewhat simple. While an increase in the size of the DNA database has been published and observed for at least a decade, recent developments in DNA sequencing technology have made the creation of data fast and affordable. Applicants claim that the matching of experimentally obtained DNA sequences to any known DNA is one of the most important challenges in bioinformatics. In this specification, Applicants show that this can be done with speed and ease that matches what Internet web search giants have made available to the general public. When considering tasks such as infection in patients, real-time surveillance such as bioterrorism defense or food safety with a desktop DNA sequencer, Applicants' method should narrow down the search space and perform more advanced analysis methods later Provides an initial step that can be done.

(Example 2)
In this example, tens of thousands of genomes and genomic regions derived from humans, mice, plants, fungi and archaea were referenced along with bacteria, viruses, phages and plasmids. Applicants also run a client that runs in a web browser and consumes a moderate amount of bandwidth to communicate with the server, but within a few seconds, get several gigabytes of raw sequencing data from a commodity portable computing device. Demonstrated the use of the client to process and identify. Thus, this example shows that the identification of DNA from raw leads can be as easy as a search engine query.

Querying a comprehensive set of references Matching a set of DNA sequences A subjective way to look at an alignment program is to divide these into two main categories: one query for a collection of known references Try to do everything to map the sequence (eg, BLAST), and the other is to try to map many short sequences to one specified reference as quickly as possible (eg, bowtie or BWA). . Applicants propose an intermediate approach that can identify good references for a large number of short sequences; Applicants match multiple sequences against a collection of reference sequences, Adopt which reference is best represented in the query set.

  The approach presented in this example does not involve any selection step in k-mer indexing, and this feature greatly simplifies the complexity of building from a collection of sequences. This sacrifices space and indexes k-mers that may be low in information value, but is offset by the following benefits: The process is linear in the total size of the collection of references and is self-evident Can be parallelized. This ultimately makes any known DNA indexing valid (similar to the web search engine indexing of any document on the Internet).

  In this example, Applicants' algorithm does more than just count k-mers, but does not perform either full mapping or alignment. The algorithm takes into account k-mer matching within the context of each lead and clusters matching k-mers close together.

  In this example, as shown in FIG. 5, while we used non-overlapping k-mers for indexing, we used overlapping k-mers in the query, Considering this as an implementation detail, one can easily use duplicate k-mers for indexing and non-duplicate k-mers in queries while maintaining the same guidelines for scoring matching references. .

  The time complexity of positioning n occurrences of a string of length p in a reference of size u indexed using k-mer is O if the tree or hash is used for k indexing and lookup. It has a calculation amount of (p + n log u) or O (p + n).

  In identifying a query set of DNA data, such as raw reads from a sequencer for diagnostic purposes, Applicants have identified the two brute force approaches that exist in mapping every lead to a comprehensive reference database. Have hundreds of megabytes or gigabytes of data transferred from the sequencing facility to the computing center and significant computational resources required to perform the task. The reference collection has 10,000 E.C. E. coli-sized bacteria and optimized aligners such as BWA and bowtie2 process raw sequencing data of 250M bases (approximately 60x in average coverage when the genome is 4M bases in size) Assuming that it takes 30 seconds to do this, it would take three and a half days for the CPU, but it can be trivially parallelized with multiple CPUs.

  In addition to the time complexity, the data transfer resulted in 250 M base DNA and moved the sequencing data to the data center holding the reference. Applicants' approach based on k-mer reduces detailed investigations, such as lead mapping or SNP calls, or even template-based de-novo assembly, to a small set of references. In assessing performance, Applicants optionally chose to consider the search as a success first simply if the correct answer exists in the set of five proposed matches. The task of mapping all leads to these references to accurately identify which one matches best can be performed in the same CPU in 12 minutes, despite the three and a half days foreseen per sample described above. It can be executed in a shorter period of time if a powerful multi-core architecture can be obtained. Every genome transfer represents about 20 M bases of DNA, which can be easily performed with a 3G mobile internet connection. Applicants' approach allows a mobile sequencing facility such as Ion bus [15] to perform critical diagnostic or scientific tasks at a remote location. If there are unmapped reads due to the presence of smaller regions, such as plasmids, virulence genes, viruses or bacterial mixtures, treat these reads in the same way and complete the contents by several iterations. Can be identified.

Benchmark Construction To benchmark our system, originally designed to identify bacteria in sequencing data, we derived from bacteria available from the EBI database at the beginning of 2012. Every sequence that was collected was repetitively collected, ie, 747 bacterial genomes, plus a complete database of references contained: Bacteria references, phages and viruses from NCBI , Plasmids as well as the human genome (see Table 1 below). Table 1 shows genome reference snapshots (reference sources and numbers) at the beginning of 2012. A reference is a complete genome or plasmid and a mixture of genomic fragments such as contigs or genes.

  To simulate the reads obtained from a DNA sequencer, for each genome, Applicants created random, possibly overlapping subsequences from the genome sequence; 50, 100, 150, 200 and 250 bases in length. A partial sequence was used. Applicants have rates of 0% (no errors), 1%, 5% and 10% to simulate both the class of sequencing errors and the presence of regular mutations in real samples. A uniform random substitution of the base was also introduced. Random samples of 100 partial sequences or reads were taken for each genome, length and replacement rate, and this sampling was repeated 5 times.

  Our objective is to find out what known DNA is present in the sample, or to assess whether the genome is close enough when counting uncertainties such as sequencing errors or mutations That is.

Predictive performance For each bacterial genome, we collect 100 random simulated reads and use our method to identify other bacteria, phage, plants, fungi, viruses and From a larger collection of sequences and genomes from mammals, these were scored against a database containing the bacterial genome, and the rank of the query genome in the list of 25 best matching references was recorded. . To evaluate the variability of results for each test bacterial genome, this was repeated 5 times per genome and the average rank and standard deviation of the ranks are presented in FIG.

  Although the performance was relatively low for 50 nucleotide long reads, Applicants observed a dramatic improvement when increasing the length of the read, and the length at the sequenced base The 100 leads were already close to maximum performance. The best result is that the correct genome is in the results list above 97% at the lower error rate in the top 5 species with low replacement rates and in the top 15 species with higher replacement rates Is shown. Increasing the lead length to 250 bases helped compensate for the negative effects of increasing error rate. Increasing the number of reads in random samples sent for identification did not have much effect. See FIG. 7: The 100 reads are a small amount of data but appear to be sufficient for DNA identification in many cases.

  As detailed above, Applicants' method aims to return the correct reference in the proposed set of matches, and by doing this, the procedure that the brute force approach requires computationally. Simplify the search space that requires searching by. Since all 25 analysis runs are still significant compared to the thorough search, it is almost certainly more rigorous than necessary to restrict yourself to find the query sequence in the top 5 results. It is pointed out that the method can already return the correct answer within a very small set of answer candidates.

  In the context of iterative search and identification, pointing to the correct bacterial species can already be considered a relatively successful answer, even if it is not a correct and accurate lineage or genomic reference. FIG. 6 shows that Applicants' identification procedure performs very well with reads greater than 50 nucleotides.

  The length and substitution rate ranges used by the Applicants are Illumina (up to 150 bases with an error rate of about 0.1-1%), Life Technologies SOLiD 5500 (maximum with an error rate of 0.01%). 75 nt lead), Ion Torrent PGM (up to 200-300 bases with 1% error rate) or Pacific Bioscience (3,000 bases with 15% error rate) Comparable. Applicants' method has shown superior performance within these ranges, and Applicants have added support for paired-end sequencing, a technique used to provide longer lead substitutions. Predict further increasing performance. Applicants 'method appears to be relatively insensitive to sequencing errors, such as base substitutions, and the low rank expected for Applicants' test queries is minimized as the substitution rate increases. Affected.

  Applicants have also attempted approaches in sequencing data from Ion Torrent PGM derived from samples ranging from viral and bacterial isolates to metagenomic mixtures. Very similar genomes in a collection of indexed references, such as multiple strains of the same species, contribute to performance degradation by increasing the probability of having a more closely related genome than the correct reference genome Can do. This is confirmed by an increase in performance when considering species rather than exact references, and is a moderate inconvenience that can eliminate ambiguity in the second iteration. Finally, we considered very promising results from sequencing from samples from a variety of mammals because we considered k-mers in the context of reads rather than isolated entities. And we expect to identify them reliably in the near future.

Compute performance server:
Memory usage on the server can be kept to a minimum by using disk-based key value storage, and tuning performance can be achieved by caching them in memory available on the computer that runs it. it can. Thanks to the use of the NoSQL database, Applicants also anticipate superior scale-up as genomic data becomes more and more rich, and an index of an increasingly large collection of references in relatively affordable computer systems Dates and inquiries continue to be possible.

  In this run, both the indexing system and the server are run in Python, and the 44G base reference DNA is indexed in a few hours using 8 cores (Intel Xeon, 2.93GHz) Sample processing takes several seconds. Significant acceleration can be achieved through optimization efforts, such as a bottleneck moved to C, but if the need becomes clear, dedicating additional cores increases the comprehensive performance in handling additional requirements. It is also possible.

client:
To facilitate the use of Applicants' method, Applicants have used Javascript® and HTML5 features that can be accessed at http://tapir.cbs.dtu.dk. Developed a browser-based client. The client is currently running on the latest Firefox release (version 15 or higher).

  With Firefox running on a relatively medium laptop with Intel Core i5 CPU achieved at 2.53 GHz, raw leads in FASTQ files up to 2 Gb in size can be processed in less than 30 seconds, The smaller the file, the faster it was, and it took several seconds to communicate with the server using less than 300Mb of RAM.

  Applicants further executed a console-based command line tool to perform Applicants' algorithm and subsequent alignment. Execution is available in a general software repository: https://bitbucket.org/lgautier/dnasnout-client. The implementation uses Applicants' algorithm on the fetch reference genome and performs these indexing and mapping of any reads by bowtie2. When considering 10 top leads, a complete iteration takes less than a minute, and one iteration is sufficient for 98% of cases. With the rapid development of browsers, Applicants anticipate that it will soon be possible to perform workflows similar to those performed by epidemiological laboratories using desktop sequencing runs using only a web browser.

Discussion Applicants argue that the matching of experimentally obtained DNA sequences to any known DNA is one of the most important challenges in bioinformatics. In this specification, applicants have shown that this can be done with speed and ease that matches what Internet web search giants have made available to the general public. When considering tasks such as real-time surveillance, such as infection, bioterrorism defense or food safety in patients, today's desktop DNA sequencers such as Ion Torrent PGM or Illumina MiSeq can already withstand the task, This method eliminates the need to transfer a large amount of raw data between a DNA sequencing laboratory and a computing facility, narrows the search space, and allows more advanced analysis methods to be performed locally later. Provides initial steps.

Sources of method genome references:
Published genomes, contigs, plasmids and individual genes available from EBI and NCBI were downloaded as our reference DNA. While the exact composition of the reference is expanding over time, Applicants listed the snapshots used in this example in Table 1.

Reference indexing:
Each reference sequence is divided into non-overlapping k-mers, and for every k-mer that spans every reference, a key value store or NoSQL database (we use KyotoCabinet [4]) is created, and each k-mer A mer (key in the database) is associated with a list of identifiers corresponding to references having the k-mer. Applicants called this the presence database. Similarly, we stored the location in the reference where the k-mer was found in what we call the location database. Since this yielded satisfactory results and because multiples of 4 were well suited for bit packing, k was chosen to be equal to 16. Associations between reference identifiers and information, such as description lines and data sources, were stored in separate SQL databases.

Scoring:
Applicants repeated through these random samples to score a short query sequence or set of reads. The larger the sample size, the more accurate this will be. For each array, Applicants iterated over successive k-mers, obtained by sliding a window of width k across the array. For each k-mer, if this was not previously counted and found in the presence database, Applicants queried the location of the reference. Once every k-mer of a lead has been processed, Applicants examine the number of adjacent positions matched in the reference and are the highest concentration of matching k-mer originating from the same lead across every matching reference Only the largest cluster of matches was considered. For each such cluster, Applicants updated the list of previously counted k-mers, adding the number of k-mers, possibly to the number previously added to the reference. Subsequently, the next sequence or read was processed. Once every lead has been processed, a list of references associated with k-mer counts found to match is obtained. For each pair <reference, count>, the count was divided by the number of unique k-mers in the query set to give a rough score of the amount of DNA in the query matched by a given reference. According to the illustrated scoring principle, if the query set exactly matches the sequence, the score will be 1, otherwise it will be smaller; If it is a mixture of equal proportions of the two references, the score for both references will be around 0.5. The count is also divided by the size of the reference to get a rough score for the fraction of the reference represented by the query; this second score helps to select matching references and avoid bias to the largest reference . The final score was calculated as a weighted sum of these two scores using equal weights. If the query set is large, for example, if we consider every read obtained from a DNA sequencing run, only use a random sample of that set.

Run the client:
To facilitate use of the service, Applicants have run an HTML5 / Javascript® client that runs as a page in a web browser. For this study, Firefox version 15 was used and the applicants were using Android 4.0 (tablet) with Linux (R), Mac OS X, Microsoft Windows (R) (various laptops and desktops). ASUS TF101-Applicants have tested this to work in (expect that they can also work from high-end smartphones). However, one skilled in the art will recognize that other suitable browsers may be useful as well. The client also runs as a Python library and command line tool for easy evaluation and integration in existing workflows and pipelines.

Other technical specifications:
With the exception of binding to the library, such as KyotoCabinet, all executions were performed on the server side using Python version 2.7.3. Web application uses a micro-framework Flash and is provided by lighttp. A client side library and command line tool was developed for Python version 3.3.

  One skilled in the art can execute the algorithm or portions of the algorithm in other suitable commonly known programming languages such as, for example, the C programming language, by reducing the time used for the query. It will be appreciated that the performance of the method can be improved.

References

Claims (63)

A method of identifying a likely source of a biological sequence, such as a short lead,
a) sampling a sequence or a subset of short reads from a source;
b) fragmenting sequences from the subset into k-mers;
c) interrogating one or more k-mers from the subset against a first collection containing k-mers of a reference sequence;
d) interrogating one or more k-mers from the subset against a second collection that includes the position of the k-mer in the reference sequence;
e) determining which references contain the one or more k-mers;
f) returning a description of a likely source reference, wherein the first collection containing the k-mer of the reference sequence is the second collection containing the position of the k-mer in the reference sequence How to be separate.   The method of claim 1, which does not include the use of an alignment algorithm on the sequence data, such as an alignment algorithm that uses a scoring matrix.   The method according to any of the preceding claims, wherein the querying step further comprises the step of determining the position of the k-mer in the reference sequence.   A method according to any preceding claim, wherein presence and position are used to determine the continuity of the query k-mer in the reference sequence.   The method according to any of the preceding claims, wherein the biological sequence is an amino acid sequence.   The method according to claim 1, wherein the biological sequence is a DNA or RNA sequence.   A method according to any preceding claim, wherein the k-mer query comprises determining an exact match between the query and the reference k-mer.   The query is at least one source sequence or short lead, preferably at least 50, such as at least 100, such as at least 150, such as at least 200, such as at least 250, such as at least 300, such as at least 400, For example, including any k-mer query derived from at least 500, such as at least 750, such as at least 1000, such as at least 1500, such as at least 2000, such as at least 2500, such as at least 5000 sequences. A method according to any preceding claim.   The source sequence is at least 50 bases, preferably at least 100 bases, such as at least 150 bases, such as at least 200 bases, such as at least 250 bases, such as at least 300 bases, such as at least 400, at least 500 or more. The method according to any of the preceding claims, wherein the method is a nucleotide sequence of a base.   Said subset of sequences is at least 1%, such as at least 2%, such as at least 4%, such as at least 5%, such as at least 6%, such as at least 7.5%, such as at least 10%, such as A method according to any preceding claim, comprising at least 15%, such as at least 25%, such as at least 30%, such as at least 35%, such as at least 40%, such as at least 50%, discrete sequences. .   The method according to any of the preceding claims, further comprising selecting one or more further subsets of the sequence and subjecting them to steps a) to f) according to claim 1.   The method according to any of the preceding claims, wherein the subset is random or filtered.   Any of the preceding claims, wherein the k-mer is of size 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64 or more. The method described in 1.   The method according to claim 1, wherein the k-mer is continuous.   The claim, wherein the k-mers are overlapping and gradually increase by at least 1, such as at least 2, such as at least 3, such as at least 4, such as at least 5, such as at least 6 bases or amino acids. The method in any one of.   A method according to any preceding claim, wherein the k-mer is a disjoint subsequence linkage.   A k-mer from a given sequence is queried against a database to determine the presence of the k-mer in one or more reference sequences and the position of the k-mer in the one or more reference sequences. A method according to any of the preceding claims.   The method of claim 17, wherein a location is queried only if the k-mer is present.   The method according to any of the preceding claims, wherein the score of the returned reference is calculated.   The method according to any of the preceding claims, wherein a score for the identified reference sequence is calculated and the score correlates with the number of k-mers from one or more sequences found in a given reference sequence. .   A score of the identified reference is calculated, said score correlating to the continuity by the average or approximate continuity of the local concentration of k-mers from one or more sequences found in the reference sequence, said claim A method according to any of the paragraphs.   8. The score of an identified reference is calculated, wherein the score correlates with the number of k-mers in a reference sequence that is also present in the subset of k-mers from the source. the method of.   23. A method according to any of claims 19 to 22, wherein likely source references are ranked according to the score or scores.   The method according to any of the preceding claims, wherein every k-mer from one source sequence or short read is queried and one or more scores of the source sequence or short lead are calculated.   A method according to any of the preceding claims, wherein a count of k-mers that match the reference sequence is obtained.   The method according to any of the preceding claims, wherein the score is obtained by dividing the count of k-mers matching the reference sequence by the number of unique k-mers in the queried subset.   27. A method according to claims 24 to 26, wherein a score is obtained by dividing the count of k-mers that match against a reference sequence by the size of the reference sequence.   28. The method of claims 24 to 27, wherein the score of the reference sequence is calculated as a weighted sum of the scores of claims 26 and 27.   A method according to any of the preceding claims, further comprising the step of querying any k-mer from the second source sequence, preferably the third source sequence.   The method according to any of the preceding claims, wherein the database query can be stopped once a reference organism has been identified with a defined statistical probability.   The method according to any of the preceding claims, wherein the database query can be aborted if a defined fraction of k-mers is not found in the database.   The database includes the following information about one or more likely references: sequence, coding sequence, regulatory sequence annotation, taxonomic name of the likely reference, likely reference The reference source, the group of further related references, the place where the reference was obtained (soil, sea, intestine or sewer, etc.), the time the reference sequence was obtained, the taxonomic classification, The method according to any one of the preceding claims, wherein one or more of information on a database (NCBI or EBI / Sanger database, etc.) related to a database in which a reference sequence is downloaded is output.   The method according to any of the preceding claims, wherein the database outputs the most likely reference sequence, and preferably the database outputs the complete genomic sequence of the most likely reference species.   A method according to any preceding claim, wherein results from references having very similar sequences or results from further related references are grouped in the output.   A method according to any of the preceding claims, wherein several iterations of the method are performed, e.g. in the first iteration the most abundant reference is identified and the most abundant reference from a source sequence or short read. A method of removing sequences derived from a reference.   36. The method of claim 35, further comprising identifying a second rich reference in a second iteration, removing sequences derived from the second rich reference, and the like.   38. The method of claim 36, further comprising identifying a reference with a high probability of insertion in the second iteration.   8. A method according to any preceding claim, further comprising first removing source sequences that align with sequences from a defined reference.   Any of the preceding claims, comprising ignoring a k-mer from the source sequence if a defined number of k-mers from one source sequence is not present in the database. The method described.   The method according to any of the preceding claims, wherein the query comprises ignoring k-mers from one or more predefined references.   A method according to any preceding claim, wherein the raw sequence as obtained from the nucleic acid sequencer is queried.   A method according to any preceding claim, wherein adaptive sampling is used. A database for use in a method as defined by claims 1-42 comprising a k-mer of a reference sequence comprising:
a) a first collection of k-mers from a reference sequence;
b) a database comprising: a second collection of each k-mer position in the reference sequence.   44. The database of claim 43, further comprising information regarding a full-length sequence associated with a given reference, and / or a source of the reference, and / or one or more taxonomic descriptors of the reference.   45. A database according to any of claims 43 to 44, wherein a k-mer in the database is attached to a hash function that assigns a unique key to each unique k-mer.   46. A database according to any of claims 43 to 45, wherein each unique k-mer in the first collection is related by a vector to information about those references in which the k-mer exists.   47. A database according to any of claims 43 to 46, wherein each unique k-mer in the second collection, if present, is related by a vector to information about its position in each reference.   Reference identifier and description line, source of data, sequence, coding sequence, regulatory sequence annotation, likely taxonomic name, close reference to the likely reference, supply of the reference Source, additional group of related references, where the reference was obtained (soil, sea, intestine, sewer, etc.), when the reference sequence was obtained, taxonomic classification, related species, download the reference sequence 48. A database according to any of claims 43 to 47, further comprising a third collection or database having a type of information selected from the group consisting of information about the created database (such as NCBI or EBI / Sanger database) .   49. The k-mer has a length of 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64 or more. A database according to any of the above.   50. The database according to any one of claims 43 to 49, wherein the k-mers do not overlap.   51. The method of claim 43-50, wherein the k-mers overlap and are gradually increased by at least 1, such as at least 2, such as at least 3, such as at least 4, such as at least 5, such as at least 6 bases or amino acids. A database as described in any of the above.   52. A database according to any of claims 43 to 51, comprising a k-mer derived from the complete sequence of each reference.   53. A database according to any of claims 43 to 52, comprising sequence information derived from humans, animals, mammals, birds, fish, fungi, insects, plants, bacteria, archaea, viruses and / or plasmids.   54. Database according to any of claims 43 to 53, divided into sub-databases stored on several different servers.   According to one or more taxonomic descriptors selected from gates, classes, eyes, families, genera and species, or one or more environmental descriptors such as source, distribution, origin and past query frequency 55. A database according to any of claims 43 to 54, organized into sub-databases.   A data processing system for identifying a likely source of a source array comprising an input device, a central processing unit, a memory, and an output device, wherein the data processing system is executed A data processing system, wherein data representing an instruction sequence for performing the method according to claims 1 to 42 is stored therein, and the memory further comprises a database according to any of claims 43 to 55.   57. The system of claim 56, wherein the database is stored on a server, the input device and output device are clients, and the client and server are connected via a data communication connection.   58. A system according to any of claims 56 to 57, wherein the client is selected from a portable computing device such as a personal computer, a fixed PC, a portable PC, a smartphone or the like.   59. Any of claims 56 to 58, wherein the client includes an instruction sequence that allows the client to sample a subset of a source array, fragment them into k-mers and communicate them to the server. The system described in Crab.   The client further includes an instruction sequence that enables the client to perform assembly of a source array into one or more larger arrays based on the array communicated from the server to the client. 60. The system of claim 56-59, comprising.   61. A system according to any of claims 56 to 60, connected to a sequencing device via a data connection.   43. A computer software product containing an instruction sequence that, when executed, causes the method of claims 1-42 to be performed.   43. An integrated circuit product containing an instruction sequence that, when executed, causes the method of claims 1-42 to be performed.