Page 88 - profile2012.indd

Research Faculty 研究人員

副研究員 助研究員
蔡懷寬 Huai-Kuang Tsai 穆信成 Shin-Cheng Mu

Associate Research Fellow Assistant Research Fellow
Ph.D., Computer Science and Information Engineering, National Taiwan University D.Phil, Computing Laboratory, University of Oxford

Tel: +886-2-2788-3799 ext. 1718 Fax: +886-2-2782-4814 Tel: +886-2-2788-3799 ext. 1730 Fax: +886-2-2782-4814
Email: hktsai@iis.sinica.edu.tw Email: scm@iis.sinica.edu.tw
http://www.iis.sinica.edu.tw/~hktsai http://www.iis.sinica.edu.tw/~scm

● Associate Research Fellow, Institute of Information Science, Aca- Science and Engineering, National Ocean University, 2009- ● 2006 - present: assistant research fellow. IIS, Academia Sinica. gramming (2011 -- 2014).
demia Sinica, 2011- ● Assistant Professor (Joint appointment), Genome and Systems Biol- ● Member of the IFIP Working Group 2.1 on Algorithmic Languag- ● 2003 - 2006: postdoc researcher, University of Tokyo.
● Assistant Research Fellow (Joint appointment), Research Center of ogy degree program, National Taiwan University, 2010- es and Calculi (January 2010 --). ● 2003: D.Phil, University of Oxford.
Information Technology Innovation, Academia Sinica, 2006- ● Associate Professor (Joint appointment), Department of Biological ● Steering Committee Member of the Workshop on Generic Pro- ● 1996: Bachelor’s degree, National Chiao-Tung University.
● Assistant Professor (Joint appointment), Department of Computer Science and Technology, National Chiao-Tung University, 2011-
Research Description Publications Research Description Publications

My research is in the eld of computational biology, main- 1. Wang, T.Y., Su, C.H. and Tsai, H.K.* (2011) MetaRank: a My interest is mainly about formal approaches to program 1. S-C. Mu, H-S. Ko, and P. Jansson. Algebra of programming

ly on the regulatory mechanisms and metagenomics. rank conversion scheme for comparative analysis of microbial construction. I have been working on functional and re- in Agda: dependent types for relational program derivation. In
Since transcription factors (TFs) play an important role in community compositions, Bioinformatics, 27, 3341-3347. lational approaches to program calculation. The general Journal of Functional Programming, Vol. 19(5), pp. 545-579.
the transcription of genes, I am particularly interested in 2. Su, C.H., Hsu, M.T., Wang, T.Y., Weng, F., Kao, C.Y., Wang, aim of the eld is to stepwise construct, in an algebraic Sep. 2009.

inferring the functions of TFs and their recognized bind- D. and Tsai, H.K.* (2011) MetaABC – an integrated Metagen- manner, from a problem speci cation to an algorithm that 2. Z. Hu, S-C. Mu and M. Takeichi, A programmable editor for

ing sites (TFBSs). I use mainly the baker’s yeast, Saccharo- omics platform for data Adjustment, Binning, and Clustering, solves the problem, and to develop concise notations that developing structured documents based on bidirectional trans-
myces cerevisiae, as the model organism. In the past years, Bioinformatics, 27, 2298-2299. aids such a development. formations. Higher-Order and Symbolic Computation, Vol
21(1-2), pp 89-118, May 2008.
we developed computational approaches to identify the 3. Swamy, B.S. K., Chu, W.Y., Wang, C.Y., Tsai, H.K.* and While the relational approach to optimisation problems,
function and binding sites of TFs. Empirical tests show that Wang, D. (2011) Evidence of association between nucleosome developed in late 90’s, was a major achievement in the 3. S-C. Mu, Z. Hu and M. Takeichi, Bidirectionalizing tree trans-
our methods are highly accurate and outperform current occupancy and the evolution of transcription factor binding eld of program calculation, its natural next step, approxi- formation languages: a case study. In JSSST Computer Soft-

sites in yeast, BMC Evolutionary Biology, 11:150.
ware (コンピュータソフトウェア) Vol. 23(2), pp. 129-141, 2006.
methods. In addition, we constructed a user-friendly inter- mation algorithms, was curiously left out. We extended
active platform (MYBS) for dynamic binding site mapping. 4. Weng, F., Su, C.-H., Hsu, M.-T., Wang, T.-Y., Tsai, H.K.* and the theories of program calculation to handle Fully Pol- 4. R. S. Bird and S-C. Mu, Countdown: a case study in origami
Based on MYBS, we further computationally investigated Wang, D. (2010) Reanalyze unassigned reads in Sanger based ynomial-Time Approximation Scheme (FPTAS), a class of programming. In Journal of Functional Programming Vol.
metagenomic data using conserved gene adjacency. BMC Bio-
15(5), pp. 679-702, 2005.
several interesting issues on gene regulation, including informatics, 11, 565. approximation algorithms having good properties.
the impact of DNA binding position variants on gene ex- 5. Su, C.H., Shih, C.H., Chang, T.H. and Tsai, H.K.* (2010) Ge- 5. Yun-Yan Chi and Shin-Cheng Mu. Constructing list homo-
th
morphisms from proofs. In the 9 Asian Symposium on Pro-
pression, the cis-regulatory modules of divergent gene nome-wide analysis of the cis-regulatory modules of divergent We have found a general theory showing that the tradi- gramming Languages and Systems (APLAS 2011).
pairs, the association between nucleosome occupancy gene pairs in yeast. Genomics, 96, 352-361. tional “thinning” algorithms can be seamlessly extended

