17 Result(s)
within
Chuan Yi Tang
Algorithm Analysis and Problem Complexity
-
Chapter and Conference Paper
Balanced Multi-process Parallel Algorithm for Chemical Compound Inference with Given Path Frequencies
To enumerate chemical compounds with given path frequencies is a fundamental procedure in Chemo- and Bio-informatics. The applications include structure determination, novel molecular development, etc. The pro...
-
Chapter and Conference Paper
CAPS Genomic Subty** on Orthomyxoviridae
The Orthomyxoviridae is a family of single strained RNA viruses including five genera: Influenza virus A, Influenza virus B, Influenza virus C, Thogotovirus, and Isavirus. Usually, Influenza viruses are identifie...
-
Chapter and Conference Paper
Probe Selection with Fault Tolerance
Microarray techniques play an important role for testing some reactions of diseases which are caused by viruses. Probes in microarray are one kind of the most important materials. Usually, scientists use a uni...
-
Chapter and Conference Paper
3-Points Relationship Based Parallel Algorithm for Minimum Ultrametric Tree Construction
To construct an evolutionary tree is an important topic in computational biology. An evolutionary tree can symbolize the relationship and histories for a set of species. There are many models had been proposed...
-
Chapter and Conference Paper
An Efficient Parallel Algorithm for Ultrametric Tree Construction Based on 3PR
In the computational biology and taxonomy, to construct phylogenetic tree is an important problem. A phylogenetic tree can represent the relationship and histories for a set of species and helpful for biologis...
-
Chapter and Conference Paper
Efficient Algorithms for Regular Expression Constrained Sequence Alignment
Imposing constraints is an effective means to incorporate biological knowledge into alignment procedures. As in the PROSITE database, functional sites of proteins can be effectively described as regular expres...
-
Chapter and Conference Paper
A Fast Technique for Constructing Evolutionary Tree with the Application of Compact Sets
Constructing an evolutionary tree has many techniques, and usually biologists use distance matrix on this activity. The evolutionary tree can assist in taxonomy for biologists to analyze the phylogeny. In this...
-
Chapter and Conference Paper
On the Full and Bottleneck Full Steiner Tree Problems
Given a graph G = (V, E) with a length function on edges and a subset R of V, the full Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. Then the full Steiner tree proble...
-
Chapter and Conference Paper
The Full Steiner Tree Problem in Phylogeny
Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V, E) with a length function on E and a proper subset R ⊂ V, the ...
-
Chapter and Conference Paper
A New Measure of Edit Distance between Labeled Trees
One of the most important problem in computational biology is the tree editing problem which is to determine the edit distance between two rooted labeled trees. It has been shown to have significant applicatio...
-
Chapter and Conference Paper
Efficient Minus and Signed Domination in Graphs
We show that the efficient minus (resp., signed) domination problem is NP-complete for chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (resp., for chorda...
-
Chapter and Conference Paper
Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices
Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances sa...
-
Chapter and Conference Paper
Approximation Algorithms for Some Optimum Communication Spanning Tree Problems
Let G = (V, E,w) be an undirected graph with nonnegative edge weight w, and r be a nonnegative vertex weight. The productrequirement optimum communication spanning tree (PROCT) problem is to find a spanning tree
-
Chapter and Conference Paper
A Linear-Time Algorithm for Constructing an Optimal Node-Search Strategy of a Tree
Ellis et al., proposed algorithms (in terms of vertex separation) to compute the node-search number of an n-vertex tree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An ...
-
Chapter and Conference Paper
Edge and node searching problems on trees
In this paper, we show that there is a natural correspondence between a tree's edge-search strategy and its node-search strategy. By doing so, we simplify the previous linear time algorithm for determining the...
-
Chapter and Conference Paper
Efficient domination on permutation graphs and trapezoid graphs
The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graph...
-
Chapter and Conference Paper
Graph searching on chordal graphs
Two variations of the graph searching problem, edge searching and node searching, are studied on several classes of chordal graphs, which include split graphs, interval graphs and k-starlike graphs.
