Identifying species-specific subsequences in bacteria transcription terminators-A machine learning approach

Abstract

Transcription Terminators (TTs) play an impor-tant role in bacterial RNA transcription. Some bacteria are known to have Species-Specific Subsequences (SSS) in their TTs, which are be-lieved containing useful clues to bacterial evolu-tion. The SSS can be identified using biological methods which, however, tend to be costly and time-consuming due to the vast number of sub-sequences to experiment on. In this paper, we study the problem from a computational per-spective and propose a computing method to identify the SSS. Given DNA sequences of a tar-get species, some of which are known to contain a TT while others not, our method uses machine learning techniques and is done in three steps. First, we find all frequent subsequences from the given sequences, and show that this can be effi-ciently done using generalized suffix trees. Sec-ond, we use these subsequences as features to characterize the original DNA sequences and train a classification model using Support Vector Machines (SVM), one of the currently most effec-tive machine learning techniques. Using the pa-rameters of the resulting SVM model, we define a measure called subsequence specificity to rank the frequent subsequences, and output the one with the highest rank as the SSS. Our experi-ments show that the SSS found by the proposed method are very close to those determined by biological experiments. This suggests that our method, though purely computational, can help efficiently locate the SSS by effectively narrowing down the search space.