Curriculum Vitae

Kun-Mao Chao (趙坤茂)

 

Work Address:

Department of Computer Science and Information Engineering

National Taiwan University

Taipei 106, Taiwan

Tel: 886-2-23625336 ext. 423

Fax: 886-2-23628167

Email: email

Homepage: http://www.csie.ntu.edu.tw/~kmchao

 

Education:

Ph.D. in Computer Science (August 1993), The Pennsylvania State University, University Park, PA, USA.

M.S. in Computer Engineering (June 1987), National Chiao Tung University, Hsinchu, Taiwan.

B.S. in Computer Engineering (June 1985), National Chiao Tung University, Hsinchu, Taiwan.

 

Employment:

Professor, Graduate Institute of Biomedical Electronics and Bioinformatics, National Taiwan University, Taipei, Taiwan, August 2006 – present.

Adjunct Professor, Graduate Institute of Networking and Multimedia, National Taiwan University, Taipei, Taiwan, August 2004 – present.

Professor, Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, August 2002 – present.

Adjunct Professor, Graduate Program for Bioinformatics, National Yang-Ming University, Taipei, Taiwan, August 2000 – July 2002.

Adjunct Professor, Institute of Biochemistry, National Yang-Ming University, Taipei, Taiwan, October 1999 – July 2002.

Professor, Department of Life Science, National Yang-Ming University, Taipei, Taiwan, August 1999 – July 2002.

Professor, Department of Computer Science and Information Management, Providence University, January 1999 – July 1999.

Associate Professor, Department of Computer Science and Information Management, Providence University, August 1994 – December 1998.

Visiting Scholar, NCBI, National Institutes of Health, January 1994 – July 1994.

Postdoctoral Fellow, Department of Computer Science and Engineering, The Pennsylvania State University, June 1993 – July 1994.

Teaching/Research Assistant, Department of Computer Science, The Pennsylvania State University, August 1989 – May 1993.

Second Lieutenant Engineer: Chinese Air Force Headquarter, July 1987 – May 1989.

Teaching/Research Assistant, Department of Computer Engineering, National Chiao Tung University, July 1985 – June 1987.

Programmer: Microtek Ltd., July 1984 – September 1984.

  

Research Interests:

²         Algorithms

²         Bioinformatics

²         Computational Molecular Biology

²         Software Tools

 

Publications:

(A) Journal papers:

[1]     Chang, R.-C. and Chao, K.-M., 1990, Parallel Operator-Precedence Parsing, Journal of Information Science and Engineering, 6: 51-62.

[2]     Chao, K.-M., Pearson, W. R. and Miller, W., 1992, Aligning Two Sequences within a Specified Diagonal Band, Computer Applications in the Biosciences (CABIOS, now Bioinformatics), 8: 481-487. (PostScript version)

[3]     Chao, K.-M., Hardison, R. C. and Miller, W., 1993, Constrained Sequence Alignment, Bulletin of Mathematical Biology, 55: 503-524. (PostScript version)

[4]     Chao, K.-M., Hardison, R. C. and Miller, W., 1993, Locating Well-Conserved Regions within a Pairwise Alignment, Computer Applications in the Biosciences (CABIOS, now Bioinformatics), 9: 387-396. (PostScript version)

[5]     Hardison, R. C., Chao, K.-M., Adamkiewicz, M., Price, D., Jackson, J., Zeigler, T., Stojanovic, N. and Miller, W., 1993, Positive and Negative Regulatory Elements of the Rabbit Embryonic e-Globin Gene Revealed by an Improved Multiple Alignment Program and Functional Analysis, DNA Sequence, 4: 163-176.

[6]     Hardison, R. C., Chao, K.-M., Schwartz, S., Stojanovic, N., Ganetsky, M. and Miller, W., 1994, Globin Gene Server: A Prototype E-Mail Database Server Featuring Extensive Multiple Alignments and Data Compilation for Electronic Genetic Analysis, Genomics,  21: 344-353.

[7]     Chao, K.-M., Hardison R. C. and Miller, W., 1994, Recent Developments in Linear-Space Alignment Methods: a Survey, Journal of Computational Biology, 1: 271-291. (PostScript version)

