Fast Edit Distance Prediction for All Pairs of Sequences in Very Large NGS Datasets

All the known edit distance calculation algorithms run in near quadratic time with respect to sequence length. For very large number of sequences such as next generation sequencing (NGS) datasets, all pair edit distance calculation based on near quadratic run time may take days or weeks. To solve this performance bottleneck problem, several sub-quadratic run time algorithms have been proposed. Recently, Pramanik et al. [1] has proposed fast reference sequence based edit distance prediction method which addresses this performance bottleneck problem. They are very effective for correctly predicting smaller edit distances (useful, for example, clustering NGS datasets with low threshold) but less effective for larger edit distances. In this paper, we propose faster edit distance prediction method based on a very small number of special reference sequences. These sequences are very effective for predicting close to 100% accuracy. They require several novel techniques based on non-matching sub sequences. We have provided Propositions and Theorems to justify the basis for developing these novel techniques. Using these strategies, we are able to develop a linear time edit distance prediction method with respect to sequence length.