Drawing Borders Efficiently

A spreadsheet, especially MS Excel, is probably one of the most popular software applications for personal-computer users and gives us convenient and user-friendly tools for drawing tables. Using spreadsheets, we often wish to draw several vertical and horizontal black lines on selective gridlines to enhance the readability of our spreadsheet. Such situations we frequently encounter are formulated as the Border Drawing Problem (BDP). Given a layout of black line segments, we study how to draw it efficiently from an algorithmic view point, by using a set of border styles and investigate its complexity. (i) We first define a formal model based on MS Excel, under which the drawability and the efficiency of border styles are discussed, and then (ii) show that unfortunately the problem is -hard for the set of the Excel border styles and for any reasonable subset of the styles. Moreover, in order to provide potentially more efficient drawing, (iii) we propose a new compact set of border styles and show a necessary and sufficient condition of its drawability.     

Polynomial-time learning of elementary formal systems

An elementary formal system (EFS) is a logic program consisting of definite clauses whose arguments have patterns instead of first-order terms. We investigate EFSs for polynomial-time PAC-learnability. A definite clause of an EFS is hereditary if every pattern in the body is a subword of a pattern in the head. With this new notion, we show that H-EFS(m, k, t, r) is polynomial-time learnable, which is the class of languages definable by EFSs consisting of at mostm hereditary definite clauses with predicate symbols of arity at mostr, wherek andt bound the number of variable occurrences in the head and the number of atoms in the body, respectively. The class defined by all finite unions of EFSs in H-EFS(m, k, t, r) is also polynomial-time learnable. We also show an interesting series ofNC-learnable classes of EFSs. As hardness results, the class of regular pattern languages is shown not polynomial-time learnable unlessRP=NP. Furthermore, the related problem of deciding whether there is a common subsequence which is consistent with given positive and negative examples is shownNP-complete. Satoru Miyano, Dr. Sci.: He is a Professor in Human Genome Center at the University of Tokyo. He obtained B.S. in 1977, M.S. in 1979, and Dr. Sci. degree all in Mathematics from Kyushu University. His current interests include bioinformatics, discovery science, computational complexity, computational learning. He has been organizing Genome Informatics Workshop Series since 1996 and has served for the chair/member of the program committee of many conferences in the area of Computer Science and Bioinformatics. He is on the Editorial Board of Theoretical Computer Science and the Chief Editor of Genome Informatics Series. Ayumi Shinohara, Dr. Sci.: He is an Associate Professor in the Department of Informatics at Kyushu University. He obtained B.S. in 1988 in Mathematics, M.S. in 1990 in Information Systems, and Dr. Sci. degree in 1994 all from Kyushu University. His current interests include discovery science, bioinformatics, and pattern matching algorithms. Takeshi Shinohara, Dr. Sci.: He is a Professor in the Department of Artificial Intelligence at Kyushu Institute of Technology. He obtained his B.S. in Mathematics from Kyoto University in 1980, and his Dr. Sci. degree from Kyushu University in 1986. His research interests are in Computational/Algorithmic Learning Theory, Information Retrieval, and Approximate Retrieval of Multimedia Data.     

Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems

The submodular system k-partition problem is a problem of partitioning a given finite set V into k non-empty subsets V ₁,V ₂,…,V _k so that $\sum_{i=1}^{k}f(V_{i})$ is minimized where f is a non-negative submodular function on V. In this paper, we design an approximation algorithm for the problem with fixed k. We also analyze the approximation factor of our algorithm for the hypergraph k-cut problem, which is a problem contained by the submodular system k-partition problem.     

CD147 Is Essential for the Development of Psoriasis via the Induction of Th17 Cell Differentiation

Th17 cells play an important role in psoriasis. The differentiation of naïve CD4⁺ T cells into Th17 cells depends on glycolysis as the energy source. CD147/basigin, an integral transmembrane protein belonging to the immunoglobulin superfamily, regulates glycolysis in association with monocarboxylate transporters (MCTs)-1 and -4 in cancer cells and T cells. We examined whether CD147/basigin is involved in the pathogenesis of psoriasis in humans and psoriasis-model mice. The serum level of CD147 was increased in patients with psoriasis, and the expression of CD147 and MCT-1 was elevated in their dermal CD4⁺ RORγt⁺ T cells. In vitro, the potential of naïve CD4⁺ T cells to differentiate into Th17 cells was abrogated in CD147^−/− T cells. Imiquimod (IMQ)-induced psoriatic dermatitis was significantly milder in CD147^−/− mice and bone marrow chimeric mice lacking CD147 in the hematopoietic cells of myeloid lineage. These findings demonstrate that CD147 is essential for the development of psoriasis via the induction of Th17 cell differentiation.     