[8]     Chao, K.-M. and Miller, W., 1995, Linear-Space Algorithms that Build Local Alignments from Fragments, Algorithmica, 13: 106-134.

[9]     Chao, K.-M., Zhang, J., Ostell, J. and Miller, W., 1995, A Local Alignment Tool for Very Long DNA Sequences, Computer Applications in the Biosciences (CABIOS, now Bioinformatics),  11: 147-153. (PostScript version)

[10] Chao, K.-M., Zhang, J., Ostell, J. and Miller, W., 1997, A Tool for Aligning Very Similar DNA sequences, Computer Applications in the Biosciences (CABIOS, now Bioinformatics),  13: 75-80.

[11] Chao, K.-M., 1998, “On Computing all Suboptimal Alignments,” Information Sciences, 105: 189-207.

[12] Wu, Q. S., Chao, K.-M. and Lee, R. C. T., 1998, “The NPO-Completeness of the Longest Hamiltonian Cycle Problem,” Information Processing Letters, 65: 119-123.

[13] Wu, B. Y., Chao, K.-M. and Tang, C. Y., 1999, “Efficient Algorithms for the Length-Constrained Heaviest Path Problems on a Tree,” Information Processing Letters, 69: 63-67.

[14] Wu, B. Y., Chao, K.-M. and Tang, C. Y., 1999, “Exact and Approximation Algorithms for Constructing Ultrametric Trees from Distance Matrices,” Journal of Combinatorial Optimization, 3: 199-211.

[15] Chao, K.-M., 1999, “Calign: Aligning Sequences with Restricted Affine Gap Penalties,” Bioinformatics, 15: 298-304.

[16] Wu, B. Y., Chao, K.-M. and Tang, C. Y. , 2000, “Approximation Algorithms for some Optimum Communication Spanning Tree Problems,” Discrete Applied Mathematics, 102: 245-266.

[17] Wu, B. Y., Chao, K.-M. and Tang, C. Y., 2000, “A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees,” Journal of Algorithms, 36: 182-204.

[18] Wu, B. Y., Lancia, G., Bafna, V., Chao, K.-M., Ravi, R. and Tang, C. Y., 2000, A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees, SIAM Journal on Computing, 29: 761-778.

[19] Wu, B. Y., Chao, K.-M. and Tang, C. Y., 2000, “Approximation Algorithms for the Shortest Total Path Length Spanning Tree Problem,” Discrete Applied Mathematics, 105: 273-289.

[20] Wu, B. Y., Chao, K.-M. and Tang, C. Y., 2002, “Light Graph with Small Routing Cost,” Networks, 39: 130-138.

[21] Lin, Y.-L., Jiang, T. and Chao, K.-M., 2002, “Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecular Sequence Analysis,” Journal of Computer and System Sciences (JCSS), 65: 570-586.

[22] Lin, Y.-L., Huang, X., Jiang, T. and Chao, K.-M., 2003, “MAVG: Locating Non-Overlapping Maximum Average Segments in a Given Sequence,” Bioinformatics, 19: 151-152.

[23] Huang, X. and Chao, K.-M., 2003, “A Generalized Global Alignment Algorithm,” Bioinformatics, 19: 228-233.

[24] Tang, C. Y., Lu, C. L., Chang, M. D.-T., Tsai Y.-T, Sun, Y.-J., Chao, K.-M., Chang, J.-M., Chiou, Y.-H., Wu, C.-M., Chang, H.-T. and Chou, W.-I., 2003, “A Constrained Multiple Sequence Alignment Tool Development and its Application to RNase Family Alignment,” Journal of Bioinformatics and Computational Biology, 1: 267-287.

[25] Liu, H.-F., Chang, Y.-H. and Chao, K.-M., 2004, “An Optimal Algorithm for Querying Tree Structures and its Applications in Bioinformatics,” ACM SIGMOD Record, 33: 21-26.

[26] Huang, X., Ye, L., Chou, H. -H., Yang, I. -H and Chao, K.-M., 2004, “Efficient Combination of Multiple Word Models for Improved Sequence Comparison,” Bioinformatics, 20: 2529-2533.

