Bioinformatics and text segmentation have attracted enormous research efforts in recent years. Classification techniques, especially profile hidden Markov model (PHMM) and conditional random field (CRF), are established computational vehicles in these two fields for extracting useful information from the vast amount of data resulted from rapid progress in molecular biology and ever increasing World Wide Web activities.
In this dissertation, we have developed techniques that exploit partial information to overcome a number of significant limitations of extant PHMM and CRF techniques in bioinformatics and text segmentation. Our work has advanced classification techniques in these two fields along the PHMM and CRF directions.
Our research on classification in bioinformatics has been conducted in the context of Toxin Knowledge Base (TKB), a comprehensive bioinformatics resource to detect potential virulent proteins. One of the most important research problems in TKB is to improve the accuracy of predicting whether a protein is potentially virulent based on sequence homology and active site similarity.
PHMM is recognized as the state-of-the-art for detecting sequence homology. Extant PHMM training approaches either use completely unaligned or completely aligned sequences. The PHMMs resulted from these two training approaches present contrasting trade-offs w.r.t. alignment information and the accuracy of the search outcome. Producing the complete alignment information is a labor intensive process involving expensive structural analysis of entire sequences. We have developed a PHMM training technique that is parameterized w.r.t. alignment information. Our technique can improve the accuracy of PHMMs when training sequences are only partially aligned.
Current techniques for profiling 3-D biological structures with PHMM are restricted in that they only deal with entire protein structures and cannot be applied to important functional substructures such as active sites. We have expanded PHMM to profile protein active sites for their similarity search. The core of our technique is a novel serialization that captures certain conserved physico-chemical and structural features of active sites. Although our sequential representation of active sites captures only partial information about them, experiments show that our technique is practical.
In the field of text segmentation, one of the biggest limitations of existing CRF approaches is the need for manual labeling of training data, which is generally labor intensive and time consuming. We have developed a CRF training technique that can eliminate the manual work needed for labeling examples and automatically learn CRF from partial training information in structured reference data.
Our experiences show that our partial information exploiting techniques can improve PHMM classification accuracy when completely aligned sequences are not available, expand PHMM applicability on 3-D structures, or eliminate manual work in labeling training sequences for CRF.