87458683
A Knowledge-Based Approach to Protein Local Structure Prediction
Local structure prediction can facilitate ab initio structure prediction, protein threading, and remote homology detection. However, previous approaches to local structure prediction suffer from poor accuracy. In this paper, we propose a knowledge-based prediction method that assigns a measure called the local match rate to each position of an amino acid sequence to estimate the confidence of our approach. To remedy prediction results with low local match rates, we use a neural network prediction method. Then, we have a hybrid prediction method, HYPLOSP (HYbrid method to Protein LOcal Structure Prediction) that combines our knowledge-based method with a neural network method. We test the method on two different structural alphabets and evaluate it by QN, which is similar to Q3 in secondary structure prediction. The experimental results show that our method yields a significant improvement over previous studies.
5367915
A Maximum Entropy Approach to Biomedical Named Entity Recognition
Machine learning approaches are frequently used to solve name entity (NE) recognition (NER). In this paper we propose a hybrid method that uses maximum entropy (ME) as the underlying machine learning method incorporated with dictionary-based and rule-based methods for post-processing. Simply using ME for NER, inaccurate boundary detection of NEs and misclassification may occur. Some NEs are partially recognized by ME. In the post-processing stage, we use dictionary-based and rule-based methods to extend boundary of partially recognized NEs and to adjust classification. We use GENIA corpus 3.01 to conduct 10-fold cross-verification experiments. To evaluate the performance, we consider the longest NE annotations. We evaluate our approach using standard precision (P), recall (R), and F-score, where F-score is defined as 2PR/(P+R). The precision, recall and F-score ([P, R, F]) of our ME module for overall 23 categories is [0.512, 0.538, 0.525], and after the post-processing the performance becomes [0.729, 0.711, 0.72] for [P, R, F]. For protein, DNA and RNA classes, our method achieves [P, R, F] of [0.77, 0.80, 0.785], [0.653, 0.748, 0.7], and [0.716, 0.788, 0.752], respectively. The post-processing stage significantly improves the performance of our ME-based NER module.
1251407
Reference metadata extraction using a hierarchical knowledge representation framework
The integration of bibliographical information on scholarly publications available on the Internet is an important task in the academic community. Accurate reference metadata extraction from such publications is essential for the integration of metadata from heterogeneous reference sources. In this paper, we propose a hierarchical template-based reference metadata extraction method for scholarly publications. We adopt a hierarchical knowledge representation framework called INFOMAP, which automatically extracts metadata. The experimental results show that, by using INFOMAP, we can extract author, title, journal, volume, number (issue), year, and page information from different kinds of reference styles with a high degree of precision. The overall average accuracy is 92.39% for the six major reference styles compared in this study.
341424
Domain Event Extraction and Representation with Domain Ontology
With domain ontology, a meaningful index of document indexing, such as the domain events structure in this paper, can be defined. Since the construction of domain ontology is costly, an automatic domain ontology acquisition is preferred. We find that named entity can be a clue of domain event acquisition from the training corpus. Therefore , we add the named entity recognition module into the automatic domain ontology acquisition process. Thus, a subject-verb-object-modifier (SVOM) indexing can be constructed. Our experimental results demonstrate that the automatic event extraction and ontology acquisition can be good resources for text categorization and further information processing.
17603178
A Linear Time Algorithm for Finding a Maximal Planar Subgraph Based on PC-Trees
In Shih & Hsu, a planarity test was introduced utilizing a data structure called PC-trees, generalized from PQ-trees. They illustrated that a PC-tree is more natural in representing planar graphs. Their algorithm starts by constructing a depth-first-search tree and adds all back edges to a vertex one by one. An important feature in the S&H algorithm is that, at each iteration, at most two terminal nodes need to be computed and the unique tree path between these two nodes provides essentially the boundary path of the newly formed biconnected component. 
 
In this paper we modify their PC-tree algorithm and introduce the deferred planarity test (DPT), which has the added benefit of finding a maximal planar subgraph (MPS) in linear time when the given graph is not planar. DPT is an incremental algorithm, which only computes a partial terminal path at each iteration. DPT continually deletes back edges that could create a violation to the formation of those partial terminal paths so that, at the end, the subgraph constructed is guaranteed to be planar. 
 