[27] Yang, I.-H., Huang, C.-P. and Chao, K.-M., 2005, “A Fast Algorithm for Computing a Longest Common Increasing Subsequence,” Information Processing Letters, 93: 249-253.

[28] Lin, R.-R., Kuo, W.-H. and Chao, K.-M., 2005, “Finding a Length-Constrained Maximum-Density Path in a Tree,” Journal of Combinatorial Optimization, 9: 147-156.

[29] Chen, K.-Y. and Chao, K.-M.,  2005, “Optimal Algorithms for Locating the Longest and Shortest Segments Satisfying a Sum or an Average Constraint,” Information Processing Letters, 96: 197-201.

[30] Huang, Y.-T., Zhang, K., Chen, T. and Chao, K.-M., 2005, “Selecting Additional Tag SNPs for Tolerating Missing Data in Genotyping,” BMC Bioinformatics, 6: 263.

[31] Huang, Y.-T., Chao, K.-M., and Chen, T., 2005, “An Approximation Algorithm for Haplotype Inference by Maximum Parsimony,” Journal of Computational Biology, 12: 1261-1274.

[32] Chang, C.-J., Huang, Y.-T., and Chao, K.-M., 2006, “A Greedier Approach for Finding Tag SNPs,” Bioinformatics, 22: 685-691.

[33] Su, J.-S, Tsai, T.-F., Chang, H.-M., Chao, K.-M., Su, T.-S., Tsai, S.-F., 2006, “Distant HNF1 Site as a Master Control for the Human Class I Alcohol Dehydrogenase Gene Expression,” The Journal of Biological Chemistry, 281(29): 19809-19821.

[34] Cheng, C.-H., Chen, K.-Y., Tien, W.-C., and Chao, K.-M., 2006, “Improved Algorithms for the k Maximum-Sums Problems,” Theoretical Computer Science, 362: 162-170.

[35] Wu, B.Y., Wang, H.-L., Kuan, S.T. and Chao, K.-M., 2007, “On the Uniform Edge-Partition of a Tree,” Discrete Applied Mathematics, 155: 1213-1223.

[36] Chen, K.-Y. and Chao, K.-M.,  2007, “On the Range Maximum-Sum Segment Query Problem,” Discrete Applied Mathematics, 155: 2043-2052.

[37] Liu, H.-F. and Chao, K.-M, 2007, “A Tight Analysis of the Katriel-Bodlaender Algorithm for Online Topological Ordering,” Theoretical Computer Science, 389: 182-189.

[38] Wu, B.Y., Hsiao, C.Y., and Chao, K.-M., 2008, “The Swap Edges of a Multiple-Sources Routing Tree,” Algorithmica, 50: 299-311.

[39] Liu, H.-F. and Chao, K.-M, 2008, “On Locating Disjoint Segments with Maximum Sum of Densities,” Algorithmica, accepted.

[40] Huang, Y.-T. and Chao, K.-M., 2008, “A New Framework for the Selection of Tag SNPs by Multimarker Haplotypes,” Journal of Biomedical Informatics, accepted.

[41] Wang, H.-L., Wu, B.Y., and Chao, K.-M., 2008, “The Backup 2-Center and Backup 2-Median Problems on Trees,” Networks, accepted.

