PhD Research Project

My Shortlist0

This project is no longer listed in the FindAPhD database
and may not be available.

Click here to view other PhD studentship opportunities at University of Liverpool.

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

Institution:

University of Liverpool

Dept/School/Faculty:

Faculty of Science and Engineering

PhD Supervisor:

Dr WK Hon

Co-Supervisor:

Dr P Wong

Application Deadline:

Applications accepted all year round

Funding Availability:

Funded PhD Project (Students Worldwide)

PhD Research Project

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.

Funding Notes:

This project is a part of a 4-year dual PhD programme between National Tsing Hua University (NTHU) in Taiwan and the University of Liverpool in England. Students can start in either institution, after passing a ‘qualifying examination’ and must spend at least 12 months in each institution. When away from the ‘home’ institution they will receive a stipend of 10,000 TWD. There are no tuition fees for students starting at UoL and for students starting at NTHU no tuition fees will be charged while in Liverpool. Applications can be made on-line to either institution mentioning the dual PhD programme.