11626813
Sorting Signed Permutations by Fixed-length Reversals
A signed n-permutation is a permutation on {1,2,…,n} in which each element is labelled by a positive or negative sign. Here we consider the problem of sorting signed permutations by fixed-length reversals. Indeed, limiting the transformations to reversals of length exactly k can be very restrictive, for example, (+1,+3,+2,+4,…,+n) can never be sorted to (+1,+2,+3,+4,…,+n) by 2-reversals. That is, for given two signed permutations it is not obvious whether they can be sorted to each other by k-reversals. Thus in 1996, Chen and Skiena gave the following open problem: what is the connectedness of signed permutations under fixed-length reversals? In this paper, we resolve this open problem when "fixed-length" is even, and give a characterization of the connectedness of signed n-permutations under 2l-reversal, for both linear and circular permutations.
7451094
Orthogonal (g, f)-factorizations in networks
Let G = (V,E) be a graph and let g and f be two integer-valued functions defined on V such that k ≤ g(x) ≤ f(x) for all x ∈ V . Let H1,H2, · · · ,Hk be subgraphs of G such that |E(Hi)| = m, 1 ≤ i ≤ k, and V (Hi) ∩ V (Hj) = ∅ when i 6= j. In this paper it is proved that every (mg + m − 1,mf −m + 1)-graph G has a (g, f)-factorization orthogonal to Hi for i = 1, 2, · · · , k and shown that there are polynomial-time algorithms to find the desired (g, f)-factorizations.
26295637
A Linear-Time Algorithm for Computing Translocation Distance between Signed Genomes
The study of evolution based on rearrangements leads to a rearrangement distance problem, i.e., computing the minimum number of rearrangement events required to transform one geonome to another. In this paper we study the translocation distance problem, modeling the evolution of genomes by translocations. We present a linear-time algorithm for computing the translocation distance between signed genomes in this paper, improving a previous O(n 3) bound by Hannenhalli in 1996.
1876314
A 2-Approximation Algorithm for Path Coloring on Trees of Rings
A tree of rings is an undirected graph obtained from a tree by replacing each node of the tree with a cycle and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common. Given a set of paths on a tree of rings, the routing problem is to color the paths with the smallest number of colors so that any two paths sharing an edge are assigned different colors. We present a 2-approximation algorithm in this paper.
9386148
Orthogonal factorizations of graphs
Let G be a graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). We use dG(x) to denote the degree of a vertex x of G. A graph G is called a (g,f)-graph if g(x) ≤ dG(x) ≤ f(x) for each x ∈ V(G). Then a spanning subgraph F of G is said to be a (g,f)-factor of G if F itself is a (g,f)-graph. A (g,f)-factorization of G is a partition of E(G) into edge disjoint (g,f)-factors. Let F = {F1,F2,... ,Fm} be a factorization of G and H be a subgraph of G with m edges. If Fi, 1 ≤ i ≤ m, has exactly one edge in common with H, we say that F is orthogonal to H. In this paper it is proved that every (mg + k,mf - k)-graph contains a subgraph R such that R has a (g,f)-factorization orthogonal to a given subgraph with k edges, where m and k are positive integers with 1 ≤ k > m and g(x) ≥ 0. This result has been conjectured by Yan in Yan (Sci. China Ser. A 41(1) (1998) 48).
40174055
A PTAS for Distinguishing (Sub)string Selection
Consider two sets of strings, B (bad genes) and G (good genes), as well as two integers db and dg (db ? dg). A frequently occurring problem in computational biology (andother fields) is to finda (distinguishing) substring s of length L that distinguishes the bad strings from goodstrings, i.e., for each string si ? B there exists a length-L substring ti of si with d(s, ti) ? db (close to badstrings) andfor every substring ui of length L of every string gi ? G, d(s, ui) ? dg (far from goodstrings). We present a polynomial time approximation scheme to settle the problem, i.e., for any constant ? > 0, the algorithm finds a string s of length L such that for every si ? B, there is a length-L substring ti of si with d(ti, s) ? (1+?)db and for every substring ui of length L of every gi ? G, d(ui, s) ? (1 - ?)dg, if a solution to the original pair (db ? dg) exists.
1481458
Geometry of contour-based correspondence for stereo
We consider the problem of computing stereo correspondence for scenes dense in physical structures, such as a bouquet of flowers. Boundaries are the space curves, formally governed by the projective geometry induced by the stereo camera configuration and by the differential structure of curves in the scene. We propose that the correspondence problem can be solved by relating the differential structure in the left and right image planes to the geometry of curves in space. Based on the Frenet equations, we show that the compatibility between pairs of corresponding points, and tangents and curvatures at those points, is related to the local approximation of a space curve using an osculating helix. A relaxation labeling network demonstrates that the compatibilities can be used to infer appropriate correspondences in a scene. Examples are shown.
6029798
Efficient Holistic Twig Joins in Leaf-to-Root Combining with Root-to-Leaf Way
Finding all the occurrences of a twig pattern on multiple elements in an XML document is a core operation for efficient evaluation of XML queries. Holistic twig join algorithms, TwigStack and TSGeneric, have been recognized as optimal solutions when the twig pattern only involves A-D(ancestordescendant) relationships, while iTwigJoin can be optimal for partial twig patterns that contain A-D only or P-C (parent-child) only relationships. However, existing algorithms involve unnecessary computations and CPU cost of them can be further improved, and we in this paper mainly address this problem. We first propose three effective optimization rules to avoid those unnecessary computations, and then present two algorithms incorporated with these optimization rules to effectively answer twig patterns in leaf-to-root combining with root-to-leaf way. Experimental results on various datasets indicate that our algorithms perform significantly better than existing proposals.
16653782
Genetic Algorithm Based on Independent Component Analysis for Global Optimization
We design a new Genetic Algorithm based on Independent Component Analysis for unconstrained global optimization of continuous function. We use Independent Component Analysis to linearly transform the original dimensions of the problem into new components which are independent from each other with respect to the fitness. We project the population on the independent components and obtain corresponding sub-populations. We apply genetic operators on the sub-populations to generate new sub-populations, and combine them as a new population. In other words, we use Genetic Algorithm to find the optima on the independent components, and combine the optima as the global optimum for the problem. As we actually reduce the original high-dimensional problem into sub-problems of much fewer dimensions, the solution space decreases exponentially and thus the problem becomes easier for Genetic Algorithm to solve. The experiment results verified that our algorithm produced optimal or close-to-optimal solutions better than or comparable to those produced by some of other Genetic Algorithms and it required much less fitness evaluations of individuals.
109807
One table stores all: Enabling painless free-and-easy data publishing and sharing
In this paper, we present a free-and-easy data publishing and sharing system based on folksonomy. The system accepts data objects described with user-created metadata, called data units. The system supports flexible structure on the data units, and places no restrictions on the vocabulary used. We devise a generic table model for storing and representing the data units of various structures. We propose a framework for managing the data units and providing browsing, searching and querying services over them. We present our current approaches and discuss relevant research issues.
10744767
Typing Aberrance in Signal Transduction
We have developed a calculus, called Ipi, for describing the aberrance in biological models. Our approach extends the traditional pi calculus to handle aberrant process in the signal transduction. In this paper we propose a typing system that replaces the tag system of Ipi calculus. It is shown that the typing system is equal to the tag system in terms of the expressive power.