The key to the efficiency of the S&H and the DPT algorithms lies in their management on the creation and destruction of biconnected components in which the PC-tree plays a major role. Previously, there have been reports that the MPS problem can be solved in linear time. However, there was no concrete data structure realizing them.
5724385
An iterative relaxation technique for the NMR backbone assignment problem
NMR spectroscopy is one of the popular experiments to determine protein structures. An important stage of protein structure determination by using NMR is protein backbone resonance assignment (or backbone assignment for short). Due to the messiness and disorder of NMR spectral data, backbone assignment is usually a tedious and time-consuming manual work. This raises a great interest in developing an efficient and automatic method to perform backbone assignment. An iterative algorithm is proposed that is equipped with two operations: grouping and linking. Grouping is responsible for peak picking and part of connectivity determination. Ideally, those peaks with the same H/sup N/ and N chemical shifts can be grouped together; peaks belonging to the same group can be used to determine the order of two consecutive spin systems. However, in real situation, grouping is a difficult task due to false positives and false negatives. We sometimes add hypothetic peaks to tackle false negatives and use linking operation to remove false positives. Linking is responsible for part of connectivity determination and backbone assignment. Given a protein sequence and partial connectivity information, we try to link connected spin systems as much as possible. False positive spin systems may create conflicts in the linking stage. To find a good assignment on a noisy dataset, the backbone assignment problem is modeled as a maximum independent set problem. Although the problem is NP-complete, there are heuristic methods that obtain pretty good results.
2578042
Trustworthy keyword search for regulatory-compliant records retention
Recent litigation and intense regulatory focus on secure retention of electronic records have spurred a rush to introduce Write-Once-Read-Many (WORM) storage devices for retaining business records such as electronic mail. However, simply storing records in WORM storage is insuffcient to ensure that the records are trustworthy, i.e., able to provide irrefutable proof and accurate details of past events. Specifically, some form of index is needed for timely access to the records, but unless the index is maintained securely, the records can in effect be hidden or altered, even if stored in WORM storage. In this paper, we systematically analyze the requirements for establishing a trustworthy inverted index to enable keyword-based search queries. We propose a novel scheme for effcient creation of such an index and demonstrate, through extensive simulations and experiments with an enterprise keyword search engine, that the scheme can achieve online update speeds while maintaining good query performance. In addition, we present a secure index structure for multi-keyword queries that supports insert, lookup and range queries in time logarithmic in the number of documents.
17795095
A Simple Test for the Consecutive Ones Property
A (0,1)-matrix satisfies the consecutive ones property if there exists a column permutation such that the one's in each row of the resulting matrix are consecutive. Booth and Lueker [1976] designed a linear time testing algorithm for this property based on a data structure called “PQ-trees”. This procedure is very complicated and the linear time amortized analysis is also rather involved. We develop an off-line testing algorithm for the consecutive ones property without using PQ-trees. Our approach is based on a decomposition technique which separates the rows into “prime” subsets which admit unique column orderings that realize the consecutive ones property. The success of this approach is based on finding a good “row ordering” to be tested iteratively.
38774895
Fast Algorithms for the Dominating Set Problem on Permutation Graphs
AnO(n log logn) (resp.O(n2 log2n)) algorithm is presented to solve the minimum cardinality (resp. weight) dominating set problem on permutation graphs, assuming the input is a permutation. The best-known previous algorithm was given by FArber and Keil, where they use dynamic programming to get anO(n2 (resp.O(n3)) algorithm. Our improvement is based on the following three factors: (1) an observation on the order among the intermediate terms in the dynamic programming, (2) a new construction formula for the intermediate terms, and (3) efficient data structures for manipulating these terms.
16227528
Fast image retrieval using color-spatial information
Abstract. In this paper, we present an image retrieval system that employs both the color and spatial information of images to facilitate the retrieval process. The basic unit used in our technique is a single-colored cluster, which bounds a homogeneous region of that color in an image. Two clusters from two images are similar if they are of the same color and overlap in the image space. The number of clusters that can be extracted from an image can be very large, and it affects the accuracy of retrieval. We study the effect of the number of clusters on retrieval effectiveness to determine an appropriate value for “optimal'' performance. To facilitate efficient retrieval, we also propose a multi-tier indexing mechanism called the Sequenced Multi-Attribute Tree (SMAT). We implemented a two-tier SMAT, where the first layer is used to prune away clusters that are of different colors, while the second layer discriminates clusters of different spatial locality. We conducted an experimental study on an image database consisting of 12,000 images. Our results show the effectiveness of the proposed color-spatial approach, and the efficiency of the proposed indexing mechanism.
7586483
Video search reranking via information bottleneck principle
We propose a novel and generic video/image reranking algorithm, IB reranking, which reorders results from text-only searches by discovering the salient visual patterns of relevant and irrelevant shots from the approximate relevance provided by text results. The IB reranking method, based on a rigorous Information Bottleneck (IB) principle, finds the optimal clustering of images that preserves the maximal mutual information between the search relevance and the high-dimensional low-level visual features of the images in the text search results. Evaluating the approach on the TRECVID 2003-2005 data sets shows significant improvement upon the text search baseline, with relative increases in average performance of up to 23%. The method requires no image search examples from the user, but is competitive with other state-of-the-art example-based approaches. The method is also highly generic and performs comparably with sophisticated models which are highly tuned for specific classes of queries, such as named-persons. Our experimental analysis has also confirmed the proposed reranking method works well when there exist sufficient recurrent visual patterns in the search results, as often the case in multi-source news videos.