Anne Condon

Professor and Head
The Department of Computer Science
University of British Columbia
201-2366 Main Mall
Vancouver, BC V6T1Z4
Canada

telephone: (604) 822-8175 (cs office)
fax: (604) 822-5485
email: condon at cs dot ubc dot ca

Ph.D., University of Washington, 1987.
B.Sc., University College Cork, Ireland, 1982.

Contents


Research Interests

I am interested in computational complexity theory and design of algorithms, and their applications in bioinformatics, biomolecular computation, hardware verification, and combinatorial auctions. Much of my current work focuses on prediction of the secondary structure of nucleic acids from the base sequence, informed by thermodynamic energy models, as well as applications of prediction tools to design of biomolecules.

For more background on our RNA work, see the nice article in SIAM News Sweet Structural Mysteries of Life, by Barry Cipra (2008). Dick Lipton's blog, Godel's Lost Letter, has an entry (2009) titled The Unbounded Power of Randomness which decribes some of our joint theoretical work on the power of randomness and nondeterminism in finite state machines.


Publications (most are available in pdf format)

H. Jabbari and A. Condon A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures BMC Bioinformatics, 15:147, 2014.

A. Condon, B. Kirkpatrick and J. Manuch. Reachability bounds for chemical reaction networks and strand displacement systems, Natural Computing, 2013. An earlier version appeared in the 18th International Conference on DNA Computing and Molecular Programming, Springer-Verlag Lecture Notes in Computer Science 7433:43-57, 2012.

B. Rastegari, A. Condon, K. Leyton-Brown and N. Immorlica. Two-Sided matching with partial information, The Fourteenth ACM Conference on Electronic Commerce (EC), 2013.

B. Kirkpatrick, M. Hajiaghayi and A. Condon. A new model for approximating RNA folding trajectories and population kinetics, Computational Science & Discovery Volume 6 Number 1, 2013.

C. Thachuk and A. Condon. Space and energy efficient computation with DNA strand displacement systems, 18th International Conference on DNA Computing and Molecular Programming, Springer-Verlag Lecture Notes in Computer Science 7433:135-150, 2012.

A. Condon, J. Manuch and C. Thachuk, The complexity of string partitioning, 23rd Annual Symposium on Combinatorial Pattern Matching, Springer-Verlag Lecture Notes in Computer Science 7354:159-172, 2012.