[42] Yang, C.-Y., Chang, C.-H., Lin, T.-C., Yu, Y.-L., Lee, S.-A., Yen, C.-C., Yang, J.-M., Lai, J.-M., Hong, Y.-R., Tseng, T.-L., Chao, K.-M., and Huang, C.-Y., 2008,  “PhosphoPOINT: a Comprehensive Human Kinase Interactome and Phospho-Protein Database,” Bioinformatics, accepted. (ECCB'08 paper)

[43] Cheng, C.-H., Liu, H.-F. and Chao, K.-M, 2008, “Optimal Algorithms for the Average-Constrained Maximum-Sum Segment Problem,” Information Processing Letters, accepted.

[44] Liu, H.-F. and Chao, K.-M, 2008, “Algorithms for Finding the Weight-Constrained k Longest Paths in a Tree and the Length-Constrained k Maximum-Sum Segments of a Sequence,” Theoretical Computer Science, accepted.

[45] Wang, H.-L. and Chao, K.-M., 2008, “The 2-radius and 2-radiian Problems on Trees,” Theoretical Computer Science, accepted.

[46] Chen, P.-A., Liu, H.-F., and Chao, K.-M., 2008, “CNVDetector: locating copy number variations using array CGH data,” Bioinformatics, accepted.

(B) Conference papers:
 (Note: Polished forms of many of the following papers have appeared or will appear in journals listed above.)

[1]     Shaw, J.-R., Suen, J.-S., Chao, K.-M., Chen, S.-H. and Du, M.-W. , 1986, A Syntax-Directed Editor for C Language, Proceedings of the Sixth Workshop on Computer System Technology, 407-416, Taiwan.

[2]     Chao, K.-M. and Chang, R.-C. , 1987, Parallel Operator-Precedence Parsing, Proceedings of National Computer Symposium, 889-894, Taiwan.

[3]     Chao, K.-M. and Chang, R.-C. , 1987, Incremental Operator-Precedence Parsing, Proceedings of National Computer Symposium, 145-151, Taiwan.

[4]     Chao, K.-M., 1994, Computing All Suboptimal Alignments in Linear Space, Combinatorial Pattern Matching '94, Lecture Notes in Computer Science 807, 31-42, California, USA.

[5]     Chao, K.-M., 1994,  An O(MN)-Time, O()-Space Algorithm for Computing All Suboptimal Grid Points, Proceedings of the 10th Workshop on Combinatorial Mathematics and Computational Theory,.48-51, Taiwan.

[6]     Chao, K.-M., 1994, Flexible Space-Saving Strategies for Computing All Suboptimal Alignments, Proceedings of International Computer Symposium, 414-419, Taiwan.

[7]     Chao, K.-M., 1995, Multi-Pattern String Matching with Spacers and Ambiguity, Proceedings of the 12th Workshop on Combinatorial Mathematics and Computational Theory, 131-134, Taiwan.

[8]     Chao, K.-M., 1996, Aligning Genomic DNA Sequences, The First Symposium on Genome Research and Analysis, 15, Taiwan.

[9]     Chao, K.-M., 1996, On Building an Interactive Alignment Tool,” International Symposium on Combinatorics and Applications (SOCA '96), 84-93, Mainland China.

[10] Hsu, W. L., Chao, K.-M., 1996, Searching Patterns in DNA Sequences, International Computer Symposium (poster session, 5 pages), Taiwan.

[11] Zhang, J., Chao, K.-M., Florea, L., Miller, W., 1997, Alignment Requirements for NCBI's Genomes Division, First Annual International Conference on Computational Molecular Biology (RECOMB 97) (poster session, 15 pages), New Mexico, USA.

[12] Wu, B. Y., Chao, K.-M. and Tang, C. Y., 1997, Approximation Algorithms for the Shortest Total Path Length Spanning Tree Problem,” Proceedings of the 14th Workshop on Combinatorial Mathematics and Computational Theory,  10-15, Taiwan.

[13] Chao, K.-M., 1997, “Fast Algorithms for Aligning Sequences with Restricted Affine Gap Penalties,” Third Annual International Computing and Combinatorics Conference (COCOON 97), Lecture Notes in Computer Science 1276, 264-273, Shanghai, Mainland China.

[14] Wu, B. Y., Chao, K.-M., and Tang, C. Y., 1997,  Algorithms for Finding the Shortest Total Path Length 2-stars, National Computer Symposium, E73-76, Taiwan.

[15] Wu, Q. S., Chao, K.-M. and Lee, R. C. T., 1997, “Approximation Algorithms,” International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN ’97), Taiwan.

[16] Wu, B. Y., Lancia, G., Bafna, V., Chao, K.-M., Ravi, R. and Tang, C. Y., 1998, A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees, Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 98), California, USA, 21-32.

[17] Chao, K.-M., 1998  A Whirlwind Tour of Computational Molecular Biology,” Proceedings of the 15th Workshop on Combinatorial Mathematics and Computational Theory, 31-35, Taiwan.

[18] Chao, K.-M., 1998 “Recent Developments in Linear-Space Alignment Methods,” Fourth Symposium on Recent Advances in Biophysics, S37, Taiwan.

