Theory and Practice of Computation

The following sections are included:

• Preface
• Program Committees
• Contents

Syntenic distance, an evolutionary distance model, is the minimum number of fusions, fissions, and translocations required to transform one genome into another. The problem of computing for the syntenic distance between two genomes has been proven to be NP-hard. Translocation syntenic distance is a special case of syntenic distance wherein operations are restricted to translocations. This restriction leads to the limitation of input instances to square instances only. As of writing, there remains no available computational complexity results for the problem of finding the minimum translocation syntenic distance between two genomes. In this paper, we focus on the translocation syntenic distance of square input instances with square connected components. A BFS-based polynomial-time algorithm for translocation syntenic distance is devised and proven effective. The algorithm runs on O(n²) time and takes up O(n²) space. A conjecture on the NP-hardness of the minimum translocation synteny problem is also presented. The idea behind the conjecture comes from the relationship between the translocation syntenic distance problem and the unsigned translocation distance problem, which was already proven to be NP-hard.

Realizability verification of reactive system specifications can detect dangerous situations that may arise that were not expected while drawing up the specifications. However, such verification typically involves complex, intricate analyses. To avoid this dificulty, progress has been made in developing bounded or approximate approaches for realizability verification. By contrast, few unbounded approaches have been studied. We anticipate the potential of unbounded approaches. While the strongest advantage of bounded approaches is that they can apply symbolic technique, which is an implementation-level (low-level) technique, we expect that by using semi-symbolic techniques, unbounded approaches can perform competitively. Moreover, algorithm-level (high-level) techniques with unbounded approaches might be applied more exibly than in bounded approaches. Therefore, we expect that unbounded approaches could verify numerous specifications eficiently. In this paper, we present several ideas about improvements for unbounded approaches, and discuss the potential of unbounded approaches.

In this article we present a quantum algorithm for finding approximate copies of a pattern within a much longer text. The algorithm is based mainly on amplitude amplification technique used in Grover’s quantum search algorithm and is more suited for instances in which the size of the alphabet is at least twice as the number of distinct symbols of the pattern. The algorithm is composed of a filtering phase for trimming the search space and a verification phase for determining solution indices in the text. We present details of each subroutine used in the algorithm. The algorithm returns all solution indices within the text with number of iterations proportional to the ratio of the size of the text and the number of distinct symbols in the pattern with high probability. Overall, the time complexity of the algorithm is mainly influenced by the size of the text.

Repeating subpatterns in DNA sequences are called motifs and finding them is important in the field of biology. There are many algorithms to solve the Planted Motif Search like PMS1, PMSPrune, and PMS5 but Planted Motif Search (PMS) is shown to be a NP-Hard problem. In this study, we modified an exact algorithm, qPMS7, to be able to design a parallel algorithm. Then, we designed a parallel algorithm based on the modified qPMS7 algorithm to speedup the finding of motifs. Using the parallelized modified algorithm, we found out that the ratio of the time complexity of the original qPMS7 algorithm to the parallelized modified qPMS7 algorithm given a binary alphabet is at most which is significantly high.

The remote procedure call (RPC) is a widely used technology for programming in distributed computation. Cooper and Wadler proposed the RPC calculus in order to model remote procedure calls. Araki and Nishizaki proposed call-by-name evaluation strategies of RPC calculus and studied correspondence between the call-by-name evaluation strategies of the RPC calculi. In this paper, we give an abstract machine semantics of call-by-name RPC calculi and study the theoretical relationship between the abstract machine semantics and the small-step structural operational semantics of the call-by-name RPC calculus. We then define an abstract machine semantics of call-by-value RPC calculus, which is simplified based on the method in the abstract machine for the call-by-name calculus.

For the past decade, there has been a high demand for low cost, high quality genome sequence of species that has led to the advancements in sequencing technologies, known as next-generation sequencing (NGS). Current sequencing techniques are marked by increase in throughput and reduction in cost and time as compared to previous sequencing methods. SOAPdenovo, an all- purpose genome assembler, has been used to successfully assemble genomes of variety of species that have been published. SOAPdenovo2, the successor of SOAPdenovo, has exceeded its predecessor greatly in terms of error correction algorithm, memory consumption on graph construction, coverage and scaffold length. Despite these notable improvements on SOAPdenovo, the time and space used in the de Bruijn graph construction still remains an issue. In this study, we describe a method that parallelizes the graph construction of the de novo assembly in SOAPdenovo2 to improve the time efficiency. In the method applied, the time complexity of two functions has been reduced from T(n) = 4n+4 to T(n) = 5 + 7m + 12, where n is the size of the hash table and m is the no. of partitions, and from T(n) = 15n + 17 to T(n) = 22 + 5m + 23, where n is the no. of kmers in a read and m is the no. of partitions.

We propose an advanced reading aid tool that targets source code using frame-works. This tool helps programmers by displaying abstraction level and code level views that automatically synchronize with each other. For example, the tool can be configured to display UML class/sequence diagram views and a code level view with debugging information, where each view shows the current execution point of the target code. One does not get lost after switching views from one to another since the tool provides properly synchronized views. The goal of this work is to show by experiments that the use of this tool increases the comprehensibility of framework-based codes. This paper reports our current research progress in the development of the tool.

Blackhole rogue access points cause critical threats to the network by replicating SSIDs of legitimate access points. Several commercial products were already made to mitigate rogue access points however these products are highly technical and involve tedious work for the network administrator for he/she is the one who decides whether an access point is rogue or not. In this paper, we propose a solution for blackhole rogue access point clients to be automatically disassociated. This paper proposes a solution for the blackhole rogue access points where the clients of the blackhole rougue access point are automatically disassociated. By sending disassociation frames to the blackhole rogue access point, its clients are disconnected from the device. However, this solution requires the blackhole rogue access point to have at least 1 client to be able to send disassociation frames to it. Also, rogue access points with spoofed MAC addresses can neither be detected nor disassociated.

