Institute of Information Science, Academia Sinica

Library

Print

2018 Technical Report

Code
Subject / Author / Abstract
View

Code

TR-IIS-18-001

Subject / Author / Abstract

The Spiral Assembler: An Iterative Process of NGS De Novo Genome Assembly with Machine-Learning for Subset Selection on Quality-Score and K-Mer Landscape
Li-An Yang, Wei-Chun Chung, Yu-Jung Chang, Shu-Hwa Chen, Chung-Yen Lin and Jan-Ming Ho

In this manuscript, we study the problem of selecting a subset of NGS reads for de novo genome assembly. In an iterative process, we develop models to score importance of each read based on XGBoost. Each read is characterized by its k-mer landscape, i.e., k-mer count at each k-mer window, and base quality score at each mer. We then define a fixed-length feature vector of each read as input of XGBoost. The subset selection model is developed with its performance of de novo assembly being tested on datasets using SPAdes assembler and QUAST evaluation. We use two Illumina datasets, S. cerevisiae S288c and S. aureus MW2, denoted as D1 and D2 respectively, to test efficacy of the subset selection model. The experiments show that after each round of subset selection, corrected N50 of de novo genome assembly increases for both D1 and D2. In appendix A, we present the assembly results of GAGE-B Miseq datasets using the aforementioned pipeline. In appendix B, we analyze the process of read type tagging with Burrows-Wheeler Aligner and discuss the clip issue.

View

Fulltext

Code

TR-IIS-18-002

Subject / Author / Abstract

Building/environment Data/information System for Fine-Scale Indoor Location Specific Services
C.C. Li, H. Wang, J. W. S. Liu, C. J. Wu, E. T. H. Chu

This report describes a building/environment data and information system, called BeDIS for short. It is designed to support fine-scale, location specific services by smart devices and mobile applications for people in large smart buildings. Structured as a fog/mist, the system is scalable and responsive under overload; can function without Internet, WiFi and cell connections; and degrades gracefully when parts of it are damaged. During normal times, it enables hundreds and thousands of people to locate themselves sufficiently accurately and navigate amidst dense crowd and moving objects in the building via their mobile phones. When triggered by a disaster/emergency alert from responsible government agencies or the building safety system, BeDIS functions as a system of micro data servers for delivering location- and situation-specific emergency response instructions to people and attributes of the building, interior layout and objects in their immediate vicinities to support the choices of response actions of active devices and applications within fractions of a second to seconds. This paper describes its fog/mist structure, design and implementation.

View

Fulltext

Code

TR-IIS-18-003

Subject / Author / Abstract

Safe and shorter path planning for autonomous mobile robots by multi-objective island-based parallel genetic algorithm with dominating pool
Yau-Zen Chang, Kao-Ting Hung, and Jing-Sin Liu

This paper studies the application of evolutionary multi-objective optimization to path planning for mobile robots to move smoothly and safely along a shorter curvature-constrained path in completely known, planar static environments. The cost of travel is bi-objective: a new intrinsic cost of obstacle avoidance, which is designed as a weighted penetration depth to vertices of polygonal obstacles, and a length cost. The path is composed of a pre-specified number of control points, which are points of smooth turning, connected by three sub-paths composed of cubic spiral segments, where the intermediate configurations (locations and orientations) of these control points are design variables, subject to path smoothness constraint. We develop a Pareto-based evolutionary multi-objective optimization using island-based parallel genetic algorithm (IPGA) with nonsmoothness handling, aiming for searching smooth and shorter collision-free paths. To highlight the relative merit of IPGA in robustness to variations of environments, a comparative study on path planning performance based on simulations is conducted with two popular evolutionary multi-objective optimizers NSGA-II, SPEA-2 in terms of success rate in multiple runs and the shortest path length whenever a collision-free path can be successfully found. Results are presented for planar simulated rectangular environments composed of three distinct types of obstacles: polygons, walls as well as the combination of both. Our comparative study based on simulations shows that IPGA is more robust in all testing environments, while NSGA-II and SPEA-2 has a better distributed approximation to Pareto-front but sometimes the performance degrades greatly to be able to find a feasible path, especially in the environments containing wall-like obstacles.

View

Fulltext

Code

TR-IIS-18-004

Subject / Author / Abstract

Real-Time Hydrodynamic-based Obstacle Avoidance for Nonholonomic Mobile Robots with Curvature Constraints
Pei-Li Kuo, Chung-Hsun Wang, Han-Jung Chou and Jing-Sin Liu

The harmonic potential field of an incompressible fluid governed by Laplace equation is potential for mobile robots to generate smooth, natural-looking paths for obstacle avoidance. The streamlines generated by boundary value problem of Laplace equation have explicit or analytic vector field as the path tangent or robot heading specification without the waypoints. This paper presents an implementation of on-line obstacle avoidance system for nonholonomic curvature-constrained mobile robot regarded as a particle moving along smooth path primitives composed by streamlines. In combination with streamline path approaches, the proposed approach to generate an obstacle avoidance path satisfies nonholonomic constraint by pure pursuit algorithm. First, we use the potential flow field around a circle to derive three primitive curvature- constrained paths to avoid single obstacle. Furthermore, pure pursuit controller is implemented to achieve a smooth transition between the streamline paths in the environment with multiple obstacles. In addition to simulations, a proof of concept experiment implemented on a two-wheel driving mobile robot with range sensors validates that the proposed hydrodynamic path planning algorithm is able to on-line generate a path with a lower maximum curvature not violating curvature constraint to navigate smoothly and safely among multiple cylinder obstacles in partially unknown cluttered environments.

View

Fulltext