Francis Y.L. Chin

B.A.Sc.(Toronto); M.Sc., M.A., Ph.D.(Princeton); FIEEE, FHKIE, FHKACE (Hon.)

Chair of Computer Science; Taikoo Professor of Engineering; Associate Dean of Engineering

Email: chin@cs.hku.hk
Office: CB301A, Chow Yei Ching Building, The University of Hong Kong, Pokfulam Road, Hong Kong
Telephone: (+852) 2859 2178
Fax: (+852) 2858 4141

Keynote and Invited Talks (since 2008):

"Online Frequency Assignment Problem in Cellular Network Communication", Keynote, the 25th Workshop on Combinatorial Mathematics and Computation Theory, Taipei, Taiwan (April 2008)
"A Clustering-Based Approach for Finding Motif Pairs from Protein Interaction Data", Keynote, the 2008 International Conference on BioMedical Engineering and Informatics (BMEI 2008), Sanya, Hainan, China (May 2008)
"Online Tree Node Assignment Problem", Keynote, the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA'08), St. John's, Newfoundland, Canada (August 2008)
"Finding Common Patterns in DNA Sequences", Keynote, The International Symposium on Education and Computer Science(ECS2009), Wuhan, China (March 2009)
"Conserved Patterns in Bioinformatics", Plenary talk, Joint Workshop of Beijing, Hong Kong and Kyoto on Computational Mathematics, Computer and Systems Sciences (CMCSS), Kyoto, Japan (March 2009)
"Online Frequency Assignment Problem in Cellular Network Communication", Keynote, The International Conference on Networks Security, Wireless Communications and Trusted Computing (NSWCTC 2009), Wuhan, China (April 2009)
"Finding Conserved Patterns in Bioinformatics". The 2nd Mainland and HK Workshop on Bioinformatics, Xi Shuang Ban Na, China (March 22, 2010)
"Meta-IDBA: A denovo Assembler for Metagenomic Data", Metagenomics/informatics Workshop entitled “Ten Thousand Genomes at a Time: Metagenome Assembly and Beyond” DOE-JGI Walnut Creek, CA, (October 2011).

Publications (since 2008):

Book Chapter

Francis Y. L. Chin, Siu-Ming Yiu: "Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds", Encyclopedia of Algorithms, 2008

Refereed Journal Papers