[19] Wu, B. Y., Chao, K.-M., and Tang, C. Y, 1998 “Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices,” Fourth Annual International Computing and Combinatorics Conference (COCOON 98), Lecture Notes in Computer Science 1449, 299-308, Taiwan.

[20] Wu, B. Y., Chao, K.-M. and Tang, C. Y., 1998, “Approximation Algorithms for some Optimum Communication Spanning Tree Problems,” Ninth Annual International Symposium on Algorithm and Computation (ISAAC ’98), Lecture Notes in Computer Science, 1533, 107-416, Taejon, Korea.

[21] Wu, B. Y., Chao, K.-M. and Tang, C. Y., 1999, “Constructing Light Spanning Trees with Small Routing Cost,” 16th International Symposium on Theoretical Aspects of Computer Science (STACS ’99), Lecture Notes in Computer Science, 1563, 334-344, Trier, Germany.

[22] 蔡永恆, 林明信, 陳智賢, 柯建全, 王孝熙, 林敏惠, 趙坤茂, 1999, “電子商城的經營型態分析,” 邁向二十一世紀亞太管理學術研討會, 成功大學, Taiwan.

[23] 申永德, 李進成, 周文光, 王讚彬, 趙坤茂, 1999, “無線網路、商機無限,” 邁向二十一世紀亞太管理學術研討會, 成功大學, Taiwan.

[24] Wu, Q. S., Lee, R. C. T. and Chao, K.-M., 2000, “Linear Time Algorithm for the Hamiltonian Path Problem on a Series-Paralle Graph,” Fifth International Conference on Computer Science and Informatics (CS&I'2000), Atlantic City, USA.

[25] Chen, C.-Y., Su, J.-S., Chang, H.-M., Chao, K.-M., Hsiao, K.-J. and Tsai, S.-F., 2000, “The Complete Genome Sequence of the Human ADH Gene Family,” HGM 2000 Gene Mapping and Large Scale Sequencing, (poster session), Vancouver, BC, Canada.

[26] Chao, K.-M., 2002, “Dynamic-Programming Strategies for Biomolecular Sequence Analysis,” Workshop on Sequence and Gene Expression Analysis, 1-40, Singapore. (Invited Tutorial Speaker)

[27] Wu, B. Y., Chao, K.-M. and Tang, C. Y., 2002, “On the Optimum Requirement Graph Problem,” The 19th Workshop on Combinatorial Mathematics and Computational Theory.

[28] Lin, Y.-L., Jiang, T. and Chao, K.-M., 2002, “Efficient Algorithm for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecular Sequence Analysis,” The 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002), Lecture Notes in Computer Science, Poland.

[29] Tang, C. Y., Lu, C. L., Chang, M. D.-T., Tsai Y.-T, Sun, Y.-J., Chao, K.-M., Chang, J.-M., Chiou, Y.-H., Wu, C.-M., Chang, H.-T., Chou, and W.-I., 2002, “A Constrained Multiple Sequence Alignment Tool Development and its Application to RNase Family Alignment,” the first IEEE Computer Society Bioinformatics Conference (CSB 2002), Stanford University, Palo Alto, CA, USA.

[30] Yang, I.-H., Huang, C.-P. and Chao, K.-M., 2003, “A Fast Algorithm for Computing a Longest Common Increasing Subsequence,” The 20th Workshop on Combinatorial Mathematics and Computational Theory, 93-97, Taiwan.

[31] Lin, R.-R., Kuo, W.-H. and Chao, K.-M., 2003, “Finding a Length-Constrained Maximum-Density Path in a Tree,” The 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), Lecture Notes in Computer Science 2906, 78-87, Kyoto, Japan.

[32] Yang, I. -H., Wang, S. -H., Chen, Y. -H., Huang, P. -H., Ye, L., Huang, X. and Chao, K.-M., 2004, “Efficient Methods for Generating Optimal Single and Multiple Spaced Seeds,” IEEE Fourth Symposium on  Bioinformatics and Bioengineering (IEEE BIBE 2004), 411-418, Taiwan.

[33] Huang, Y.-T. and Chao, K.-M., 2004, “On the Selection of Robust Tag SNPs