Application of W-curves and TSP to Clustering HIV1 Sequences

摘要

The high mutation rate in HIV-1 makes it difficult to treat and analyze. Monitoring the evolution of drug resistance requires frequent resequencing, but comparing and visualizing the progress is difficult. One difficulty is simply locating the areas of interest: gaps and crossover mutations make it difficult to isolate clinically significant sequences for comparison. Effectively displaying the results of comparisons grouped according to multiple regions is also a problem. Our comparison algorithm based on the W-curve helps automate the comparison process, producing results suitable for clustering via a modified solution to the Traveling Salesman Problem ("TSP"). Appropriate color-coding of the TSP results allows us to display the results of multiple comparisons effectively for single samples or time-series. The results can be useful for providing guidance in treatment, analyzing the membership in anonymous study populations, tracking the evolution of drug resistance in populations, or rates of co-infection within study groups.