Stanley Fung, Feifeng Zheng, W.T. Chan, Francis Y.L. Chin, C.K.Poon and Prudence W.H. Wong, "Improved on-line broadcast scheduling with deadlines", Journal of Scheduling 11(4): 299-308 (2008) - preliminary version appeared in COCOON'06
Henry Leung and Francis Chin, "DNA Motif Representation with Nucleotide Dependency," IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(1): 110-119 (January-March 2008) - preliminary version appeared in BIBE06
Wun-Tat Chan, Francis Y. L. Chin, Deshi Ye, Guochuan Zhang, Yong Zhang, "On-Line Scheduling of Parallel Jobs on Two Machines", Journal of Discrete Algorithms, 6(1): 3-10 (March 2008) - preliminary version appeared in AWOCA 2005
Francis Y.L. Chin, Henry C.M. Leung, Wei-Lin Li and Siu-Ming Yiu, "Finding Optimal Threshold for Correction Error Reads in DNA Assembling", BMC Bioinformatics 2009, 10(Suppl 1): S15 (January 2009) - also presented at APBC2009
Henry C.M. Leung, Qian Xiang, S.M. Yiu and Francis Y.L. Chin, "Predicting Protein Complexes from PPI Data: A Core-Attachment Approach", Journal of Computational Biology, 16(2): 133-144, 2009 - preliminary version also presented in RECOMB Satellite Conference on Systems Biology and DREAM, MIT (October-November 2008)
Yong Zhang, Francis Chin and Hong Zhu, "A 1-local 13/9-competitive Algorithm for Multicoloring Hexagonal Graphs", Algorithmica 54: 557–567 (August 2009) - preliminary version appeared in the COCOON'07
Mee Yee Chan, Wun-Tat Chan, Francis Y.L.Chin, Stanley P.Y.Fung, and Ming-Yang Kao, "Linear-time Haplotype Inference on Pedigrees without Recombinations and Mating Loops" SIAM Journal of Computing, 38(6): 2179-2197 (2009) - preliminary version appeared in WABI2006
Francis Chin, Hing Fung Ting and Yong Zhang, "A Constant-Competitive Algorithm for Online OVSF Code Assignment", Algorithmica, 56(1): 89-104 (January 2010) - preliminary version appeared in ISAAC 2007
Bin Yang, Yu Peng, Henry C.M. Leung, S.M. Yiu, J.C. Chen and Francis Y.L. Chin, "Unsupervised Binning of Environmental Genomic Fragments based on an Error Robust Selection of l-mers", BMC Bioinformatics 2010, 11(Suppl 2):S5 - also presented in DTMBIO 09
Francis Y. L. Chin, Hingfung Ting, Yong Zhang, "One-Space Bounded Algorithms for Two-Dimensional Bin Packing", International Journal of Foundations of Computer Science, 21(6): 875-891 (December 2010) - preliminary version appeared in ISAAC 2009
Keqiu Li, Takashi Nanya, Hong Shen, Francis Y. L. Chin and Weishi Zhang, " An Efficient Cache Replacement Algorithm for Multimedia Object Caching", International Journal of Computer Systems Science and Engineering
Yongkai Liu, Defu Zhang and Francis Y.L. Chin, "A Clique-based Algorithm for Constructing Feasible Timetables", Optimization Methods and Software, 1029-4937 (electronic) 1055-6788 (paper), 2010
Francis Y. L. Chin, Zeyu Guo and He Sun, "Minimum Manhattan Network is NP-Complete", Discrete and Computational Geometry (2011) 45:701-722- preliminary version appeared in ACM SoCG 2009
Henry C.M. Leung, S.M. Yiu, Bin Yang, Yu Peng, Yi Wang, Zhihua Liu, Jingchi Chen, Junjie Qin, Ruiqiang Li, Francis Y.L. Chin, "A Robust and Accurate Binning Algorithm for Metagenomic Sequences with Arbitrary Species Abundance Ratio," Bioinformatics, 27(11):1489-95, Jun 2011. also presented in HiTSeq 2011.
Yu Peng, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin, "Meta-IDBA: "A de Novo Assembler for Metagenomic Data," Bioinformatics, 27(13):i94-101, July 2011, also presented in ISMB/ECCB 2011
Yong Zhang, Zhuo Chang, Francis Y.L. Chin, Hing-Fung Ting and Yung H. Tsin, "Online Uniformly Inserting Points on Grid", Information Processing Letters. 111(2011):773-779 - preliminary version appeared in AAIM 2010
Yong Zhang, Francis Y.L. Chin, Hing-Fung Ting, Joseph Wun-Tat Chan, Xin Han, Ka-Cheong Lam, "Online Call Control in Cellular Networks Revisited", Information Processing Letters. 112(2012):21-25 - preliminary version appeared in FAW 2010
Henry C.M. Leung, S.M. Yiu, Bin Yang, Yu Peng, Yi Wang, Zhihua Liu, Jingchi Chen, Junjie Qin, Ruiqiang Li, Francis Y.L. Chin, "A Robust and Accurate Binning Algorithm for Metagenomic Sequences with Arbitrary Species Abundance Ratio," Bioinformatics, 27(11):1489-95, Jun 2011, also presented in HiTSeq 2011.
Yu Peng, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin, "Meta-IDBA: A de Novo Assembler for Metagenomic Data,"Bioinformatics, 27(13):i94-101, July 2011, also presented in ISMB/ECCB 2011
Xin Han, Francis Y. L. Chin, Hing-Fung Ting, Guochuan Zhang, Yong Zhang, "A new upper bound 2.5545 on 2D Online Bin Packing". ACM Transactions on Algorithms 7(4): 50 (2011)
Francis Chin, Henry C.M. Leung and S.M. Yiu. "Non-Adaptive Complex Group Testing with Multiple Positive Sets", Theoretical Computer Science, - preliminary version appeared in TAMC 2011 (to appear)
Yi Wang, Henry C.M. Leung, S.M. Yiu, Francis Y.L. Chin, "MetaCluster 4.0: A Novel Binning Algorithm for NGS Reads and Huge Number of Species" Journal of Computational Biology 19(2): 241-249, also presented in RECOMB Regulatory Genomics 2011
Yong Zhang, Francis Y.L. Chin, Hing-Fung Ting, "Competitive Algorithms for Online Pricing", Discrete Mathematics, Algorithms and Applications (DMAA),4(2): (2012)- preliminary version appeared in COCOON 2011 (to appear)
Yong Zhang, Francis Chin, Hingfung Ting, Xin Han and Zhuo Chang, "Online Algorithm for 1-Space Bounded Multi-Dimensional Bin Packing," Journal of Combinatorial Optimization -preliminary version appeared in FAW and AAIM 2011 (to appear)
Yu Peng, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin,"IDBA-UD: A de Novo Assembler for Single-Cell and Metagenomic Sequencing Data with Highly Uneven Depth," Bioinformatics 28(11): 1420-1428, May 2012, also presented in HiTSeq 2012
Yi Wang, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin, "MetaCluster 5.0: A two-round Binning Approach for Metagenomic Data for Low-abundance Species in a Noisy Sample," Bioinformatics, 28(18): i356-i362, Sept 2012, also presented in ECCB 2012
Yu Peng, Henry C.M. Leung, S.M. Yiu, Xin-Guang Zhu, Ming-Zhu Lv and Francis Y.L. Chin, "IDBA-Tran: A More Robust de novo de Bruijn Graph Assembler for Transcriptomes with Uneven Expression Levels", to appear in Bioinformatics, also presented in ISMB/ECCB 2013
Yong Zhang, Francis Y.L. Chin, Hing-Fung Ting, "Constant-Competitive Tree Node Assignment", to apear in Theoretical Computer Science

