國立清華大學資訊工程學系
Department of Computer Science
National Tsing Hua University
專題演講
SEMINAR

   Title:          Efficient Alignment Free Sequence Comparison with Bounded Mismatches

   Speaker:   Prof. Sharma V. Thankachan

                    (Dept of Computer Science, University of Central Florida)

   Date:        October 03, 2017  (Tuesday)

   Time:        10:10am--11:00am

   Venue:      Delta Building Rm 617

    聯絡人：         韓永楷教授

   Abstract:

     Alignment free sequence comparison methods are attracting  

     persistent interest, driven by data-intensive applications in

     genome-wide molecular taxonomy and phylogentic reconstruction.

     Among the methods based on substring composition, the Average

     Common Substring (ACS) measure proposed by Burstein et al.

     (RECOMB 2005) admits a straightforward linear time sequence

     comparison algorithm, while yielding impressive results in multiple

     applications. An important direction of research is to extend the

     approach to permit a bounded edit/hamming distance between

     substrings, so as to reflect more accurately the evolutionary process.

     To date, however, algorithms designed to incorporate k≥1

     mismatches have O(kn^2) worst-case complexity, worse than

     the O(n^2) alignment algorithms they are meant to replace.

     On the other hand, accounting for mismatches does show to lead to

     much improved classification, while heuristics can improve practical

     performance.

     In this talk, we close the gap by presenting the first provably efficient

     algorithm for the k-mismatch average common string (ACS-k)

     problem that takes O(n) space and O(n log^{k+1} n) time in the worst

     case for any constant k. Our method extends the generalized suffix

     tree model to incorporate a carefully selected bounded set of

     perturbed suffixes, and can be applicable to other complex

     approximate sequence matching problems.