Time & Space Efficient String Algorithms & Data Structures with Applications to Computational Biology

a) Project aim, objectives and outline:
In the past decade, the research on stringology has been applied extensively to the area of computational biology like comparing and aligning genomic sequences. Genomic sequences including DNA sequences and RNA sequences are very long and are often searched repetitively. It is therefore natural to preprocess the sequence and construct some indexing structures to facilitate the searching process. Due to the large size of DNA sequences, ordinary indexing techniques cannot handle the sequences efficiently as the index sizes are too big to be reside in the memory. Further optimization on data structures like suffix trees and suffix arrays is required in order to handle the whole DNA sequence.
This project concerns with designing time and space efficient algorithms and data structures that help in processing data arising from biology. In particular we will focus on the following fundamental problems:
• Exact and approximate pattern matching: The problem is to search a pattern in a text. The complexity of the problem increases greatly when we allow approximate matching, i.e., a small number of errors in matching is allowed. The target is to design efficient indexing data structures to help speed up the process.
• Succint data structures and compressed indexing: Due to the massive data, space efficient data structures and compressed indexing are required so that the index can be stored in the memory for fast processing.
• External memory data structures: The memory requirement of existing data structures may not be met by laboratories with limited funding and it is important to develop data structures that allow fast retrieval of data even through external memory like harddisk.
• Applications of advanced data structures to biological problems: Genome alignment, structural alignment of RNAs, high throughput short read alignment for next generation sequencing.

b) Expected pattern of study:
The student is expected to start at Liverpool and spend the third year of the PhD study in NTHU.

c) Facilities to be used at NTHU and UoL:
The student taking this project will receive guidance from the investigators on design and analysis of algorithms and data structures. The student will also have access to the systems developed for sequence alignment and other computational biology. The student would benefit from the expertise of the supervisors:
• NTHU: indexing, data compression, external memory data structures, and combinatorial optimization.
• UoL: discrete algorithm design, string matching algorithms, advanced data structures, pattern matching, sequence alignment.