A computer-implemented and reference-free method for identifying variants in nucleic acid sequences

A computer-implemented method for identifying of nucleic acid variants between two genomic states comprising the steps of:

• A) Inputting 2 sets of nucleic acid reads, which are sequences retrieved from a nucleotide sequencing method, wherein the first set of reads corresponds to cells representing a first test state, and the second set of reads corresponds to cells representing a second control state;
• B) Filtering the reads, wherein the filtering comprises:
• B1) Keeping only the reads with at least a percentage X1 of their bases with a Phred quality score higher than 20, being X1 equal to or above 90%;
• B2) Splitting the reads with an undefined nucleotide, giving one sequence before, and one sequence after the undefined nucleotide, the latter being discarded;
• and
• B3) Discarding the sequence reads with less than X2 bases, wherein X2 is from 25 to 50;
• C) Generating a hashtable structure comprising:
• C1) Generating a number of N-X2+1 new reads for each read of sequence length N, wherein the new N-X2+1 reads correspond to all k-mers with length X2 nucleotides;
• and
• C2) Building a hashtable structure, which comprises all the k-mers generated in step C1) and further comprises the number of times each k-mer is observed in the two sets of reads corresponding to first and second states.
• D) Detecting candidate variants in the sequence between first state and second state, wherein a k-mer of the hashtable structure is taken as a candidate breakpoint, which represents a variant between the first and second states, if it fulfills all the following requirements:
• D1) At least one inflection based on a k-mer's stem must have at least X3 reads with the same variation between first and second states, being X3 at least 2;
• D2) The percentage of first state reads in second state reads is not over a threshold X4, to account for possible contamination of control state reads with test state reads, wherein X4 is at least 5%.
• E) Clustering and filtering test and control reads derived from all candidate breakpoints accepted in step D to build blocks, by carrying out the steps:
• E1) Retrieving reads which contain the stem of at least one k-mer that represents the candidate breakpoint selected in step D);
• E2) The reads of step E1) with at least X5 k-mer variants within a window of X6 nucleotides are taken as leading reads, wherein X5 is at least 7 and X6 is at least 10;
• E3) Reads whose k-mers share at least one stem with a leading read are merged to give a block;
• and
• E4) If the nucleic acid whose variant is being identified is a double stranded DNA, then both forward and reverse variants are taken into account when building the block.
• F) Aligning blocks taking their leading reads as a reference:
• F1) For each read in the block, take the leading read's stem and find the longest inflection or partial inflection between the read and the leading read. F2) Successively position each read so that its matching inflection or partial inflection is aligned against the leading read;
• wherein:
• “candidate breakpoint” means the candidate nucleotide position where the sequence changes, that is immediately flanking a sequence variant.
• “inflection” means a fragment of length k that can be derived from extending a stem of a length lower than the length of a k-mer of length k;
• and
• “stem” means a fragment of a k-mer of length k with S defined bases, where S<k, and k-S omitted (undefined) bases;
• a k-mer being understood as all possible substrings of length k that are contained in a string.