Current concept of the treatment of biliary atresia

Hepatic portoenterostomy (Kasai operation) for the patient with biliary atresia (BA) can restore the bile flow in approximately 80% of children operated on before 60 days of life [1]. However, in terms of long-term survival, according to a recent nationwide survey among the major pediatric centers in Japan, only 325 of 2013 patients had more than 10 years' survival, and only 157 patients (7.8%) remained jaundice-free with normal liver function [2]. About 20% of BA cases without jaundice are generally able to survive for long periods; and most of those patients have portal hypertension or abnormal liver function [3-5]. As the results of liver transplantation have improved, controversy has arisen over the optimal care of these children [4, 6, 7]. Some investigators have claimed that transplantation is the favored primary therapy for most patients with BA [8]. We are thus at a turning point concerning the primary therapy of BA, which makes it necessary to determine the exact indications for the Kasai portoenterostomy and the timing of liver transplantation. This paper describes our strategy for the optimal treatment of BA patients based on our 117 patients who have had various form of portoenterostomy.     

Emergence and takeover of YMDD motif mutant hepatitis B virus during long-term lamivudine therapy and re-takeover by wild type after cessation of therapy

Treatment of hepatitis B virus (HBV) with lamivudine is effective in suppressing virus replication and results in reduced inflammatory activity. However, the emergence of lamivudine-resistant mutant virus, with amino acid substitution in the YMDD motif of DNA polymerase, has been reported. We report the emergence and takeover of YMDD mutant and re-takeover by wild type during and after long-term lamivudine therapy. YMDD mutants were detected in five patients who showed DNA breakthrough (HBV DNA becoming detectable after a period of DNA negativity), which occurred after 9 to 14 months of lamivudine therapy. Four of five mutants had amino acid sequence YIDD, and the remaining mutant had YVDD. Patients with high HBV-DNA titer and/or hepatitis B e antigen tended to develop breakthrough (P = .038). Using a sensitive and specific polymerase chain reaction (PCR)-based method developed in this study, the emergence of YMDD mutants was detected 1 to 4 months before DNA breakthrough, but not detected in any of the pretreatment sera. The mutants were predominant at breakthrough, but were replaced by wild-type virus 3 to 4 months after cessation of therapy in the two patients who discontinued therapy. One of these patients had a relapse of hepatitis. Mutant continued to replicate in the remaining three patients who continued to receive treatment, and relapse occurred in only one of these patients. Our results suggest that the replication of YMDD mutant viruses is less than wild type and is re-overtaken by wild type after cessation of therapy. Re-administration of lamivudine, possibly combined with other antiviral therapy, might be useful in some patients experiencing hepatitis with lamivudine-resistant variants.     

Effect of Physical Aging on the Creep Deformation of an Epoxy Resin

This paper is concerned with an experimental study of the theinfluence of physical aging and temperature on the creep deformation ofepoxy resin. Master curves for various aging conditions were found tocollapse into a single smooth curve corresponding to a reference agingcondition after suitable horizontal translation. It is proposed that theresulting curve be designated the master-master curve and thecorresponding time scale the reduced-reduced time. In addition, theamount of horizontal translation, the aging parameter, can be used toestimate the aging process. We have also shown that there is one-to-onecorrespondence between the aging parameter and polymer density.     

Stress Intensity Controlled Kinetic Crack Growth and Stress History Dependent Life Prediction with Statistical Variability

Consistent with viscoelastic behavior, a power law form in terms of the stress intensity factor is used to specify crack kinetics (growth rate) in the central crack problem under Mode I conditions. The crack growth rate is integrated to obtain the crack size and thereby the stress intensity factor as a function of time. The crack is allowed to grow in a controlled, load dependent manner until it reaches the size at which it becomes unstable. The corresponding time at which this occurs is taken as the lifetime of the material under the specified load history. The special cases of constant load (creep rupture) and constant strain rate to failure are found to have a very simple relationship with each other. This lifetime relationship is verified through the comparison with corresponding data upon a polymeric composite. Finally the creep rupture case is generalized to a probabilistic formalism. The theoretically predicted lifetime distribution functions are verified with data, also upon a polymeric composite. Possible extension of the entire formalism to cyclic fatigue in metals is discussed. Dedicated to Professor Z.P. Bažant for his many contributions.