====================================
List of Research Projects
Leong Hon Wai, RAS-Group, SoC, NUS
====================================
Contact: leonghw at comp.nus.edu.sg
url: http://www.comp.nus.edu.sg/~leonghw/

We do both fundamental and applied research in combinatorial optimization.
The application areas are in computational biology, transportation logistics,
resource allocation and scheduling, and other optimization problems.

We look for students who are algorithmically/mathematically inclined
and who can do good software development.
We have a very strong team culture and look for students who are team players.

This list contains only *some* of the projects.  There are 
many more interesting projects of a similar nature.  
Email me (leonghw@comp.nus.edu.sg) if interested.


Title:
------
Randomized Algorithms for Problems from Computational Biology (CB)

Short Description: 
------------------
Many algorithmic/optimization problems in computation biology have 
inherent error in the input data or in the problem interpretation. 
Traditional algorithms do not handle these error naturally.

In this research, we consider the use of randomized algorithms 
for solving algorithmic problems in computational biology 
(such as [1],[2]) since randomization may be one way of dealing 
with inherent error. Initial candidate problems include 
phylogenetic tree constructions [1], motif, pattern finding 
in DNA sequences, and PPI network analysis. 

We are looking for students who are strong in design and analysis 
of algorithms, especially of randomized algorithms. 
(No prior computational biology knowledge is required.)


<b>References:</b> 

