Theory And Practice Of Computation - Proceedings Of Workshop On Computation: Theory And Practice Wctp2013

Proceedings of Workshop on Computation: Theory and Practice WCTP2013

Shin-ya Nishizaki, Masayuki Numao, Jaime D L Caro, Merlin Teodosia C Suarez

• Publisher: WSPC
• Year: 2014
• ISBN:
  9789814612890
• Topic: Biological Sciences
• Subtopic: Science General
• Index: Biological Sciences

This is the proceedings of the Third Workshop on Computing: Theory and Practice, WCTP 2013 devoted to theoretical and practical approaches to computation. This workshop was organized by four top universities in Japan and the Philippines: Tokyo Institute of Technology, Osaka University, University of the Philippines — Diliman, and De La Salle University. The proceedings provides a comprehensive view of the current development of fundamental research in formal method, programming language and programming development environment, bioinformatics, empathic and intelligent systems, and computing gaming in Japan and the Philippines.

This is the proceedings of the Third Workshop on Computing: Theory and Practice, WCTP 2013 devoted to theoretical and practical approaches to computation. This workshop was organized by four top universities in Japan and the Philippines: Tokyo Institute of Technology, Osaka University, University of the Philippines — Diliman, and De La Salle University. The proceedings provides a comprehensive view of the current development of fundamental research in formal method, programming language and programming development environment, bioinformatics, empathic and intelligent systems, and computing gaming in Japan and the Philippines.

Readership: Graduate students and professionals in the field of artificial intelligence, software engineering/programming and computer science.
Key Features:

• There are few books on research topics in both Japan and Philippines. Especially, if readers who wants to know the research preferences in the Philippines, this book is one of the most important material

PROBING THE HARDNESS OF THE APPROXIMATE GENE CLUSTER DISCOVERY PROBLEM (AGCDP)

G. S. CABUNDUCAN^*, J. B. CLEMENTE, H. N. ADORNA

Algorithms and Complexity Laboratory, Department of Computer Science, University of the Philippines, Diliman 1101, Quezon City, Philippines
http://aclab.dcs.upd.edu.ph/

R. T. RELATOR

Institute of Mathematics, University of the Philippines, Diliman 1101, Quezon City, Philippines

We present a polynomial-time transformation of the input for a variant of Median String Problem (MSP) that employs Hamming distance into the input for Approximate Gene Cluster Discovery Problem (AGCDP). Since MSP is NP-complete, the transformation forms the integral part of the reduction of MSP into AGCDP, for all input instances, such that AGCDP is confirmed to be NP-hard.

Keywords: Approximate Gene Cluster Discovery Problem; Median String Problem; Reduction; NP-hard.

1.Introduction

Approximate gene cluster discovery problem (AGCDP) aims to find a set of genes that are kept more or less together in a set of sequences. Genes belonging to a cluster are believed to perform similar functions or are involved in the same cellular process. AGCDP shows strong similarity to an NP-complete problem called median string problem (MSP),¹ which gives a possibility that it is NP-hard. Certain variants of MSP has been shown to be NP-complete,² and this includes the case of unbounded alphabet.³ In some research articles, MSP is also known as the consensus patterns problem in which Hamming distance is used as the distance measure. This is a more studied variant of MSP, and it is NP-complete as discussed in Fellows et al., 2006⁴ and shown in Li et al., 2002.⁵ Moreover, it also admits a polynomial time approximation scheme (PTAS).⁵ Given the different possibilities in the parameters for MSP, certain parameterized variants, e.g. a version parameterized to the number of strings a...

Table of contents

• Cover Page
• Title Page
• Copyright Page
• Contents
• Preface
• Organizing Committee
• Call-by-Name Evaluation of RPC and RMI Calculi
• Notes in Delays and Bisimulations of Spiking Neural P Systems Using SNP Algebra
• Probing the Hardness of the Approximate Gene Cluster Discovery Problem (AGCDP)
• Weak Bisimulation Between Two Biogeochemical Cycles
• A Simulation of Transition P Systems in Weighted Spiking Neural P Systems
• Robustness Analysis on Human-made Faults in Procedural Manuals
• Compositional Construction of Group-wide Meta-level Architectures
• An Application Programming Interface for the Communication and Storage Protocol for the TALA Empathic Space
• An Object-oriented Language for Parameterised Reactive System Specification based on Linear Temporal Logic
• Building Policies for Supportive Feedback in Self-Directed Learning Scenarios
• Data Collection with Prioritization for Wireless Sensor Networks
• Health Information Search Personalization with Semantic Network User Model
• Learning English Words via Animations and Making Sentences using an Etymological Memorization Method
• A Serious Game Stimulating Children’s Interest in Chemical Bonding
• Development of a Visual Debugger for C Implemented in JavaScript
• Flash Code with Dual Modes of Encoding
• Ranking Analysis of Battle Result of Board Game Strategy in Java Programming Exercise
• Distributed Inference to Support Inter-Subjective Empathic Computing
• Author Index