Ming Li's Home Page

Canada Research Chair in Bioinformatics
Professor, School of Computer Science
University of Waterloo, Waterloo, Ontario N2L 3G1
Email: mli at uwaterloo dot ca
Phone: 519-888-4659, Fax: 519-885-1208

picture of my .sig

Home | Complete CV | Bioinformatics papers | Other papers
Some old papers in computational biology:

Our bioinformatics group website maintains a complete list of all my bioinformatics papers. Please go there to download my papers related to bioinformatics or computational biology.

PatternHunter: Faster and mose sensitive homology search by B. Ma, J. Tromp, M. Li, Bioinformatics, 18:3(2002), 440-445.

A compression algorithm for DNA sequences and its applications in genome comparison by Xin Chen, Sam Kwong, Ming Li in GIW'99 (Best Paper Award) and RECOMB'00 . You can go to Sam's website to download the program and find more information.

Linear Approximation of Shortest Superstrings by Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis in STOC'91 and Journal of ACM, 41:4 (1994), 630-647.

DNA Sequencing and String Learning by Tao Jiang and Ming Li in Math. Syst. Theory 29(1996), 387-405. Preliminary version in FOCS'90 by Ming Li.

Finding Si milar Regions in Many Strings by Ming Li, Bin Ma, and Lusheng Wang (323K) STOC'99.

Distinguishing String Selection by J. Kevin Lanctot, Ming Li, Bin Ma, Shaojiu Wang, and Louxin Zhang (220K) SODA'99.

Recovering Bran ches on the Tree of Life: An Approximation Algorithm by Paul Kearney, Ming Li, John Tsang and, Tao Jiang (290K), SODA'99.

Orchestratin g Quartets: Approximation and Data Correction by Tao Jiang, Paul Kearney, and Ming Li (277K) in FOCS98.

From Gene Trees to Species Trees by Bin Ma, Ming Li, and Louxin Zhang (395K). Preliminary version in RECOMB'98.

On the Complexit y and Approximation of Syntenic Distance by Bhaskar DasGupta, Tao Jiang, Sampath Kannan, Ming Li, and Elisabeth Sweedyk (293K) in RECOMB'97.

Inferring a DNA sequence from erroneous copies by John Kececioglu, Ming Li, and John Tromp. In Theoretical Computer Science, 185:1(1997), 3-13

On Distances b etween Phylogenetic Trees by Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, and Louxin Zhang (439K) in SODA'97.

Some Not es on the Nearest Neighbour Interchange Distance by Ming Li, John Tromp, and Louxin Zhang (139K) in Journal of Theoretical Biology,182 (1996), 463-467.

Quartet Cle aning: Improved Algorithms and Simulations by Vincent Berry, Tao Jiang, Paul Kearney, Ming Li, and Todd Wareham (293K) submitted for publication.

On the approximation of shortest common supersequences and longest common subsequences by Tao Jiang and Ming Li. In ICALP'94 and SIAM J. Comput. 24:5(1995), 1122-1139.

Fixed topology alignment with recombination by Bin Ma, Lusheng Wang, and Ming Li. In CPM'98.

Twist-rotation transformations of binary trees and arithmetic expressions by Ming Li and Louxin Zhang. Journal of Algorithms. This paper is not really in computational biology, although related to nni distance.
Papers in Computational Learning Theory