Wireless sensor and actuator networks or WSAN are comprised of spatially distributed autonomous devices, enabling a number of applications through sensing and actuating of components in an environment. Wireless sensor nodes have been a popular platform, however communication is constrained due to having a half-duplex medium and low bandwidth. Despite these constraints, these networks must still be able to handle traffic from nodes in the network while providing fair throughput. Protocols such as IEEE 802.15.4 does not have any form of traffic handling while protocols like ZigBee may contain too much overhead from features which may not be needed by all networks. Since these protocols are not specifically built for WSANs but rather for wireless sensor networks, a decrease in efficiency may be observed. The study aims to create a network communication protocol with traffic handling that uses messaging for node communication for WSANs.

Due to the privacy concerns that come with health data, it is important that data stored in health information system are encrypted. Homomorphic encryption has come into attention these past years as a method for storing confidential data. It allows us to perform computation over encrypted data without the need to decrypt it. CryptDB is one tool that allows us to use homomorphic encryption in MySQL. In our work, we developed a dental information system using CryptDB and evaluated the differences in the development methods between CryptDB and regular PHP/MySQL development. We also noted the changes in the development efforts needed when using CryptDB.

We propose a system that automatically generates a resume while an agent and a user interact. This research is a prototype for automatically generating dialogue questions without preparing a dialogue pattern in advance. The agent prepares the questions for a job interview from the format of a resume and practices a job interview. The system stores the user’s information through an interview and finally creates the resume. The system provides both opportunities for practicing an interview and writing a resume.

This paper describes the building of a tourism-related parallel corpus in English-Cebuano language pair. The source for building the corpus is the web because it is rich with probable translation pairs, specifically in bilingual websites. The resulting tourism corpus will be used as a training data for a statistical machine translation system. The corpus contained information on the Philippines in the context of destinations, food, festivals, and other related concepts. From the parallel corpus, a separate named entity list on these contexts is generated. The results show that the procedures used were able to build a tourism-related parallel English-Cebuano corpus from the web and the named entities were correctly identified.

The prevalence and continuous advancement of mobile technologies give way to the utilization of mobile devices for delivering learning content to learners. Education can take advantage of the benefits being provided by mobile learning, including self-directed learning and anytime-anywhere access of courses in mobile devices. Learners can use their waiting time (e.g. watching how to tie a knot while waiting for a ride home) to engage in learning experiences that can take place in seconds up to few minutes.

This paper proposes a system that helps improve children’s pitching form in baseball to improve throwing speed. The system uses Microsoft Kinect for motion sensing, onomatopoeia to teach users the timing of a pitch, and visual and aural effects to motivate them. The effectiveness of the system was tested through an experiment involving children as subjects. We also investigated how the impressions of visual and aural effects that effectively improve users’ throwing speed by conducting an experiment using subjects.

Moodle is a web-based content management system used for distance learning. Ateneo de Davao (AdDU) introduced Moodle at the college level in 2011 and the service has been available to all units and departments since then. With over two years of activity logs and fully populated course modules, this study set out to answer the basic question of the extent of utilization of Moodle in the university.

What this study found was a wide variance in the adoption of Moodle across different units and departments. For two operational Moodle servers, at least 64% of courses were unused on the first server and at least 40% on the second server. This study presents more detailed usage profiles, such as the types of activities in course modules and the usage over time. This study also found that the most active courses on Moodle were those that made use of automated quiz assessment components.

This paper addresses the problem of gas identification from an output of a gas sensor. Gas detectors are capable of detecting presence of certain types of gases but sensors that accept multiple analytes like MQ2 do not identify them. Identification of the analyte is very important to properly handle explosive gas. Template for each analyte is generated and used for template matching. A Gaussian type noise embedded in the input is also considered. Sample templates and percentage of accuracy in using template matching are shown. Gases used in the experiment include LPG, butane, propane, methane, alcohol, hydrogen and smoke. Smoke, which is not explosive, is also considered and classified as part of other gas detected.

With the increase of urbanization in cities, there is also the rise of crime incidence. It is important for the police force to stay ahead in proactive policing. In this paper, the researcher presents a simple approach to predict crime in a geographic space using grid thematic mapping and neural networks. The study particularly focuses on the possibility of using historical crime data in predicting future crime incidents. The dataset is divided into monthly, weekly, and daily data called as a snapshot for training the model. The study area, Cebu City, is divided into a square grid of various sizes and crime incidents, from each cell in the grid of each snapshot, will then be recorded. This data is then fed into the neural network to predict possible areas where crime would happen for the next time interval. Initial results have shown that the model is accurate enough to predict crime areas when the data snapshot is divided monthly and weekly and grid size is set to a large size of about 1000 by 1000 meters and 750 by 750 meters. The best model was able to yield an F1 score of 0.95. Although the created model is simple, this can be a stepping stone to further crime modelling and prediction studies. This tool can be used to aid decisions and policy-making in the deployment of police resources throughout the city.

This study presents a music notation software, which facilitates note reading, sightsinging, and encoding for music amateurs and enthusiasts. The system can accept scanned images of music score sheets as input and renders them into a software playable music score sheets. The software renders automatically the music score sheet containing round notes into shape notes. This greatly eliminates the problem of incorrectly encoding the correct properties of individual musical notes like proper positions, duration, shapes, etc. At the same time, the time consuming tasks of encoding the musical notes is also greatly shortened.

The following section is included:

• Author Index