and the evolution of TFBSs, and the identi cation of inter- 6. Swamy, B.S. K.+, Cho, C.Y.+, Chiang, S., Tsai, Z. T.Y., and to construct FPTAS. 6. Shin-Cheng Mu and Akimasa Morihata. Generalising and du-
alising the third list-homomorphism theorem. In the 16 ACM
th
actions between TFs. As to metagenomics, we proposed a Tsai, H.K.* (2009) Impact of DNA binding position variants It is known that, once we infer that two functions form a SIGPLAN International Conference on Functional Program-
series of computational methods to discriminate the dif- on yeast gene expression, Nucleic Acids Research, 37, 6991- “Galois connection”, a ubiquitous mathematical structure, ming (ICFP 2011).
ferences between distinct microbial communities and to 7001. many nice properties follow. 7. Shin-Cheng Mu and José Nuno Oliveira. Programming from
enhance the accuracy in estimating the taxonomic com- 7. Chen, C.Y., Tsai, H.K., Hsu, C.M., Chen, M.J. May, Hung, Galois connections. In the12 International Conference on
th
positions of metagenomes. We started by studying various H.G., Huang, G.T., and Li, W.H. (2008) Discovering gapped As an on-going project, we have developed theories that Relational and Algebraic Methods in Computer Science

well-known distance functions and found that using rank binding sites of yeast transcription factors, Proc Natl Acad Sci allow us to construct programs speci ed as the lower ad- (RAMiCS 12), May 30 - June 3, 2011.
normalization and considering phylogenetic information U S A, 105, 2527-2532. joint of a Galois connection. and are currently extending 8. Shin-Cheng Mu, Yu-Han Lyu, and Akimasa Morihata. Con-
yield rational clustering of metagenomic samples. We fur- 8. Tsai, H.K.*, Chou, M.Y., Shih, C. H., Huang, Grace T. W., the theory to deal with more optimisation problems. structing datatype-generic fully polynomial-time approxi-
ther developed the MetaRank scheme, a series of statisti- Chang, T. H. and Li, W.H. (2007) MYBS: A comprehensive While most of the calculations above are traditionally car- mation schemes using generalised thinning. In the 6 ACM
th
cal hypothesis tests, for comparative analysis of microbial web server for mining transcription factor binding sites in ried out by hand, I have recently shifted interest to theory SIGPLAN workshop on Generic programming (WGP 2010),

community compositions. Empirical tests con rmed that yeast, Nucleic Acids Research, 35, W221-W226. and tools of dependently typed programming and theo- pages 97-108, Sep. 2010.
MetaRank is able to reduce the e ects of sampling biases 9. Tsai, H.K., Huang, Grace T., Chou, M.Y., Lu, Henry, H.S. and rem proving. We developed a library “Algebra of Program- 9. Kazutaka Matsuda, Shin-Cheng Mu, Zhenjiang Hu, and Ma-

and clarify the characteristics of metagenomes. In addi- Li, W.H. (2006) Method for identifying transcription factor ming in Agda” that allows us to encode algebraic, relation- sato Takeichi. A grammar-based approach to invertible pro-
th
tion, we also built a single platform, MetaABC, which in- binding sites in yeast, Bioinformatics, 22, 1675-1681. al proofs into Agda, a dependently typed programming grams. In 19 European Symposium on Programming (ESOP
2010), LNCS 6012, pp 448-467, March 2010.
tegrates several binning tools coupled with methods for 10. Tsai, H.K., Lu, H.H. and Li, W.H. (2005) Statistical methods language, such that proofs can be read by people and also
removing artifacts, analyzing unassigned reads, and con- for identifying yeast cell cycle transcription factors, Proc Natl checked by machine. In an another on-going project, we 10. S-C. Mu, H-S. Ko, and P. Jansson. Algebra of programming
trolling sampling biases. Acad Sci USA, 102, 13532- 13537. are trying to provide a fully machine-checked proof of an using dependent types. In Mathematics of Program Construc-
tion 2008, LNCS 5133, pp 268-283. July 2008.
algorithm solving the “maximally dense segment” prob-
lem. While the algorithm appears relatively simple, the
proof turns out to be extremely hard.

研究人員
88 Research Faculty
89