M. Kearns, M. Li and L. Valiant, Learning Boolean Formulae in J. ACM, 41:6(1994), 1298-1328. (Preliminary version appeared in STOC'87)

M. Kearns and M. Li, Learning in the presence of malicious errors. in STOC'88 and SIAM J. Comput., 22:4(1993), 807-837. Source missing, to be added.

T. Hancock, T. Jiang, M. Li and J. Tromp, Lower bounds on learning decision lists and trees. in Information and Computation, 126:2(1996), 114-122.

M. Li and P.M.B. Vitanyi, Learning simple concepts under simple distributions, SIAM. J. Computing, 20:5(1991), 911-935. (Also in FOCS'89)

M. Li and P.M.B. Vitanyi, Computational Machine Learning in Theory and Praxis. In: `Computer Science Today', J. van Leeuwen, Ed., Lecture Notes in Computer Science, Vol. 1000, Springer Verlag, Heidelberg, 1995, 518-535.

P.M.B. Vitanyi and M. Li, On Prediction by Data Compression, Proc. 9th European Conference on Machine Learning, Lecture Notes in Artificial Intelligence, Vol. 1224, Springer-Verlag, Heidelberg, 1997, 14-30.

P.M.B. Vitanyi and M. Li, Minimum Description Length Induction, Bayesianism, and Kolmogorov Complexity Submitted to: IEEE Trans. Inform. Theory.

M. Li and P.M.B. Vitanyi, Inductive reasoning and Kolmogorov complexity, J. Comp. System Sciences, 44:2(1992), 343-384.

M. Li, Q. Gao and P.M.B. Vitanyi, Recognizing on-line handwritten characters using MDL, Proc. 1993 IEEE Information Theory Workshop, Japan, 1993, 24-25. Manuscript (full version) (Some results were reported by Q. Gao and M. Li in IJCAI'88)
Papers in Distributed Computing and Physics of Computing

M. Charikar, C. Chekuri, T.Y. Cheung, Z. Dai, A. Goel, S. Guha, M. Li, Approximation algorithms for directed Steiner problems, In SODA'98.

A. Israeli and M. Li, Bounded Time Stamps, In Distributed Computing, 6(1993), 205-209 and also in FOCS'87.

M. Li, J. Tromp and P.M.B. Vitanyi, How to share concurrent wait-free variables, J. Assoc. Comp. Mach., 43:4 (1996), 723-746.

M. Li and P.M.B. Vitanyi, Optimality of Wait-Free Atomic Multiwriter Variables, Information Processing Letters, 43(1992), 107-112.

M. Li and P.M.B. Vitanyi, Reversibility and adiabatic computation: trading time and space for energy, Proc. Royal Society of London, Series A, 452(1996), 769-789.

M. Li, J. Tromp, and P. Vitanyi, Reversible simulation of irreversible computation. Physica D, 120(1998) 168-176.
Papers in Logic Programming and AI

J.H. You, R. Cartwright, and M. Li, Iterative belief revision in extended logic programming, In Theoretical Computer Science, 170(1996), 383-406.

D. Foulser, M. Li, and Q. Yang, A theory of plan merging, In Artificial Intelligence, 57(1992), 143-181. (Preliminary version appeared in AAAI'91.) (This file misses a few pictures and reference section.)
Papers in Kolmogorov Complexity:

M. Li and P.M.B. Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, Second Edition, 1997 (xx + 637 pp). Readers' comments and order information of this book can be found at amazon.com Chinese version won the First Class award of 1999 Chinese Science and Technology Book Prize.

M. Li, X. Chen, X. Li, B. Ma, P. Vitanyi, Similarity measure and phylogeny. ms April, 2002, Appeared in SODA, IEEE Trans Information theory

X. Chen, M. Li, B. Mckinnon, A. Seker, A theory of uncheatable program plagiarism detection and its practical implementation. Manuscript. May, 2002. Appeared in IEEE Trans Information theory.

T. Jiang, M. Li, P. Vitanyi, Average-Case Complexity of Shellsort. J.ACM 47:5(2000), 905--911

T. Jiang, M. Li, P. Vitanyi, The expected size of Heilbronn's triangles. Random Structures and Algorithms, 20:2(2002), 206-219

H. Buhrman, T. Jiang, M. Li, P. Vitanyi, New applications of the incompressibility method: Part II, Theretical Computer Science, (also ICALP'99)

H. Buhrman, M. Li, J. Tromp and P.M.B. Vitanyi, Kolmogorov Random Graphs and the Incompressibility Method, SIAM J. Comput

T. Jiang, M. Li, P. Vitanyi, New applications of the incompressibility method: Part I, The Computer Journal.

C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitanyi, and W. Zurek, Information Distance, IEEE Trans. Inform. Theory, IT-44:4(1998) 1407--1423. (Also in STOC'93)

T. Jiang and M. Li, K one-way heads cannot do string matching. STOC'93 (Final version in JCSS)

M. Li and P.M.B. Vitanyi, Average-case analysis via incompressibility, Proc. 11th Conference on Fundamentals of Computation Theory, Lecture Notes in Comuter Science, Vol. 1279, Springer-Verlag, Heidelberg, 1997, 38--50.

W. Kirchherr, M. Li and P.M.B. Vitanyi, The miraculous universal distribution, ``Mathematical Intelligencer,'' 19:4(1997), 7--15.

M. Li and P.M.B. Vitanyi, A new approach to formal language theory by Kolmogorov complexity, SIAM J. Comput., 24:2(1995), 398-410.

M. Li and P.M.B. Vitanyi, Kolmogorov complexity arguments in Combinatorics, J. Comb. Th., Series A, 66:2(1994), 226-236. Correction, Ibid., 69(1995), 183.

M. Li and P.M.B. Vitanyi, Statistical properties of finite sequences with high Kolmogorov complexity, Math. System Theory, 27(1994), 365-376.

M. Li and P.M.B. Vitanyi, Average case complexity equals worst-case complexity under the Universal Distribution, Information Processing Letters, 42(1992), 145-150.

M. Li, L. Longpré, and P.M.B. Vitanyi, The power of the queue, SIAM J. Computing, 21:4(1992), 697-712.

M. Li and P.M.B. Vitanyi, Tape versus stacks and queue: the lower bounds, Information and Computation, 78 (1988), 56-85.

Chain Letters

Mammal Tree Matrix
Maintained by Ming Li, April 14, 2005.