演算法與計算理論學會

Association of Algorithm and Computation Theory

研討會訊息公告

主題
Seminar on Longest Common Subsequence
主辦單位
演算法與計算理論學會
協辦單位
國立中山大學資訊工程學系
時間
2016年11月18日(五)14:10~17:00
地點
中山大學電資大樓EC1009
流程

14:10~15:00
講題:The Longest Common Subsequence Problem
演講者:中山大學資工系楊昌彪教授 (主持人:王有禮教授)
摘要
The longest common subsequence (LCS) has been studied for several decades. It can be widely applied in many areas, such as biosequence alignment, speech recognition, file comparison, text search, and plagiarism detection. There are also several variants on the LCS problem, such as sequence inclusion or exclusion, and merged LCS. The “diff” command of Unix OS, and “Compare it” software are based on the LCS algorithms.

15:10~16:00

講題: The Gapped Longest Common Subsequence
演講者:資訊工業策進會彭永興博士 (主持人:楊昌彪教授)
摘要
The longest common subsequence (LCS) problem with gap constraints (or the gapped LCS), which has applications to genetics and molecular biology, is an interesting and useful variant to the LCS problem. In this talk, efficient algorithms based on incremental suffix maximum query (ISMQ) for finding gapped LCS will be introduced. In addition, the speaker would like to show that ISMQ can be used to improve time complexities in previous papers.

16:10~17:00

講題: Resequencing a Set of Strings Based on a Target String
演講者:臺灣科技大學資管系王有禮教授(主持人:彭永興博士)
摘要
Given a set S={S1, S2, …, Sp} of p strings, a text T, and a natural number k, find a string M, which is a concatenation of k strings (not necessarily distinct) from S, whose longest common subsequence with T is longest. Such a string is called a k-inlay. The resequencing longest common subsequence problem is to find a k-inlay for each query with parameter k after T and S are given. In this talk, we introduce an efficient algorithm for solving this problem.