Browsing by Author "Hsu, D. Frank"

Now showing 1 - 8 of 8

Feature selection and combination criteria for improving accuracy in protein structure prediction
(2007-06-01)
Lin, Ken-Li
;
Lin, Chun-Yuan
;
Huang, Chuen-Der
;
Chang, Hsiu-Ming
;
Yang, Chiao-Yun
The classification of protein structures is essential for their function determination in bioinformatics. At present, a reasonably high rate of prediction accuracy has been achieved in classifying proteins into four classes in the SCOP database according to their primary amino acid sequences. However, for further classification into fine-grained folding categories, especially when the number of possible folding patterns as those defined in the SCOP database is large, it is still quite a challenge. In our previous work, we have proposed a two-level classification strategy called hierarchical learning architecture (HLA) using neural networks and two indirect coding features to differentiate proteins according to their classes and folding patterns, which achieved an accuracy rate of 65.5%. In this paper, we use a combinatorial fusion technique to facilitate feature selection and combination for improving predictive accuracy in protein structure classification. When applying various criteria in combinatorial fusion to the protein fold prediction approach using neural networks with HLA and the radial basis function network (RBFN), the resulting classification has an overall prediction accuracy rate of 87% for four classes and 69.6% for 27 folding categories. These rates are significantly higher than the accuracy rate of 56.5% previously obtained by Ding and Dubchak. Our results demonstrate that data fusion is a viable method for feature selection and combination in the prediction and classification of protein structure.
Mutually independent hamiltonian cycles for the pancake graphs and the star graphs
(2009-09-06)
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Huang, Hua-Min
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
A hamiltonian cycle C of a graph G is an ordered set < u(1), u(2,) ..., u(n(G)), u(1)> of vertices such that u(i) not equal u(j) for i not equal j and u(i) is adjacent to u(i+1) for every i is an element of {1, 2, ..., n(G) - 1} and u(n(G)) is adjacent to u(1), where n(G) is the order of G. The vertex u(1) is the starting vertex and u(i) is the ith vertex of C. Two hamiltonian cycles C(1) = < u(1), u(2), ..., u(n(G)), u(1)> and C(2) = < v(1), v(2), ..., v(n(G)), v(1)> of G are independent if u(1) = v(1) and u(i) not equal v(i) for every i is an element of {2, 3, ..., n(G)}. A set of hamiltonian cycles {C(1), C(2), ..., C(k)} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there exist k mutually independent hamiltonian cycles of G starting at u. In this paper, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the n-dimensional pancake graphs P(n) and the n-dimensional star graphs S(n). It is proven that IHC(P(3)) = 1, IHC(P(n)) = n - 1 if n >= 4, IHC(S(n)) = n - 2 if n is an element of {3, 4} and IHC(S(n)) = n - 1 if n >= 5. (C) 2009 Elsevier B.V. All rights reserved.
On the extremal number of edges in hamiltonian connected graphs
(2010-01-01)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
Assume that n and delta are positive integers with 3 <= delta < n. Let hc(n, delta) be the minimum number of edges required to guarantee an n-vertex graph G with minimum degree delta(G) >= delta to be haimiltonian connected. Any n-vertex graph G with delta(G) >= delta is hamiltonian connected if vertical bar E(G)vertical bar >= hc(n, delta). We prove that hc(n, delta) = C(n - delta + 1, 2) + delta(2) - delta + 1 if delta <= [n+3x(n mod 2)/6] + 1, hc(n, delta) = C(n - [n/2] + 1, 2) + [n/w](2) - [n/2] + 1 if [n+3x(n mod 2)/6] + 1 < delta <= [n/2], and hc(n, delta) = [n delta/2] if delta > [n/2]. (C) 2009 Elsevier Ltd. All rights reserved.
On the Extremal Number of Edges in Hamiltonian Graphs
(2011-09-01)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
Assume that n and delta are positive integers with 2 <= delta < n. Let h(n, delta) be the minimum number of edges required to guarantee an n-vertex graph with minimum degree delta(G) >= delta be hamiltonian, i.e., any n-vertex graph G with delta(G) >= delta is hamiltonian if vertical bar E(G)vertical bar >= h(n, delta). We move that h(n, delta) = (n - delta, 2) + delta(2) +1 if delta <= left perpendicular n + 1 + x ((n + 1mld 2)/6 right perpendicular, h(n, delta) = C(n - left perpendicular n - 1/2 right perpendicular, 2) + left perpendicular n - 1/2 right perpendicular(2) + 1 if left perpendicular n + 1 + 3 x ((n + 1) mod2)/6 < delta <= left perpendicular n - 1/2 right perpendicular, and h(n, delta, = inverted right perpendicular n delta/2inverted left perpendicular if delta > left perpendicular n - 1/2 right perpendicular.
On the spanning connectivity and spanning laceability of hypercube-like networks
(2007-08-22)
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
;
資訊工程學系
Let u and v be any two distinct nodes of an undirected graph G, which is k-connected. For 1 <= w <= k, a w-container C(u, v) of a k-connected graph G is a set of w-disjoint paths joining u and v. A w-container C(u, v) of G is a w*-container if it contains all the nodes of G. A graph G is w*-connected if there exists a w*-container between any two distinct nodes. A bipartite graph G is w*-laceable if there exists a w*-container between any two nodes from different parts of G. Let G(0) = (V-0, E-0) and G(1) = (V-1, E-1) be two disjoint graphs with vertical bar V-0 vertical bar= vertical bar V-1 vertical bar. Let E = ((v, phi(v)) vertical bar v is an element of V0, phi(v) is an element of V-1, and phi : V-0 -> V-1 is a bijection}. Let G = G(0) circle plus G(1) = (V0 boolean OR V1, E-0 boolean OR E-1 boolean OR E). The set of n-dimensional hypercube-like graph H-n(') is defined recursively as (a) H-1(') = {K2}, K2 = complete graph with two nodes, and (b) if G(0) and G(1) are in H-n', then G = G(0) circle plus G(1) is in H-n+1('). Let B-n' = {G is an element of H-n' and G is bipartite} and N-n' = H-n' B-n'. In this paper, we show that every graph in B-n' is w*-laceable for every w, 1 <= w <= n. It is shown that a constructed N-n'-graph H can not be 4*-connected. In addition, we show that every graph in N-n' is w*-connected for every w, 1 <= w <= 3. (c) 2007 Published by Elsevier B.V.
On the spanning fan-connectivity of graphs
(2009-04-06)
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
;
資訊工程學系
Let G be a graph. The connectivity of G, kappa(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, C(k)(u, v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k*-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, kappa*(G), is the maximum integer k such that G is w*-connected for 1 <= w <= k if G is 1*-connected. Let x be a vertex in G and let U = {y(1), y(2,) . . . , y(d)} be a subset of V(G) where x is not in U. A spanning k - (x, U)-fan, F(k)(x, U), is a set of internally-disjoint paths {P(1), P(2,) . . . , P(k)} such that P(i) is a path connecting x to y(i) for 1 <= i <= k and U(i=1)(k) V(P(i)) = V(G). A graph G is k*-fan-connected (or k(f)*-connected) if there exists a spanning Fk(x, U)-fan for every choice of x and U with vertical bar U vertical bar = k and x is not an element of U. The spanning fan-connectivity of a graph G, kappa(f)*(G), is defined as the largest integer k such that G is w(f)*-connected for 1 <= w <= k if G is 1(f)*-connected. In this paper, some relationship between kappa(G), kappa*(C), and kappa(f)*(G) are discussed. Moreover, some sufficient conditions for a graph to be k(f)*-connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k*-pipeline-connected. Published by Elsevier B.V.
On the spanning w-wide diameter of the star graph
(2006-12-01)
Lin, Cheng-Kuan
;
Huang, Hua-Min
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
;
資訊工程學系
Let a and v be any two distinct nodes of an undirected graph G, which is k-connected. A container C(u, v) between a and v is a set of internally disjoint paths {P(1), P(2),..., P(W)} between a and v where 1 <= w <= k. The width of C(u, v) is w and the length of C(u, v) {written as I[C(u, v)]} is max{I(P(i)) 1 <= I <= w}. A w-container C(u, v) is a container with width w. The w-wide distance between u and v, d(w)(u, v), is min{I(C(u, v)) C(u, v) is a w-container). A w-container C(u, v) of the graph G is a w*-container if every node of G is incident with a path in C(u, v). That means that the w-container C(u, v) spans the whole graph. Let S(n) be the n-dimensional star graph with n >= 5. It is known that S(n) is bipartite. In this article, we show that, for any pair of distinct nodes u and v in different partite sets of S(n), there exists an (n - 1)*-container C(u, v) and the (n - 1)-wide distance d((n-1))(u, v) is less than or equal to n!/n-2 + 1. In addition, we also show the existence of a 2*-container C(u, v) and the 2-wide distance d(2)(u, v) is bounded above by nI/2 + 1. (C) 2006 Wiley Periodicals, Inc.
The construction of mutually independent Hamiltonian cycles in bubble-sort graphs
(2010)
Shih, Yuan-Kang
;
Lin, Cheng-Kuan
;
Hsu, D. Frank
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
A Hamiltonian cycle C=< u(1), u(2), ..., u(n(G)), u(1) > with n(G)=number of vertices of G, is a cycle C(u(1); G), where u(1) is the beginning and ending vertex and u(i) is the ith vertex in C and u(i)not equal u(j) for any i not equal j, 1 <= i, j <= n(G). A set of Hamiltonian cycles {C(1), C(2), ..., C(K)} of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B(n))=n-1 if n >= 4, where B(n) is the n-dimensional bubble-sort graph.