Refereed Conference Papers

Francis Y.L. Chin, Henry C.M. Leung, M.H. Siu and S.M. Yiu, "Optimal Algorithm for Finding DNA Motifs with Nucleotide Adjacent Dependency," The 6th Asia-Pacific Bioinformatics Conference (APBC2008), Kyoto, Japan, 343-352 (January 2008)

Wun-Tat Chan, Francis Y. L. Chin, Xiangyu Hong and HingFung Ting, "Dynamic Offline Conflict-Free Coloring for Unit Disks", The 6th Workshop on Approximation and Online Algorithms (WAOA 2008), Universitat Karlsruhe, Germany, (September 2008)

Henry C.M. Leung, Qian Xiang, S.M. Yiu and Francis Y.L. Chin, "Predicting Protein Complexes from PPI Data: A Core-Attachment Approach", The Annual RECOMB Satellite Conference on Regulatory Genomics, Systems Biology and DREAM (Recomb-Sat/DREAM 08), MIT, Boston, USA (October-November 2008) - final version appears in Journal of Computational Biology 2009

Francis Y.L. Chin, Henry C.M. Leung, Wei-Lin Li and Siu-Ming Yiu, "Finding Optimal Threshold for Correction Error Reads in DNA Assembling", The 7th Asia-Pacific Bioinformatics Conference (APBC2009), Beijing, China, 153-161 (January 2009) - final version appears in BMC Bioinformatics 2009

Francis Y. L. Chin, Hingfung Ting, Yong Zhang, "1-Space Bounded Algorithms for 2-Dimensional Bin Packing", The 2nd Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2009), Hangzhou, China (April 1009)

Francis Y. L. Chin, Zeyu Guo and He Sun, "Minimum Manhattan Network is NP-Complete", The 25th Annual ACM Symposium on Computational Geometry (SoCG 2009), 393-402, Denmark (June 2009) - final version appears in Discrete and Computational Geometry

Francis Y.L. Chin, Hing-Fung Ting, and Yong Zhang, "Variable-size Rectangle Covering", The 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA'09), Huangshan, China, 145-154 (June 2009)

Li Yan, Marek Chrobak and Francis Chin. "Algorithms for the Flow Monitors Problem (Extended Abstract)", The 5th International Conference on Algorithmic Aspects in Information and Management (AAIM 2009), San Francisco, USA (June 2009)

