Title: Fast algorithms for problems in genome rearrangements

Speaker:  Mingfu Shao

时间:  2016.5.19  15:00

地点:  教研楼 3楼会议室

 Abstract:
The deluge of sequenced whole-genome data has motivated the study of comparative genomics, which provides global views on genome evolution, and also offers practical solutions in deciphering the functional roles of components of genomes. A fundamental computational problem in whole-genome comparison is to infer the most likely large-scale events (rearrangements and content-modifying events) of given genomes during their history of evolution.

In this talk, He will introduce some novel algorithms for these problems and their applications on analyzing and annotating biological datasets. He designed the exact algorithm to compute the edit distance under the DCJ (double-cut-and-join) model, the exact algorithm to compute the edit distance under a model including DCJ operations and segmental duplications, and the fast and exact algorithms for the three formulations of the breakpoint distance problems. He applied their methods to infer orthologs and in-paralogs between a pair of genomes to systematically infer functional relationships and annotate genomes. On biological whole-genome datasets, the methods run very fast, scale up to whole genomes, and also achieve very high accuracy.

Bio:

Mingfu Shao is currently a Lane Fellow at CMU under the supervision of Prof. Carl Kingsford. He obtained Ph.D. from École Polytechnique Fédérale de Lausanne (EPFL), Switzerland, under the supervision of Prof. Bernard M.E. Moret. His research focuses on algorithm design and combinatorial optimization, and particularly their applications in computational biology. He has published many papers in related conferences and journals such as BMC Bioinformatics, RECOM and JCB and so on.