New algorithms for automated phylogenetic reconstruction using artificial intelligence and data mining techniques

Academic and industrial research in the late 90s have brought about an exponential explosion of DNA sequence data. Automated expert systems are being created to help biologists to extract patterns, trends and links from this ever-deepening ocean of information. Two such systems aimed on retrieving and subsequently utilizing phylogenetically relevant information have been developed in this dissertation, the major objective of which was to automate the often difficult and confusing phylogenetic reconstruction process. ^ Popular phylogenetic reconstruction methods, such as distance-based methods, attempt to find an optimal tree topology (that reflects the relationships among related sequences and their evolutionary history) by searching through the topology space. Various compromises between the fast (but incomplete) and exhaustive (but computationally prohibitive) search heuristics have been suggested. An intelligent compromise algorithm that relies on a flexible “beam” search principle from the Artificial Intelligence domain and uses the pre-computed local topology reliability information to adjust the beam search space continuously is described in the second chapter of this dissertation. ^ However, sometimes even a (virtually) complete distance-based method is inferior to the significantly more elaborate (and computationally expensive) maximum likelihood (ML) method. In fact, depending on the nature of the sequence data in question either method might prove to be superior. Therefore, it is difficult (even for an expert) to tell a priori which phylogenetic reconstruction method—distance-based, ML or maybe maximum parsimony (MP)—should be chosen for any particular data set. ^ A number of factors, often hidden, influence the performance of a method. For example, it is generally understood that for a phylogenetically “difficult” data set more sophisticated methods (e.g., ML) tend to be more effective and thus should be chosen. However, it is the interplay of many factors that one needs to consider in order to avoid choosing an inferior method (potentially a costly mistake, both in terms of computational expenses and in terms of reconstruction accuracy.) ^ Chapter III of this dissertation details a phylogenetic reconstruction expert system that selects a superior proper method automatically. It uses a classifier (a Decision Tree-inducing algorithm) to map a new data set to the proper phylogenetic reconstruction method. ^

"Gangsterism," HIV, and "tik:" An exploration of Cape Town youth

Since early 2000, the Western Cape of South Africa has been documented as an area for monitoring the spread of HIV. The majority of HIV cases occur within individuals between the ages of 15-49 years, and the epidemic is believed to be complicated by the increased use of crystal methamphetamine (CM), or “tik.” Eighty percent of current CM users in Cape Town are under the age of 21 years, and almost 18% of current HIV cases are in individuals under the age of 24 years. Gang membership in youth may also be complicating the HIV problem as gangs feed the social acceptability of “tik” and encourage sexual violence. With almost half the population of Cape Town in their mid-twenties, the threat of a new HIV epidemic complicated by CM use has become a concern in the young adults of the city. Research into the relationships between gang membership and drugs/violence has been extensively studied in the Cape Flats. Yet, few have examined the role of gangs in the perpetuation of HIV. Therefore, the purpose of this investigation was exploratory in nature. Key informant interviews from Cape Town youth were used as case illustrations to generate potential hypotheses on the interrelationships between “gangsterism,” “tik” use, and HIV. Such awareness is important if effective efforts to reduce HIV incidence in Cape Town (and Sub-Saharan Africa) are to transpire. If the problem of CM is not addressed quickly, the Cape Flats may find itself with a higher rate of an already uncontrollable HIV epidemic. ^