A. Condon and C. Thachuk. Efficient codon optimization with motif engineering, J. Discrete Algorithms, May 3, 2012. (A preliminary version appeared in the International Workshop on Combinatorial Algorithms, 337-348, 2011.

M. Hajiaghayi, A. Condon and H. H. Hoos. Analysis of energy-based algorithms for RNA secondary structure prediction, BMC Bioinformatics 13:22 (11 pages), 2012.

A. Condon, A.J. Hu, J. Manuch and C. Thachuk. Less haste, less waste: On recycling and its limits in strand displacement systems, J. Royal Society - Interface Focus, February 2012 (published online before print). (A preliminary version appeared in 17th International Conference on. DNA Computing and Molecular Programming, 2011.)

Jiarui Ding, Ali Bashashati, Andrew Roth, Arusha Oloumi, Kane Tse, Thomas Zeng, Gholamreza Haffari, Martin Hirst, Marco A. Marra, Anne Condon, Samuel Aparicio and Sohrab P. Shah. Feature based classifiers for somatic mutation detection in tumour-normal paired sequencing data, Bioinformatics (2012) 28(2): 167-175.

A. Condon. Molecular programming: DNA and the brain, Nature News and Views, 475, 304-305, 2011.

B. Rastegari, A. Condon and K. Leyton-Brown. Revenue monotonicity in deterministic, dominant-strategy combinatorial auctions, Artificial Intelligence, 175:2, 441-456, 2011.

C. Thachuk, J. Manuch, L . Stacho, and A. Condon. NP-completeness of the direct energy barrier height problem without pseudoknots, Natural Computing, 10(1):391-405, 2011. (pdf) (A preliminary version appeared in Proc.15th International Meeting on DNA Computing and Molecular Programming, Springer-Verlag Lecture Notes in Computer Science 5877:106-115, 2009.)

M. Andronescu, A. Condon, H.H. Hoos, D.H. Mathews and K.P. Murphy. Computational approaches for RNA energy parameter estimation, RNA 16, 2304-2318, 2010.

C. Thachuk, J. Manuch, A. Rafiey, L.-A. Mathieson, L. Stacho, and A. Condon. An algorithm for the energy barrier problem without pseudoknots and temporary arcs, Pacific Symposium on Biocomputing, 15:108-119, 2010.

M. S. Andronescu, C. Pop, and A. E. Condon. Improved free energy parameters for RNA pseudoknotted secondary structure prediction, RNA 16, 26-42, 2010.

H.L. Chen, H. Jabbari and A. Condon. An O(n5) algorithm for MFE prediction of kissing hairpins and 4-chains in nucleic acids, J. Comput. Biol., 803-815 2009.

ACM DL Author-ize serviceAlgorithms for distributional and adversarial pipelined filter ordering problems
Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu
ACM Transactions on Algorithms (TALG), 2009

B. Rastegari, A. Condon, and K. Leyton-Brown. Stepwise randomized combinatorial auctions achieve revenue monotonicity, ACM-SIAM Symposium on Discrete Algorithms, 738-747, 2009.

A. Condon and H. Jabbari. Computational prediction of nucleic acid secondary structure: Methods, applications and challenges, Theoretical Computer Science, 9:340 (10 pages), 2009.

M. Andronescu, V. Bereg, H.H. Hoos, and A. Condon. RNA STRAND: The RNA secondary structure and statistical analysis database, BMC Bioinformatics 9:340, 2008.

A. Condon, J. Manuch, and C. Thachuk. Complexity of a collision-aware string partition problem and its relation to oligo design for gene synthesis, The 14th Annual International Computing and Combinatorics Conference (COCOON), Springer-Verlag Lecture Notes in Bioinformatics 5092:265-275, 2008.

H. Jabbari, A. Condon, A. Pop, C. Pop, and Y. Zhao. HFold: RNA pseudoknotted secondary structure prediction using hierarchical folding, J. Comput Biol.15(2): 139--163, 2008. (A preliminary version appeared in Algorithms in Bioinformatics: 5th International Workshop, 2007.)

C. Thachuk and A. Condon, On the design of oligos for gene synthesis, IEEE 7th International Symposium on Bioinformatics and Bioengineering, 2007.

M. Andronescu, A. Condon, H.H. Hoos, D.H. Mathews and K.P. Murphy. Efficient parameter estimation for RNA secondary structure prediction, Bioinformatics. 2007 Jul 1;23(13):i19-28. (Proc. of the 15th Annual International conference on Intelligent Systems for Molecular Biology, 2007.)

ACM DL Author-ize service Revenue monotonicity in combinatorial auctions
Baharak Rastegari, Anne Condon, Kevin Leyton-Brown
ACM SIGecom Exchanges, 2007

B. Rastegari and A. Condon. Parsing nucleic acid pseudoknotted secondary structure: algorithm and applications, J. Comput Biol.14(1): 16--32, 2007. (A preliminary version appeared in Algorithms in Bioinformatics: 5th International Workshop, Springer-Verlag Lecture Notes in Computer Science 3692:341-352, 2005.)

R. Aguirre-Hernandez, H.H. Hoos and A. Condon. Computational RNA secondary structure design: empirical complexity and improved methods, BMC Bioinformatics, 8:34, 2007.

A. Condon. Designed DNA molecules: principles and applications, Nature Reviews Genetics 7, 565-575, 2006.

ACM DL Author-ize serviceFlow algorithms for two pipelined filter ordering problems
Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu
PODS '06 Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2006

M. Andronescu and A. Condon. Finding MFE structures formed by nucleic acid strands in a combinatorial set, Nanotechnology: Science and Computing, J. Chen, N. Jonoska. G. Rozenberg (Eds.), G. Rozenberg (Eds.), Natural Computing Series, Springer, 121-136, 2006.

A. Condon and S. Shah. Finding local RNA motifs using covariance models, Technical Report Number TR-2006-08, U. British Columbia, April 2006.

J. Ren, B. Rastegari, A. Condon, and H.H. Hoos. HotKnots: Heuristic prediction of RNA secondary structures including pseudoknots, RNA, 11 (10): 1494-1504, 2005.

D. Tulpan, M. Andronescu, S.B. Chang, M.R. Shortreed, A. Condon, H.H. Hoos, and L.M. Smith. Thermodynamically based DNA strand design, Nucleic Acids Res. 2005 33(15):4951-64.

M.R. Shortreed, S.B. Chang, D.G. Hong, M. Phillips, B. Campion, D.C. Tulpan, M. Andronescu, A. Condon, H.H. Hoos, and L.M. Smith. A thermodynamic approach to designing structure-free combinatorial DNA word sets, Nucleic Acids Research 2005 33(15):4965-4977.

M. Andronescu, Z.C. Zhang and A. Condon. Secondary structure prediction of interacting RNA molecules, Journal of Molecular Biology, 345 (5): 987-1001, Feb 2005.

J. Bingham, A. Condon, A.J. Hu, S. Qadeer, and Z.C. Zhang. Automatic verification of sequential consistency for unbounded addresses and data values, 16th International Conference on Computer Aided Verification (CAV), Springer-Verlag Lecture Notes in Computer Science 3114:427-439, 2004.

A. Condon, B. Davy, B. Rastegari, F. Tarrant, and S. Zhao. Classifying RNA pseudoknotted structures, Theoretical Computer Science 2004, 320(1):35--50.

A. Condon. Automata make antisense, Nature News and Views 2004, 429(6990): 351--352.

M. Saks and A. Condon. A limit theorem for sets of stochastic matrices, Linear Algebra and Applications 2004, 381:61--76.

M. Andronescu, A.P. Fejes, F. Hutter, H.H. Hoos, and A. Condon. A new algorithm for RNA secondary structure design, Journal of Molecular Biology 2004, 336(3):607-624.

M. Andronescu, R. Aguirre-Hernandez, A. Condon, and H.H. Hoos. RNAsoft: a suite of RNA secondary structure prediction and design software tools, Nucl. Acids. Res. 2003, 31: 3416-3422.

A. Condon. Problems on RNA secondary structure prediction and design, Proceedings of the 30th Annual International Colloquium on Automata, Languages and Programming (ICALP), Jos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Herhard J. Woeginger (Eds.), Springer-Verlag Lecture Notes in Computer Science 2719:22-32, 2003.

ACM DL Author-ize serviceToward a decidable notion of sequential consistency
Jesse D. Bingham, Anne Condon, Alan J. Hu
SPAA '03 Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, 2003

ACM DL Author-ize serviceAutomatable verification of sequential consistency
Anne E. Condon, Alan J. Hu
SPAA '01 Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, 2001

O. Madani, A. Condon, and S. Hanks. On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision process problems, Artificial Intelligence, Special Issue on Planning with Uncertainty and Incomplete Information, Sven Koenig, Tom Dean and Craig Boutilier (Eds.), 147:1-2, 5 - 34, 2003.

M. Andronescu, D. Dees, L. Slaybaugh, Y. Zhao, B. Cohen, A. Condon, and S. Skiena. Algorithms for testing that sets of DNA words concatenate without secondary structure, Proceedings of the Eighth International Workshop on DNA Based Computers, Hokkaido, Japan, June 2002. Springer-Verlag Lecture Notes in Computer Science 2568:182-195, 2003.

D. Tulpan, H.H. Hoos, and A. Condon. Stochastic local search algorithms for DNA word design, Proceedings of the Eighth International Workshop on DNA Based Computers, Hokkaido, Japan, June 2002. Springer-Verlag Lecture Notes in Computer Science 2568:229-241, 2003.

A. Brenneman and A. Condon. Strand design for bio-molecular computation, (Survey Paper), Theoretical Computer Science, Vol. 287:1, 2002, pages 39-58.

D. Sorin, M. Plakal, A.E. Condon, M.D. Hill, M.M. Martin, and D.A. Wood. Specifying and verifying a broadcast and a multicast snooping cache coherence protocol, IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 6, June 2002.

M. Li, H. Lee, A. Condon, and R.M. Corn. DNA word design strategy for creating sets of non-interacting sets of oligonucleotides for DNA microarrays, Langmuir 18, 805-812, American Chemical Society, 2002.

T. Braun, A. Condon, A.J. Hu, K.S.Juse, M. Laza, M. Leslie, and R. Sharma. Proving sequential consistency by model checking, IEEE International High Level Design Validation and Test Workshop (HLDVT), November 2001.

A. Condon. Bounded error probabilistic finite state automata, Handbook on Randomized Computing, Volume II, (edited by Panos Pardalos, John Reif, and Jose Rolim), Kluwer, 2001, pages 509-532.

A. Condon, R.M. Corn, and A. Marathe. On combinatorial DNA word design, J. Computational Biology, 8:3, pages 201-220, 2001. (Extended abstract in Proceedings of the 5th International Meeting on DNA Based Computers, June 1999).

A. Condon and R.M. Karp. Algorithms for graph partitioning on the planted bisection model, J. Random Structures and Algorithms, 18, 116-140, 2001. (Extended abstract in RANDOM'99, August, 1999).

L. Wang, Q. Liu, A. Condon, R.M. Corn, and L.M. Smith. Multiple word DNA computing on surfaces, J. Am. Chem. Soc., 122 7435-7440.

Q. Liu, A.G. Frutos, L. Wang, A. Condon, R.M. Corn, and L.M. Smith. DNA computations on surfaces, Nature, 403 pages 175-179, 2000.

ACM DL Author-ize serviceA system-level specification framework for I/O architectures
Mark D. Hill, Anne E. Condon, Manoj Plakal, Daniel J. Sorin
SPAA '99 Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, 1999

A. Condon, M. Hill, M. Plakal, and D. Sorin. Using Lamport clocks to reason about relaxed memory models, Proceedings of the Fifth International Symposium On High Performance Computer Architecture (HPCA-5), January 1999.

ACM DL Author-ize serviceLamport clocks: verifying a directory cache-coherence protocol
Manoj Plakal, Daniel J. Sorin, Anne E. Condon, Mark D. Hill
SPAA '98 Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, 1998

S. Agarwal and A. Condon. On approximation algorithms for hierarchical MAX-SAT, Journal of Algorithms., Vol. 26, 1998, pages 141-165.

A. Condon and L. Narayanan. Upper and lower bounds for selection on the mesh, Algorithmica, Vol. 20, 1998, pages 1-30.

A. Condon, L. Hellerstein, S. Pottle, and A. Wigderson. Finite state automata with nondeterministic and probabilistic states, SIAM Journal on Computing , Vol. 27, No. 3, pages 739-762, June 1998.

E. Bach, A. Condon, E. Glaser, and C. Tanguay. DNA models and algorithms for NP-complete problems, J. Computer and System Sciences , 57, pages 172-186, 1998. An extended abstract appeared in the Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, May 1996.

A.G. Frutos, Q. Liu, A.J. Thiel, A.M.W. Sanner, A.E. Condon, L.M. Smith and R.M. Corn. Demonstration of a word design strategy for DNA computing on surfaces (Abstract), Nucleic Acids Research, Vol. 25, pp. 4748-4757 (1997).

A. Condon, J. Feigenbaum, C. Lund, and P. Shor. Random debaters and the hardness of approximating stochastic functions, SIAM Journal on Computing, Vol. 26, No. 2, March 1997, pages 369-400.

W. Cai, A. Condon, R.M. Corn, E. Glaser, Z. Fei, T. Frutos, Z. Guo, M.G. Lagally, Q. Liu, L.M. Smith, and A. Thiel. The power of surface-based DNA computation, Proceedings of the First Annual International Conference on Computational Molecular Biology (Recomb97) , ACM, January 1997.

A. Condon, J. Lampe, R.E. Ladner, and R. Sinha. The complexity of sub-bus mesh computations, SIAM Journal on Computing, Vol. 25, No. 3, June 1996, pages 520-539.

Q. Liu, Z. Guo, A. Condon, R.M. Corn, M.G. Lagally and L.M. Smith. A surface-based approach to DNA computation, Proceedings of the Second Annual Meeting on DNA Based Computers, Princeton, June 1996.

A. Condon and G. Lewandowski. Experiments with parallel graph coloring heuristics, Cliques, Coloring and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science , Volume 26, American Mathematical Society, 1996, pages 309-334.

S. Chung and A. Condon. Parallel implementation of Boruvka's minimum spanning tree algorithm, Proceedings of the 10th International Parallel Processing Symposium , April 1996.

E. Bach, A. Condon, and G. Lewandowski. Realistic analysis of parallel dynamic programming algorithms, IEEE Transactions on Parallel and Distributed Systems , Vol. 7, No. 4, April 1996, pages 425-438.

A. Condon, J.Feigenbaum, C. Lund, and Peter Shor. Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions, Chicago Journal of Theoretical Computer Science , Vol. 1995, Article 4, 19 October 1995.

A. Condon and R. Ladner. Interactive proof systems with polynomially bounded strategies, Journal of Computer and System Sciences , Vol. 50, No. 3, June 1995, pages 506--518.

A. Condon. A theory of strict P-completeness, Computational Complexity, Vol. 4, 1994, pages 220-241.

A. Condon and D. Hernek. Random walks on colored graphs, Random Structures and Algorithms, Vol. 5, No. 2, 1994, pages 285-303.

A. Condon and M. Melekopoglou. On the complexity of the policy iteration algorithm for stochastic games, Operations Research Society of America (ORSA) Journal on Computing, Vol. 6, No. 2, Spring 1994.

J-Y Cai, A. Condon, and R.E. Lipton. PSPACE is provable by two provers in one round, Journal of Computer and System Sciences, Vol. 48, No. 1, February 1994, pages 183-193.

A. Condon. On algorithms for simple stochastic games, In ``Advances in Computational Complexity Theory,'' DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 13, edited by Jin-Yi Cai, American Mathematical Society, 1993, pages 51-73.

A. Condon. The complexity of space bounded interactive proof systems, In ``Complexity Theory: Current Research,'' S. Homer, U. Schöning and K. Ambos-Spies (Eds.), Cambridge University Press, 1993, pages 147-190.

ACM DL Author-ize serviceSpace-bounded probabilistic game automata
Anne Condon
Journal of the ACM (JACM), 1991

A. Condon and R.J. Lipton. On the complexity of space bounded interactive proofs, Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS), 1989, pages 462--267.

A. Condon and R.E. Ladner. Probabilistic game automata, J. Computer and System Sciences, Vol. 36(3) 1988, pages 452-489.

Links