Genotype Imputation Using K-Nearest Neighbors and Levenshtein Distance Metric

With several new genome sequencing methods such as Next Generation Sequencing (NGS) and nanopore technologies, there exists a wide range of techniques to explore different genetic variants and their impacts. However, these sequences can become degraded as some genotypes are not detected, leading to missing base pair values. Imputing these gaps in the data is essential to analyze the data properly. Some past studies have shown that certain machine learning models have, to some extent, been able to accurately impute the missing values in genotypes. This paper aims to outline an imputation approach created using the K-Nearest Neighbors algorithm and Levenshtein Distance parameters on the Mus genus. This approach involved imputing randomly masked nucleotide bases in any given gene sequence in Mus musculus by using data of the same genes from similar species in the Phylogenetic tree, namely Mus pahari and Mus caroli. Predictions for the missing spaces were generated by comparing a set number of bases before and after a given sequence of missing nucleotide bases in the target species, Mus musculus, to the same number of bases occurring before and after every possible prediction in the similar species using the Levenshtein distance metric. We found that using our proposed algorithm, we were able to predict over 500,000 individual missing bases in the gene sequences of Mus musculus with accuracies up to 87%. The model maintained an accuracy greater than 80% when all the blank spaces (sequences of consecutive blank spaces) were less than 200 characters long.