In this paper, we define a new subclass of integer linear programming problems called the composition problem. We shall propose efficient algorithms for solving this problem and its variants. Moreover, as an application of the composition problem, those algorithms are applied to solve the P-constrained secure set problem, which is a variation of the secure set problem introduced in [5], on trees. A P-constrained secure set problem is to find a minimum secure set containing a set of |P| predetermined vertices.

BACKGROUND: Many research results show that the biological systems are composed of functional modules. Members in the same module usually have common functions. This is useful information to understand how biological systems work. Therefore, detecting functional modules is an important research topic in the post-genome era. One of functional module detecting methods is to find dense regions in Protein-Protein Interaction (PPI) networks. Most of current methods neglect confidence-scores of interactions, and pay little attention on using gene expression data to improve their results. RESULTS: In this paper, we propose a novel hub-attachment based method to detect functional modules from confidence-scored protein interactions and expression profiles, and we name it HUNTER. Our method not only can extract functional modules from a weighted PPI network, but also use gene expression data as optional input to increase the quality of outcomes. Using HUNTER on yeast data, we found it can discover more novel components related with RNA polymerase complex than those existed methods from yeast interactome. And these new components show the close relationship with polymerase after functional analysis on Gene Ontology. CONCLUSION: A C++ implementation of our prediction method, dataset and supplementary material are available at http://hub.iis.sinica.edu.tw/Hunter/. Our proposed HUNTER method has been applied on yeast data, and the empirical results show that our method can accurately identify functional modules. Such useful application derived from our algorithm can reconstruct the biological machinery, identify undiscovered components and decipher common sub-modules inside these complexes like RNA polymerases I, II, III.

To deal with the issue of data unbalanced condition among a task of multilingual speech recognition and a phenomenon of pronunciation variations across languages, we propose an approach to clustering context dependent phones from an extended phone set in an acoustic model trained on a data unbalanced bilingual corpus. First, we generate an extended phone set using pronunciation modeling by a confidence measure between Mandarin and Taiwanese. Second, we use a two-step agglomerative hierarchical clustering with delta Bayesian information criteria to automatically generate a merged extended phone set (MEPS). Third, we choose a parametric modeling technique, model complexity selection, to increase the final number of Gaussian components dependent on the available training data in a data unbalanced condition. The experimental results show that the proposed automatic extending phone clustering approach reduced relative syllable error rate by 8.3% over the best result of the decision tree based phone clustering approach.

UNLABELLED: Included in Prokaryotic Growth Temperature database (PGTdb) are a total of 1334 temperature data from 1072 prokaryotic organisms, Bacteria and Archaea: PGTdb integrates microbial growth temperature data from literature survey with their nucleotide/protein sequence and protein structure data from related databases. A direct correlation is observed between the average growth temperature of an organism and the melting temperature of proteins from the organism. Therefore, this database is useful not only for microbiologists to obtain cultivation condition, but also for biochemists and structure biologists to study the correlation between protein sequences/structures and their thermostability. In addition, the taxonomy and ribosomal RNA sequence(s) of an organism are linked through NCBI Taxonomy and the Ribosomal RNA Operon Copy Number Database umdb, respectively. PGTdb is the only integrated database on the Internet to provide the growth temperature data of the prokaryotes and the combined information of their nucleotide/protein sequences, protein structures, taxonomy and phylogeny. AVAILABILITY: http://pgtdb.csie.ncu.edu.tw

In this paper, we sketch common properties of a class of so-called subgraph optimization problems that can be systematically solved on distance-hereditary graphs. Based on the found properties, we then develop a general problem-solving paradigm that solves these problems efficiently in parallel. As a by-product, we also obtain new linear-time algorithms by a sequential simulation of our parallel algorithms. Let T d |V|,|E|) and P d (|V|,|E|) denote the time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M d . Based on the proposed paradigm, we show that the maximum independent set problem, the maximum clique problem, the vertex connectivity problem, the domination problem, and the independent domination problem can be sequentially solved in O(|V|+|E|) time, and solved in parallel in O(T d (|V|,|E|)+log |V|) time using O(P d (|V|,|E|)+|V|log |V|)processors on M d . By constructing a decomposition tree under a CREW PRAM, we also show that T d (|V|,|E|)=O(log 2 |V|) and P d (|V|,|E|)=O(|V|+|E|).

A new approach to the generation of a feature‐point‐driven facial animation is presented. In the proposed approach, a hypothetical face is used to control the animation of a face model. The hypothetical face is constructed by connecting some predefined facial feature points to create a net so that each facet of the net is represented by a Coon’s surface. Deformation of the face model is controlled by changing the shape of the hypothetical face, which is performed by changing the locations of feature points and their tangents. Experimental results show that this hypothetical‐face‐based method can generate facial expressions which are visually almost identical to those of a real face.