[1] Seung-Jin Sul and Tiffani L. Williams, "A Randomized Algorithm 
for Comparing Sets of Phylogenetic Trees," Asia-Pacific 
Bioinformatics Conference (APBC'07), pp. 121- 130,2007.

[2] Shuai Cheng Li, Dongbo Bu, Jinbo Xu and Ming Li
"Finding Largest Well-Predicted Subset of Protein Structure Models"
LNCS-5029, (2008), pp. 44-55, DOI: 10.1007/978-3-540-69068-9_7

Number of RS needed: 2



Title:
------
Algorithms for peptide sequencing via tandem mass spectrometry (computational biology)

Short Description:
------------------
Peptide sequencing is the problem of identification of proteins (determining 
the sequence of a protein) and recent technological advances in tandem mass 
spectrometry has made it the method of choice for high-throughput 
identification of proteins. 
(See [1], [2], [3] and others for quick introduction.) 

Recently, we initiated a project on multi-charge peptide sequencing
(MCPS) that focusses on mass spectra with multiple charge (> 2). 
We showed in [1] that significant performance gain can be achieved 
by considered multi-charge peaks during the peptide sequencing process. 

There are several possible PhD projects in this area:
 (1) One project deals with improved algorithms for de novo sequencing 
       for multi-charge mass spectra. 
 (2) Another project deals with more precise peak annotation in 
       multi-charged mass spectra.
 (3) Another project deals with the important problem of detection of post 
       translation modifications (PTMs). This problem has important implications
       in the study of translational medicine. A collaborative project with an 
       overseas partner is currently being pursued for this project. 

We are looking for students who are strong in design of algorithms and mathematical
analysis. Currently, two PhD students are working in this area in my research group.

This is joint research with Prof. Pevzner at UCSD and Prof Haixu Tang at 
Indiana University. 

References:

[1] KetFah Chong, Kang Ning and Hon Wai Leong, "Characterization of Multi Charge Mass
    Spectra for Peptide Sequencing", APBC-2006, (2006), pp. 109-119.
[2] Vineet Bafna, Nathan Edwards: "On de novo interpretation of tandem mass spectra 
    for peptide identification.", RECOMB 2003: 9-18 
[3] Ari Frank and P.A. Pevzner, "De Novo Peptide Sequencing via Probabilistic 
    Network Modelling." Anal. Chem., 77, pp. 964-973, 2005. 

Number of RS needed: 2



Title:
------
Research and Development in PGO (Phylogeny from Gene Orders)

Short Description:
------------------
Phylogeny from Gene Orders (PGO) [1] is a software system for constructing
and comparing phylogenetic trees build using different techniques and 
using different evolutionary distances on the same set of gene orders (genomes).
Our PGO system allows researchers to compare different classes of 
algorithms for building phylogenetic trees. It also allows researchers 
to compare the phylogenetic trees build from different evolutionary distances. P
GO integrates a number of software packages related to phylogenetic 
reconstruction from gene order and gene content of genomes.

Our system can be access as a web service where users can upload their 
gene order data and select the set of programs they wish to run on their data. 
A similar web service that analyzes DNA sequences (instead of gene orders) 
is given in [2].

In this project, we perform R&D on enhancements to PGO. Some possible 
enhancements includes implementation and integration of more distance functions, 
performing comparative study of different distance functions, evaluating 
the practicality of DCR operations as a proxy to actual evolutionary distances, 
and design and implementation of algorithms for new distance measures.

We are looking for students who are strong in algorithm design and implementation. 
(No prior computational biology knowledge is required.) 

<b>References:</b>

[1] M. Zhang, F. Hao, and H. W. Leong. Phylogeny from Gene Order (PGO): 
an integrated system for comparing phylogenetic reconstruction algorithms, 
International Conference on Genome Informatics, Dec 2010.

[2]  A. Dereeper, V. Guignon, G. Blanc, S. Audic, S. Buffet, F. Chevenet, 
J. Dufayard, S. Guindon, V. Lefort, M. Lescot, et al. 
"Phylogeny. fr: robust phylogenetic analysis for the non-specialist." 
Nucleic Acids Research, 2008.

Number of RS needed: 1



Title:
------
Algorithms for the Genome Sorting Problem

Short Description:
------------------
In genome sorting, we are given two genomes (given by their gene sequences 
or gene order), and we want to find the minimum sequence of operations 
that transform one genome to the other. Different variations ([1], [2]) 
of the genome sorting problem arise from the different sets of evolutionary 
operations allowed: including insertion, deletion, reversals, translocation, 
transposition, block interchange, fusion, fission, segmental duplication, 
chromosome duplication and chromosome deletion. 

An ongoing project, GSB (Genome Sorting with Bridges) considers the 
genome sorting problem in which we allow all known traditional operations 
(see list given above). By making no assumptions on the two genomes and 
allowing all known traditional operations, we hope to make it more convenient 
to compute evolutionary distances and we also hope that the evolutionary 
distances computed are closer to the real distances. We have devised a new
algorithm called GSB (Genome Sorting with Bridges) that combines existing 
techniques with new innovative ideas called T-bridges and X-bridges. 

This project will continue this work and will continue implementation 
of the GSB algorithm and related extensions.

We are looking for students who are strong in algorithm design and 
implementation. (No prior computational biology knowledge is required.) 

<b>References:</b>

[1] M. Bader. Genome rearrangements with duplications. BMC Bioinformatics, 
    11(Suppl 1):S27, 2010.

[2] F. Hao, J. Luan, and D. Zhu. Translocation-Deletions Distance Formula 
    for Sorting Genomes. WRI World Congress on Computer Science and 
    Information Engineering, 2009

Number of RS needed: 1




Title:
------
Fragment Assembly using very short fragments (Computational Biology)

Short Description:
------------------
Fragment assembly is an important genome sequencing problem in computational 
biology. A highly successful approach to fragment assembly is recently 
proposed by Pevzner et al in [1] and [2]. 

This project deals with consider fragment assembly using very short fragments 
(about 100bp each) produced by new fragment generation technology. For these 
short fragments, frequent repeats in DNA sequences causes problems in the assembly.
In this project, we aim to seek efficient solution to this problem.

We are looking for students who are strong in design of algorithms and 
mathematical analysis. Currently, two students are working in related area 
in my research group.

This project is a joint project with Prof Haixu Tang in Indiana University.

References:
[1] Pevzner PA, Tang H, Waterman MS., "An Eulerian path approach to DNA 
fragment assembly." Proc Natl Acad Sci, USA 2001 Aug 14;98(17):9748-53. 
[2] Pevzner PA, Tang H, "Fragment Assembly with Double-barreled Data," 
BioInformatics, Vol 17, Supp 1, (2001), pp. S225-S233. 

Number of RS needed: 1



Title:
------
Rearrangements in genomes with unequal content (computational biology)

Short Description:
------------------
Whole-genome rearrangement studies are typically separated into two steps:
(i) identification of large blocks of sequence shared by the set of genomes; 
and (ii) comparison of the respective arrangements of these blocks.

When studying many very different genomes simultanously, it becomes 
difficult to identify large blocks in step (i) simply because there are 
limited number of elements common to all genomes. In other words, many 
of the similarities that are identified by pairwise comparisons are 
dropped in step (i) when we restrict to elements common to all genomes.

In the past, we have worked on an algorithm to compare the respective 
arrangements of blocks in multiple genomes (the program is called MGR, 
Bourque and Pevzner 2002). The algorithm is a heursitic that seeks the 
most parsimonious rearrangement scenario that best explains the observed 
arrangements. MGR relies on a polynomial time algorithm to compute the 
pairwise distance between 2 multichromosomal genomes (Pevzner and 
Hannenhalli 1995, Tesler 2002).

Instead of working on a set of blocks common to all genomes, we would 
like to adapt the algorithm to work on the different sets of pairwise 
blocks. Given that MGR already only relies on pairwise comparisons to 
identify rearrangements implies that this modification is very accessible. 
The main challenge is to describe how these pairwise blocks are modified
by the rearrangements and how to deal with boundary ambiguities since 
a rearrangement is defined for different sets of blocks on the same 
genome. One approach would be to add virtual markers to account for 
missing markers in some of the genomes.

Not restricting to common blocks will retain much more information 
and we expect the recovered scenarios to be more accurate. It will 
also open new applications to include more genomes, distant genomes 
and genomes with low quality map or sequence. These developments 
would be useful not only in conjunction with MGR but also for any 
other multiple genome rearrangement study.

Number of RS needed: 1



Title:
------
Algorithms for Phylogenetic Tree Reconstructions (in Computational Biology)

Short Description:
------------------
A phylogenetic tree (or evolutionary tree) is a tree
representation of the evolutionary history of a set of species. 
Over the past decade, there has been intensive reesarch in algorithms
for reconstructing phylogenetic tree. A number of different techniques
have been used.

In this project, we aim to design efficient algorithms for phylogenetic tree 
reconstruction. The project starts with an up-to-date survey of existing
techniques for phylogenetic tree reconstruction and a comparative study of
their relative strengths and weaknesses. 

Number of RS: 1


For other related research topics in computational biology, please come
by to see me in S16 06-01.

(For more projects, see http://www.comp.nus.edu.sg/~leonghw, 
   ---> under Research Project)




Title:
------
Efficient Algorithms for Berth Allocation Planning Problems 

Short Description:
------------------
The complex operations involved in the management and operation
of a world-class container transshipment port in Singapore are
complex and involves many different resources and systems.
In this project, we undertake to study the problem of planning
of some of these operations to improve their effectiveness.

Initial study with the berth allocation planning system (BAPS)
has produced interesting research problems and results.
Some examples of these are the berth partitioning problem,
the berth assignment problems. 
This project aims to extend the current BAPS research with
the study of more efficient algorithms for solving these and
other related optimization problems in container port operation.

Number of RS: 1



Title:
------
Multi-Agent Approach to Combinatorial Optimization (2 students)

Short Description:
------------------
The majority of past approaches to combinatorial optimization 
use a centralized decision making framework where the algorithm
is aware of all relevant problem parameters.

In this project, we study the an interesting new approach
to combinatorial optimization -- the multi-agent approach
in which a distributed decision making framework is employed.
Such a distributed framework is more flexible and is able to
incorporate new changes and new constraints in the dynamic business
environment of today. 

In our multi-agent approach, we model the entities in the problem
using software agents, each of which has only a restricted 
picture of the entire state of the system. 
Thus, the agents cooperate as well as compete for scarce resources
while optimizing some global objective functions. The multi-agent
approach has been successfully applied to two logistics problems --
the vehicle routing problem and the inventory routing problem.

In this project, we develop a multi-agent algorithm for solving
a scheduling problem that involves multiple entities and scarce, shared
resources. The challenge will be to appropriate model the various
entities using appropriate agents with associated properties, believes
and operations. We then explore issues such as the influence of local
information, and the appropriate distributed decision making framework.
This project will also involve the implementation of the multi-agent 
approach and benchmarking against the state-of-the-art approaches.

Two starting reference: 
   Yizhi Lao, and Hon Wai Leong, "A Multi-Agent Based Approach
     to the Inventory Routing Problem", Pacific-Rim Intl. Conf. on 
     Artificial Intelligence (PRICAI-02), (2002), LNAI-2417, pp 345-354.

   Hon Wai Leong and Ming Liu, "A Multi-Agent Algorithm for 
     Vehicle Routing Problem with Time Windows", ACM Symposium on 
     Applied Computing (SAC-2006), AIMS Track, (2006), pp. 106-111.
 
Number of RS: 1

For other related research topics in logistics, please come
by to see me in S16 06-01.

(For more projects, see http://www.comp.nus.edu.sg/~leonghw, 
   ---> under Research Project)




Research Scholars Currently Supervised:
---------------------------------------

Ng Hoong Kee,   PhD (Jan 2000 -- )  email: nghoong
   Topic: Multi-Point Range Query: Algorithms and Applications 

Chong Ket Fah,  PhD (Jan 2002 -- )  email: chongket
   Topic: Computational Proteomics

Ning Kang,  PhD (Jul 2002 -- )  email: ningkang
   Topic: Computational Proteomics, SCS related problems


Recently Graduated Students:
----------------------------

Tan Jing Song, MSc  (Jul 2002 -- Jul 2003)  (now doing PhD at U-Penn)
   Topic: Efficient Algorithms for Dynamic Route Advisory Problems

Li Shuai Cheng, MSc (July 2001 -- Jul 2002) (now doing PhD at Waterloo)
   Topic: Efficient Algoritms for the Berth Assignment Problem

Lao Yizhi, MSc (July 2000 -- July 2001)
   Topic: A Multi-Agent Based Approach to the Inventory Routing Problem.

Ong Tat Wee, MSc  (2000)
   Topic: A Graph Partitioning Algorithm for the Berth Allocation Problem