Joseph Wun-Tat Chan, Francis Y.L. Chin, Hing-Fung Ting, and Yong Zhang, "Online Tree Node Assignment with Resource Augmentation", The 15th International Computing and Combinatorics Conference (COCOON'2009), Niagara Falls, New York, U.S.A., 358-367 (July 2009)

Henry C.M. Leung, S.Y. Leung, S. M. Yiu, Francis Y. L. Chin, "Predicting Conserved Metabolic Pathways Leading to an Important Final Product", The 8th Annual International Conference on Computational Systems Bioinformatics Conference (CSB2009) (poster), Stanford University, USA (August 2009)

Yu Peng, Henry C.M. Leung, S.M. Yiu, Francis Y.L. Chin and Ruiqiang Li, "Assembling Short Reads with Much Less Memory", The 11th International Meeting on Human Genome Variation and Complex Genome Analysis (HGV2009), Tallinn, Estonia (September 2009)

Bin Yang, Yu Peng, Henry C.M. Leung, S.M. Yiu, J.C. Chen and Francis Y.L. Chin, "Unsupervised Binning of Environmental Genomic Fragments based on an Error Robust Selection of l-mers",The 3rd International Workshop on Data and Text Mining in Bioinformatics (DTMBIO 09) in the 18th ACM Conference on Information and Knowledge Management, Hong Kong (November 2009) - complete version appears in BMC Bioinformatics 2010

Francis Y. L. Chin, Hingfung Ting, Yong Zhang, "1-Bounded Space Algorithms for 2-Dimensional Bin Packing", The 20th International Symposium on Algorithms and Computation (ISAAC 2009), Hawaii, USA, 321-330 (December 2009) - complete version appears in International Journal of Foundations of Computer Science 2010

Yong Zhang, Francis Y.L. Chin and Hing-Fung Ting, "Approximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs", The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam (July 2010)

Joseph Wun-Tat Chan, Francis Y.L. Chin, Xin Han, Ka-Cheong Lam, Hing-Fung Ting, and Yong Zhang, "Deterministic Online Call Control in Cellular Networks and Triangle-Free Cellular Networks" The Fourth International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China (August 2010)

Bin Yang, Yu Peng, Henry C.M. Leung, S.M. Yiu, Junjie Qin, Ruiqiang Li and Francis Y.L. Chin, "MetaCluster: Unsupervised Binning of Environmental Genomic Fragments and Taxonomic Annotation", The ACM International Conference on Bioinformatics and Computational Biology (ACM-BCB 2010), Niagra Falls, New York, USA, 358-367 (August 2010)

Yu Peng, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin, "IDBA - A Practical Iterative de Bruijn Graph De Novo Assembler", The Fourteenth Annual International Conference on Research in Computational Molecular Biology (RECOMB 2010), Lisbon, Portugal (August 2010)

S.Y. Leung, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin, "Predicting Metabolic Pathways from Metabolic Networks with Limited Biological Knowledge", International Workshop on Graph Theoretic Analysis of Biological Networks, IEEE International Conference on Bioinformatics & Biomedicine (BIBM 2010), Hong Kong (December 2010)

Yong Zhang, Jingchi Chen, Francis Y.L. Chin, Xin Han, Hing-Fung Ting, and Yung H. Tsin, "Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing", The 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju Island, Korea (December 2010)

Henry C.M. Leung, S.Y. Leung, Carlos Xiang, S.M. Yiu and Francis Y.L. Chin, "DMPFinder - Finding Differentiating Pathways with Gaps from Two Groups of Metabolic Networks", The 3rd International Conference on Bioinformatics and Computational Biology (BICoB), New Orleans USA (March 2011)

Yu Peng, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin, "T-IDBA: A de novo Iterative de Bruijn Graph Assembler for Transcriptome", The 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2011), Vancouver (March 2011)

Francis Chin, Henry C.M. Leung and S.M. Yiu. "Non-Adaptive Complex Group Testing with Multiple Positive Sets", The 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Tokyo Japan (May 2011), to appear in Theoretical Computer Science

Yong Zhang, Francis Chin, Hingfung Ting, Xin Han and Zhuo Chang, "Online Algorithm for 1-Space Bounded Multi-Dimensional Bin Packing," The Joint Conference of FAW and AAIM 2011, Jinhua China (May 2011), to appear in Journal of Combinatorial Optimization.

Henry C.M. Leung, S.M. Yiu, Bin Yang, Yu Peng, Yi Wang, Zhihua Liu, Jingchi Chen, Junjie Qin, Ruiqiang Li, Francis Y.L. Chin, "A Robust and Accurate Binning Algorithm for Metagenomic Sequences with Arbitrary Species Abundance Ratio," HiTSeq: Conference on High Throughput Sequencing Analysis and Algorithms, Vienna, July 2011, appeared in Bioinformatics, 27(11):1489-95, Jun 2011.

Yong Zhang, Francis Y.L. Chin, Hing-Fung Ting, "Competitive Algorithms for Online Pricing", The 17th Annual International Computing and Combinatorics Conference (COCOON 2011), Dallas, Texas, 391-401 (August 2011), to appear in Discrete Mathematics, Algorithms and Applications (DMAA)

Yu Peng, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin, "Meta-IDBA: "A de Novo Assembler for Metagenomic Data," The 19th Annual International Conference on Intelligent Systems for Molecular Biology and 10th European Conference on Computational Biology (ISMB/ECCB 2011), Vienna, July 2011, appeared in Bioinformatics, 27(13):i94-101, July 2011

