Categorizing HIV-1 subtypes using an ant-based clustering algorithm

David King, Wei Hu

.

DOI: 10.4236/jbise.2010.38104                

Abstract

Human Immunodeficiency Virus (HIV) is especially difficult to treat due to its rapid mutation rate. There are currently eleven different genomic subtypes of HIV-1, as well as a number of recombinant subtypes. An area of study in bioinformatics is the development of algorithms to identify the subtypes of HIV-1 genomes. Ant-based algorithms have the ability to find global solutions in optimizations problems, and are also able to process complex data efficiently. We proposed a new technique named Ant Colony Anchor Algorithm (ACAA), using anchors of training data on a topographic map to categorize HIV-1 sequences based on ant-based clustering. We used three sets of sequences from the POL region of the HIV-1 genome. We categorized these three dataset with the Subtype Analyzer (STAR), a current HIV-1 categorization algorithm, and the ACAA. We found that the ACAA returned higher accuracy values of 83.2%, 67.1%, and 53.5% for our three datasets respectively, than the STAR’s 47.3%, 49.4% and 18%. The results of the ACAA are the average results of 20 runs of the algorithm. We also observed the performance of the algorithm on specific subtypes, and observed that while the STAR and ACAA performed with similar accuracy on several subtypes (A, B, and C in particular), the ACAA had a significant advantage over the STAR in others, especially in categorizing recombinant subtypes.

Keywords

Ants; Clustering; HIV; Classification; Subtype; STAR; ATTA; Bioinformatics

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Myers, E.R., et al. (2005) A statistical model for HIV-1 sequence classification using the subtype analyzer (STAR). Bioinformatics, 21(17), 3535-3540.
[2]	Oliveira, T., et al. (2005) An automated genotyping system for analysis of HIV-1 and other microbial sequences. Bioinformatics, 21(19), 3797-3800.
[3]	Handl, J. (2003) Ant-based methods for tasks of clustering and topographic mapping: Improvements, evaluation and comparison with alternative methods. Ph.D. Thesis, Friedrich-Alexander University, Erlangen-Nürnberg.
[4]	Chen, L., et al. (2004) An adaptive ant colony clustering algorithm. Proceedings of the 3rd International Conference on Machine Learning and Cybernetics, Shanghai, 26-29 August 2004, 1387-1392.
[5]	Deneubourg, J.L., et al. (1991) The dynamics of collective sorting: Robot-like ants and ant-like robots. Proceedings of the 1st International Conference on Simulation of Adaptive Behavior: From Animals to Animats, MIT Press, Cambridge, 1, 356-365.
[6]	Handl, J., et al. (2004) Strategies for increased robustness of ant-based clustering. Engineering Self-Organising Systems (Lecture Notes in Computer Science), 2977, 90- 104.
[7]	Handl, J., et al. (2004) Ant-based clustering and topographic mapping. Artificial Life, 12(1), 35-61.
[8]	Lee, M., et al. (2007) An ant-based clustering system for knowledge discovery in DNA chip analysis data. Proceedings of World Academy of Science, Engineering and Technology, 32, 261-266.