Anne Condon
Professor The Department of Computer Science University of British Columbia Room X551, 2366 Main Mall Vancouver, BC V6T1Z4 Canada telephone: (604) 8228175 (cs office) fax: (604) 8225485 email: condon at cs dot ubc dot ca 

Ph.D., University of Washington, 1987.
B.Sc., University College Cork, Ireland, 1982.
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.
A. Condon and C. Thachuk. Toward Space and EnergyEfficient Computations, In "The Energetics of Computing and Life", The SFI Press, To Appear, 2019.
B. Chugg, A. Condon, and H. Hashemi. Output Oblivious Stochastic Chemical Reaction Networks, The 22nd International Conference on Principles of Distributed Systems (OPODIS), 21:121:16, 2018.
A. Condon, H Kirchner, D. Larivière, W. Marshall, V. Noireaux, T. Tlusty, and E. Fourmentin. Will biologists become computer scientists? EMBO Reports, 19:e46628  2018.
S. Zolaktaf, F. Dannenberg, X. Rudelis, A. Condon, J. Schaeffer, M. Schmidt, C. Thachuk, and E. Winfree. Inferring Parameters for an Elementary Step Model of DNA Structure Kinetics with Locally ContextDependent Arrhenius Rates, 23rd International Conference on DNA Computing and Molecular Programming, SpringerVerlag Lecture Notes in Computer Science, Volume 10467, 172187, 2017. (Also here.)
A. Condon, M. Hajiaghayi, D. Kirkpatrick and J. Manuch. Simplifying Analyses of Chemical Reaction Networks for Approximate Majority, 23rd International Conference on DNA Computing and Molecular Programming, SpringerVerlag Lecture Notes in Computer Science, Volume 10467, 189209, 2017. (Also here.)
A. Condon, B. Kirkpatrick and J. Manuch. Design of nucleic acid strands with long lowbarrier folding pathways, Natural Computing, 2017.
J. Ding, S. Shah, and A. Condon. densityCut: an efficient and versatile topological approach for automatic clustering of biological data, Bioinformatics, 32(17), 25672576 2016.
J. Ding, M.K. McConechy, H.M. Horlings, G. Ha, F.C. Chan,, T. Funnell, S.C. Mullaly, J. Reimand, A. Bashashati, G.D. Bader, D. Huntsman, S. Aparicio, A. Condon, and S.P. Shah. Systematic analysis of somatic mutations impacting gene expression in twelve tumour type, Nature Communications, 6:8554 doi: 10.1038/ncomms9554 (13 pages), 2015.
L.A. Mathieson and A. Condon. On low energy barrier folding pathways for nucleic acid sequences, 21st International Conference on DNA Computing and Molecular Programming, SpringerVerlag Lecture Notes in Computer Science, 181193, 2015.
A. Condon, J. Manuch and C. Thachuk, The complexity of string partitioning, Journal of Discrete Algorithms, 32:2443, 2015. Preliminary version appeared in the 23rd Annual Symposium on Combinatorial Pattern Matching, SpringerVerlag Lecture Notes in Computer Science 7354:159172, 2012.
A. Condon, B. Kirkpatrick and J. Manuch. Reachability bounds for chemical reaction networks and strand displacement systems, Natural Computing, 13(4):499516, 2014. An earlier version appeared in the 18th International Conference on DNA Computing and Molecular Programming, SpringerVerlag Lecture Notes in Computer Science 7433:4357, 2012.
M. Andronescu, A. Condon, D.H. Turner, and D.H. Mathews. The Determination of RNA folding nearest neighbor parameters, Methods in Molecular Biology, 1097:4570, 2014.
H. Jabbari and A. Condon. A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures BMC Bioinformatics, 15:147, 2014.
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, (24 pages) 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, SpringerVerlag Lecture Notes in Computer Science 7433:135150, 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, 337348, 2011.
M. Hajiaghayi, A. Condon and H. H. Hoos. Analysis of energybased 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. (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 tumournormal paired sequencing data, Bioinformatics (2012) 28(2): 167175.
A. Condon. Molecular programming: DNA and the brain, Nature News and Views, 475, 304305, 2011.
B. Rastegari, A. Condon and K. LeytonBrown. Revenue monotonicity in deterministic, dominantstrategy combinatorial auctions, Artificial Intelligence, 175:2, 441456, 2011.
C. Thachuk, J. Manuch, L . Stacho, and A. Condon. NPcompleteness of the direct energy barrier height problem without pseudoknots, Natural Computing, 10(1):391405, 2011. (pdf) (A preliminary version appeared in Proc.15th International Meeting on DNA Computing and Molecular Programming, SpringerVerlag Lecture Notes in Computer Science 5877:106115, 2009.)
M. Andronescu, A. Condon, H.H. Hoos, D.H. Mathews and K.P. Murphy. Computational approaches for RNA energy parameter estimation, RNA 16, 23042318, 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:108119, 2010.
M. S. Andronescu, C. Pop, and A. E. Condon. Improved free energy parameters for RNA pseudoknotted secondary structure prediction, RNA 16, 2642, 2010.
H.L. Chen, H. Jabbari and A. Condon. An O(n^{5}) algorithm for MFE prediction of kissing hairpins and 4chains in nucleic acids, J. Comput. Biol., 803815 2009.
B. Rastegari, A. Condon, and K. LeytonBrown. Stepwise randomized combinatorial auctions achieve revenue monotonicity, ACMSIAM Symposium on Discrete Algorithms, 738747, 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 collisionaware string partition problem and its relation to oligo design for gene synthesis, The 14th Annual International Computing and Combinatorics Conference (COCOON), SpringerVerlag Lecture Notes in Bioinformatics 5092:265275, 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): 139163, 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):i1928. (Proc. of the 15th Annual International conference on Intelligent Systems for Molecular Biology, 2007.)
B. Rastegari and A. Condon. Parsing nucleic acid pseudoknotted secondary structure: algorithm and applications, J. Comput Biol.14(1): 1632, 2007. (A preliminary version appeared in Algorithms in Bioinformatics: 5th International Workshop, SpringerVerlag Lecture Notes in Computer Science 3692:341352, 2005.)
R. AguirreHernandez, 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, 565575, 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, 121136, 2006.
A. Condon and S. Shah. Finding local RNA motifs using covariance models, Technical Report Number TR200608, 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): 14941504, 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):495164.
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 structurefree combinatorial DNA word sets, Nucleic Acids Research 2005 33(15):49654977.
M. Andronescu, Z.C. Zhang and A. Condon. Secondary structure prediction of interacting RNA molecules, Journal of Molecular Biology, 345 (5): 9871001, 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), SpringerVerlag Lecture Notes in Computer Science 3114:427439, 2004.
A. Condon, B. Davy, B. Rastegari, F. Tarrant, and S. Zhao. Classifying RNA pseudoknotted structures, Theoretical Computer Science 2004, 320(1):3550.
A. Condon. Automata make antisense, Nature News and Views 2004, 429(6990): 351352.
M. Saks and A. Condon. A limit theorem for sets of stochastic matrices, Linear Algebra and Applications 2004, 381:6176.
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):607624.
M. Andronescu, R. AguirreHernandez, A. Condon, and H.H. Hoos. RNAsoft: a suite of RNA secondary structure prediction and design software tools, Nucl. Acids. Res. 2003, 31: 34163422.
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.), SpringerVerlag Lecture Notes in Computer Science 2719:2232, 2003.
O. Madani, A. Condon, and S. Hanks. On the undecidability of probabilistic planning and infinitehorizon 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:12, 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. SpringerVerlag Lecture Notes in Computer Science 2568:182195, 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. SpringerVerlag Lecture Notes in Computer Science 2568:229241, 2003.
A. Brenneman and A. Condon. Strand design for biomolecular computation, (Survey Paper), Theoretical Computer Science, Vol. 287:1, 2002, pages 3958.
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 noninteracting sets of oligonucleotides for DNA microarrays, Langmuir 18, 805812, 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 509532.
A. Condon, R.M. Corn, and A. Marathe. On combinatorial DNA word design, J. Computational Biology, 8:3, pages 201220, 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, 116140, 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 74357440.
Q. Liu, A.G. Frutos, L. Wang, A. Condon, R.M. Corn, and L.M. Smith. DNA computations on surfaces, Nature, 403 pages 175179, 2000.
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 (HPCA5), January 1999.
S. Agarwal and A. Condon. On approximation algorithms for hierarchical MAXSAT, Journal of Algorithms., Vol. 26, 1998, pages 141165.
A. Condon and L. Narayanan. Upper and lower bounds for selection on the mesh, Algorithmica, Vol. 20, 1998, pages 130.
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 739762, June 1998.
E. Bach, A. Condon, E. Glaser, and C. Tanguay. DNA models and algorithms for NPcomplete problems, J. Computer and System Sciences , 57, pages 172186, 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. 47484757 (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 369400.
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 surfacebased 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 subbus mesh computations, SIAM Journal on Computing, Vol. 25, No. 3, June 1996, pages 520539.
Q. Liu, Z. Guo, A. Condon, R.M. Corn, M.G. Lagally and L.M. Smith. A surfacebased 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 309334.
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 425438.
A. Condon, J.Feigenbaum, C. Lund, and Peter Shor. Probabilistically checkable debate systems and approximation algorithms for PSPACEhard 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 506518.
A. Condon. A theory of strict Pcompleteness, Computational Complexity, Vol. 4, 1994, pages 220241.
A. Condon and D. Hernek. Random walks on colored graphs, Random Structures and Algorithms, Vol. 5, No. 2, 1994, pages 285303.
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.
JY 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 183193.
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 JinYi Cai, American Mathematical Society, 1993, pages 5173.
A. Condon. The complexity of space bounded interactive proof systems, In ``Complexity Theory: Current Research,'' S. Homer, U. Schöning and K. AmbosSpies (Eds.), Cambridge University Press, 1993, pages 147190.
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 462267.
A. Condon and R.E. Ladner. Probabilistic game automata, J. Computer and System Sciences, Vol. 36(3) 1988, pages 452489.