A new approach for the generation of feature point-driven facial animation is presented. This approach is based on the construction of a hypothetical face formed by connecting face feature points into a net and representing each facet of the net by a mathematically expressed surface to control the deformation of a real face model. The deformation is controlled by changing both the locations of the feature points and their tangents. The experimental results show that the hypothetical-surface-based method can generate almost identical facial expressions to a real face.

Traffic smoothing for delivery of online VBR media streams is one of the most important problems in designing multimedia systems. Given available client buffer and a window-sliding size, conventional approaches try to reduce bandwidth allocated in each window. However, they can not lead to the minimization of bandwidth allocated for transmitting the entire stream. Although a window-sliding approach was introduced previously to further reduce the bandwidth allocated, it was computational costly. In this paper, an effective and efficient online traffic-smoothing scheme is proposed. Different from the conventional static window-sliding approaches, this approach dynamically decides the suitable window-sliding size to online smooth the bursty traffic. Then, an aggressive workahead scheme is applied in transmitting the entire stream. By examining different media streams, the approach has a small bandwidth, high bandwidth utilization and small computation cost. Considering the online transmission of a Star War movie, our approach result is 13% less for the bandwidth and 4% less for the network idle rate than SLWIN(1). Comparing the number of window sliding, our approach is 75% less than SLWIN(1). The relations between the characteristic of the input traffic and the behavior of obtained scheduling results are discussed. Finally, an extension of the proposed approach to resolve the latency and quality tolerance applications is also introduced.

Given a pre-recorded VBR video, we have proposed an O(n) algorithm to smooth the transmission schedule with the minimum required resources. N is the number of video frames. As n is usually very large and varying for different videos, it is not suitable for online computation. To facilitate resource management and admission control for QoS (quality-of-service) guarantees, we need to explore the relations among the required resources. Thus, whenever a new request is presented, the admission control procedure can easily check the required resources against the available resources and decides to admit this new request or not. To compute these relations (such as rate-buffer and rate-delay), a native algorithm takes O(n/sup 3/) time complexity. An O(n log n) algorithm is proposed to characterize the low-bounds of resources allocated for transmitting a pre-recorded VBR video. Having these pre-computed functions, the admission control procedure is as simple as a chart look-up with O(1) time complexity to allocate the required resources.

In this paper, we present a system that extracts and generalizes terms from Internet documents to represent classification knowledge of a given class hierarchy.We propose a measurement to evaluate the importance of a term with respect to a class in the class hierarchy, and denote it as support.With a given threshold, terms with high supports are sifted as keywords of a class, and terms with low supports are filtered out.To further enhance the recall of this approach, Mining Association Rules technique is applied to mine the association between terms.An inference model is composed of these association relations and the previously computed supports of the terms in the class.To increase the recall rate of the keyword selection process.we then present a polynomialtime inference algorithm to promote a term, strongly associated to a known keyword, to a keyword.According to our experiment results on the collected Internet documents from Yam search engine, we show that the proposed methods In the paper contribute to refine the classification knowledge and increase the recall of keyword selection. 'In the paper, we use "term" as word or phrase, which is extracted from the Internet documents, rather than use "keyword"."Keyword" is representative to the concept, while "term" is probably nonrepresentatlve.

We present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree for a distance-hereditary graph which take O(log n) time using O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of a given graph, respectively. We also find a maximum weighted clique of a distance-hereditary graph in O(log/sup 2/ n) time using O(n+m) processors on a CREW PRAM.

This paper proposes a wavelet-based approach to solving the shape from shading (SFS) problem. The proposed method takes advantage of the nature of wavelet theory, which can be applied to efficiently and accurately represent "things", to develop a faster algorithm for reconstructing better surfaces. In order to improve the robustness of the algorithm, two new constraints are introduced into the objective function to strengthen the relation between an estimated surface and its counterpart in the original image. Thus, solving the SFS problem becomes a constrained optimization process. In the first stage of the process, the set of function variables to be solved is represented by a wavelet format. Due to this format, the set of differential operators of different orders which is involved in the whole process can be approximated with the connection coefficients of Daubechies bases. In each iteration of the optimization process an appropriate step size which will result in maximum decrease of the objective function is determined. After finding correct iterative schemes, the solution of the SFS problem will finally be decided. Compared with conventional algorithms, the proposed scheme makes great improvements on the accuracy as well as the convergence speed of the SFS problem.>

Abstract The dynamic constraints technique has been proposed for building geometrical models composed of rigid bodies, which are made to act naturally, according to Newtonian laws, by specifying constraints on their states. In computer animation, the dynamic constraints technique alleviates the work‐load of animators who formerly had to plan animated sequences in detail by intuition alone. Nevertheless, for some real‐world applications, it is desirable to have a mechanism that makes physically‐based elements move according to a given scenario by providing some control states. The control states can be represented by transient constraints that are to be met and then released immediately. In this paper, a technique called the sequential‐goal constraints technique is proposed to provide such a mechanism. With the sequential‐goal constraints technique, it is easy to specify transient constraints according to a given scenario and derive proper forces and torques to drive an element to meet each transient constraint exactly at a specified time so that the whole motion of the element is continuous and integral.