In this paper we present a new evolutionary algorithm for the protein folding problem. We study the problem in the 3D FCC HP model which has been widely used in previous research. Our focus is to develop evolutionary algorithms (EA) which are robust, easy to operate and can handle various energy functions. We propose lattice rotation for crossover and K-site move for mutation, which form the key components of our evolutionary algorithms. Experiment shows that our algorithms are able to find minimum-energy conformations for many sequences whose optimal conformations are not found in previous EA-based algorithms. Furthermore, our idea can be easily integrated into Monte Carlo and Tabu searches as approaches for local searches.

As there are more and more online sources available on the Web, it becomes very time-consuming, if not impossible, to visit and search all web sites, one by one. Many search engines has been developed to help users find information of their need. However, search engines work poor for online sources whose data are often in deep web, which is not part of surface web indexed by standard search engines. Metasearch is a very popular mechanism to search deep web. Metasearch provides the capability for users to search and access all of the information sources in one query submission. One of the fundamental problems in building metasearch systems is to learn wrappers which extract and integrate data records from query result pages returned from online sources. In this paper, develop an unsupervised approach for wrapper induction that combines visual, content and HTML tag information. Our approach first learns a visual content model that alleviates HTML tag differences among data records, and then finds a tag model from all data records that match the visual content model. Experiment shows that our approach works well for data sets collected from well-known search engines and shopping websites.

As databases can overlap each other, data matching that aims to identify data records or elements describing the same object is one of the fundamental problems in physical integration of databases. Matching results can be applied to induce more accurate and complete object descriptions, remove data redundancy, check data consistency and generate cross-links. In this paper, we present a multilevel approach to match data between pathway databases that consist of 3 levels of information, compounds, reactions and pathways. Compounds comprise reactions, and reactions comprise pathways. Our main idea is to use relationships discovered in lower levels to infer relationships in upper levels, and use relationships in upper levels to enhance relationships in lower levels. In particular, we first use attributes of compounds to identify compound matching, i.e. to map compounds in one database to those in another database. Compound matching is then used to induce reaction matching. Reaction matching is used to induce pathway matching as well as to enhance compound matching. We experiment our approach for integration of two well known pathway databases KEGG and MetaCyc. The experiment shows that our approach identifies 1025 matchings in compound level, 968 matchings in reaction level, and 387 relations in pathway level. According to matching result, we assign EC number to 84 reactions in MetaCyc that do not have EC number, and discover some duplicate errors in both databases. Furthermore, our approach identifies 532 of the 544 unification links provided by MetaCyc. The recall rate is 0.977.

Automatic identification and extraction of interesting objects instead of just related Web pages is useful to users of the World Wide Web. For example, an instructor teaching a data mining course may be interested in finding all text books, lecture notes, slides, homeworks and term projects from Web pages of all data mining and their related courses. In this paper, we present a tool WISE for extraction of objects from Web pages, which are of interest. In WISE, objects in HTML pages are defined as nodes in an extension of DOM trees. Extraction of objects is then formulated as the problem of classification of tree nodes. We develop a mechanism for object specifications, and a specific-to-general (bottom-up) search algorithm for learning object specifications. Experiment shows that WISE works well for extracting objects such as, for example, extracting items in paper lists, and extracting lists of lecture notes in algorithms courses.

Here, we study the problem of integrating documents from different sources into a comprehensive topic hierarchy. Our objective is to develop efficient techniques that improve the accuracy of traditional categorization methods by incorporating categorization information provided by data sources into categorization process. Notice that in the World-Wide Web, categorization information is often available from information sources. We present several enhancing techniques that use categorization information to enhance traditional methods such as naive Bayes and support vector machines. Experiment on collections from Openfind and Yam, and Google and Yahoo!, well-known popular Web sites in Taiwan and USA, respectively, shows that our techniques significantly improve the classification accuracy from, for example, 55% to 66% for Naive Bayes, and from 57% to 67% for SVM for the data set collected from Yam and Openfind.

This paper presents a window-based approach to design lock-free concurrent implementations for a class of top-down tree structures that supports operations whose executions can be modeled as a process of moving a window along a rooted simple path. Our approach can be implemented on multiprocessor systems that, support load-linked, store-conditional and check-valid synchronization primitives that are supported in MIPS-II and DEC Alpha architectures. Our approach achieves high degree of concurrency, requires low coordination overhead, is wait-free and fault tolerant. Simulation shows that our approach is efficient.

In this paper we give new techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in internal memory. We use these techniques to develop optimal and practical algorithms for a number of important large-scale problems. We discuss our algorithms primarily in the context of single processor/single disk machines, a domain in which they are not only the first known optimal results but also of tremendous practical value. Our methods also produce the first known optimal algorithms for a wide range of two-level and hierarchical multilevel memory models, including parallel models. The algorithms are optimal both in terms of I/O cost and internal computation.>

There is a large and growing body of literature concerning the solution of geometric problems on mesh-connected arrays of processors [5,9,14,17]. Most of these algorithms are optimal (i.e., run in time Ο(n1/d) on a d-dimensional n-processor array), and they all assume that the parallel machine is trying to solve a problem of size n on an n-processor array. What happens when we have parallel machine for efficiently solving a problem of size p, and we are interested in using it to solve a problem of size n < p? The answer to that question has to do with a fundamental, and yet (at least so far) little-studied property of geometric problems: their parallel-decomposability. More specifically, given that a problem of size p can be solved on a parallel machine P faster by a factor of (say) s(p) than on a RAM alone, then that problem is fully parallel-decomposable for P if a RAM to which the parallel machine P is attached can solve arbitrarily large problems with a speedup of also s(p) when compared to a RAM alone. The issue has been settled for the sorting problem when P is a linear systolic array [1,2,3,11]. Here we show that many geometric problems are fully parallel-decomposable for (multidimensional) mesh-connected arrays of processors.