Browsing by Author "Chiu, WC"

Now showing 1 - 2 of 2

Approximate solutions for the Maximum Benefit Chinese Postman Problem
(2005-10-20)
Pearn, WL
;
Chiu, WC
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
The Maximum Benefit Chinese Postman Problem (MBCPP) is an interesting and practical generalization of the classical Chinese Postman Problem, which has many real-world applications. Each arc on the MBCPP network is associated with a service cost for the traversal with service, a deadhead cost for the traversal with no service, and a set of benefits. Each time an arc is traversed, a benefit is generated. The objective of the MBCPP is to find a postman tour traversing a selected set of arcs with the total net benefit maximized. Such a generalization reflects real-world situations more closely. The MBCPP has been shown to be more complicated than the Rural Postman Problem, which is an NP-hard problem. Therefore, it is difficult to find polynomial-time bounded algorithms to solve the problem exactly. In this paper, we first review an existing exact solution procedure, and introduce several heuristic algorithms including the Branch-Scan algorithm, the Connection algorithm with various connection strategies, and the Directed Tree algorithm, to solve the MBCPP approximately. We also apply one-opt, two-opt, component exchange, and component-drop procedures to improve the solutions. The proposed algorithms are tested and compared. Extensive computational results are provided and analysed.
Structure-stability-activity relationship in covalently cross-linked N-carbamoyl D-amino acid amidohydrolase and N-acylamino acid racemase
(2006-06-09)
Chiu, WC
;
You, JY
;
Liu, JS
;
Hsu, SK
;
Hsu, WH
N-Acylamino acid racemase (NAAAR) and N-carbamoyl-D-amino-acid amidohydrolase (D-NCAase) are important biocatalysts for producing enantiopure a-amino acids. NAAAR forms an octameric assembly and displays induced fit movements upon substrate binding, while D-NCAase is a tetramer that does not change conformation in the presence of a ligand. To investigate the effects of introducing potentially stabilizing S-S bridges in these different multimeric enzymes, cysteine residues predicted to form inter or intra-subunit disulfide bonds were introduced by site-directed mutagenesis. Inter-subunit S-S bonds were formed in two NAAAR variants (A68C-D72C and P60C-Y100C) and two D-NCAase variants (A302C and P295C-F304C). Intra-subunit S-S bonds were formed in two additional NAAAR variants (E149C-A182C and V265C). Crystal structures of NAAARs variants show limited deviations from the wild-type overall tertiary structure. An apo A68C-D72C subunit differs from the wild-type enzyme, in which it has an ordered lid loop, resembling ligand-bound NAAAR. The structures of A222C and A302C D-NCAases are nearly identical to the wild-type enzyme. All mutants with inter-subunit bridges had increases in thermostability. Compared with the wild-type enzyme, A68C-D72C NAAAR showed similar k(cat)/K-m ratios, whereas mutant D-NCAases demonstrated increased k(cat)/K-m ratios at high temperatures (A302C: 4.2-fold at 65 degrees C). Furthermore, molecular dynamic simulations reveal that A302C substantially sustains the fine-tuned catalytic site as temperature increases, achieving enhanced activity. (c) 2006 Elsevier Ltd. All rights reserved.