Francis Y.L. Chin, Henry C.M. Leung and Siu-Ming Yiu, "Adaptive Phenotype Testing for AND/OR Items", The 22th International Symposium on Algorithms and Computation (ISAAC 2011), Yokohama, Japan, 754-763 (December 2011)

Junjie Yu, Henry C.M. Leung1, S. M. Yiu, Yong Zhang, Francis Y.L. Chin, Nathan Hobbs, and Amy Y.X. Wang, "Phylogenetic Tree Reconstruction with Protein Linkage" International Symposium on Bioinformatics Research and Applications (ISBRA), Dallas, USA, LNBI 7292, pp. 315--327. May 2012

Yong Zhang, Francis Y.L. Chin, and Hing-Fung Ting, "Online Pricing for Multi Type of Items," Proceedings of the Joint Conference of FAW and AAIM 2012, Beijing China, 82-92 (May 2012

Yu Peng, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin,"IDBA-UD: A de Novo Assembler for Single-Cell and Metagenomic Sequencing Data with Highly Uneven Depth," HiTSeq 2012 (to appear), also appeared Bioinformatics 28(11): 1420-1428, May 2012

S.M. Yiu and Francis Y.L. Chin, "Algorithms for constructing k‐articulated network: a more powerful classification of phylogenetic networks", First RECOMB Satellite Conference Open Problem in Algorithmic Biology (RECOMB-AB), Petersburgh, Russia, August 2012 (to appear).

Francis Chin and S. M. Yiu, "Phylogenetic tree reconstruction with protein linkage", First RECOMB Satellite Conference Open Problem in Algorithmic Biology (RECOMB-AB), Petersburgh, Russia, August 2012 (to appear).

Yi Wang, Henry C.M. Leung, S.M. Yiu and Francis Y.L. Chin, "MetaCluster 5.0: A two-round Binning Approach for Metagenomic Data for Low-abundance Species in a Noisy Sample," ECCB 2012, Bali, Switzerland, also appeared in Bioinformatics, 28(18): i356-i362, Sept 2012.

Yu Peng, Henry C.M. Leung, S.M. Yiu, Xin-Guang Zhu, Ming-Zhu Lv and Francis Y.L. Chin, "IDBA-Tran: A More Robust de novo de Bruijn Graph Assembler for Transcriptomes with Uneven Expression Levels", The 21th Annual International Conference on Intelligent Systems for Molecular Biology and 12th European Conference on Computational Biology (ISMB/ECCB 2013), Berlin, July 2013, appeared appeared in Bioinformatics.

[See older publications]

Research Grants:

"Multiresolution Polygonal/Subdivision Approximation," HKU 541/96E, HK$416,000 (1997-1999)
"Line Estimator/Stabbing Problem", HKU 7024/98E, HK$380,000 (1998-2001)
"Tetrahedralization of Convex Polyhedron", HKU 7019/00E, HK$635,817 (2000-2003)
"On-line Scheduling with Partial Job Values" (HKU 7142/03E) HK$377,149 (2003-2005)
"Finding Motifs for Sequences with Weak Binding Sites" (HKU 7135/04E) HK$ 339,414 (2004-2006)
"Computationally Haplotyping Pedigree Data" (HKU 7119/05E) HK$ 359,224 (2005-2007)
"A New Motif Representation Based on Position Specific Patterns" (HKU 7120/06E) HK$ 775,008 (2006-2009)
"Design and Analysis of Online Algorithms for Frequency/Code Assignment Problems in Cellular Networks" (HKU 7113/07E) HK$ $418,000 (2007-2009)
"Finding Conserved Patterns in Biological Networks" (HKU 7116/08E) HK$777,108 (2008-2012)
"Combinatorial Phenotype Testing" (HKU 7117/09E) HK$394,053 (2009-2012)
"Next-Generation Sequencing Algorithms" (HKU 7111/12E) HK$905,425 (2012-2015)

Hong Kong Industrial Support Fund/ITF:

"High Performance and Intelligent Video Surveillance System" (UIM/118) HK$5,444,00 (2003-2005)
"Robust Object Segmentation Method for Video Surveillance System" (UIT/058) HK$365,000 (2004-2006)
"Flexible Framework for GPGPU-based Video Decoding and Post-processing" (ITS/139) HK$999,120 (2009-2010)

Last updated : January 2011