Professor
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
|
Anne Condon
Professor 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.
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.
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,
Springer-Verlag Lecture Notes in Computer Science, 181-193, 2015.
A. Condon, J. Manuch and C. Thachuk,
The complexity of string partitioning,
Journal of Discrete Algorithms, 32:24-43, 2015.
Preliminary version appeared in the
23rd Annual Symposium on Combinatorial Pattern Matching,
Springer-Verlag Lecture Notes in Computer Science 7354:159-172, 2012.
A. Condon, B. Kirkpatrick and J. Manuch.
Reachability bounds for chemical reaction networks and strand
displacement systems, Natural Computing, 13(4):499-516, 2014.
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.
M. Andronescu, A. Condon, D.H. Turner, and D.H. Mathews.
The Determination of RNA folding nearest neighbor parameters,
Methods in Molecular Biology, 1097:45-70, 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,
Springer-Verlag Lecture Notes in Computer Science
7433:135-150, 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.
(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.
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.)
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.
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
Publications
(most are available in pdf format)
Reasoning about optimal stable matchings under partial informationBaharak Rastegari, Anne Condon, Nicole Immorlica, Robert Irving, Kevin Leyton-Brown
EC '14 Proceedings of the fifteenth ACM conference on Economics and computation, 2014Two-sided matching with partial informationBaharak Rastegari, Anne Condon, Nicole Immorlica, Kevin Leyton-Brown
EC '13 Proceedings of the fourteenth ACM conference on Electronic commerce, 2013Flow algorithms for two pipelined filter ordering problemsAnne 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
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.
Toward a decidable notion of sequential consistency
Automatable verification of sequential consistencyO. 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.
A system-level specification framework for I/O architecturesA. 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.
Lamport clocks: verifying a directory cache-coherence protocolS. 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.
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.