%% Books
@book{LynchRudDonald01,
Author = {B. R. Donald and K. Lynch and D. Rus},
Title = {Algorithmic and Computational Robotics: New
Directions},
Pages = {408},
Publisher = {A. K. Peters},
Address = {Boston},
Year = {2001},
Key = {LynchRudDonald01}
}
@book{KapurMundyDonald92,
Author = {B. R. Donald and D. Kapur and J. Mundy},
Title = {Symbolic and Numerical Computation for Artificial
Intelligence},
Pages = {369},
Publisher = {Academic Press, Harcourt Jovanovich},
Address = {London},
Year = {1992},
Key = {KapurMundyDonald92}
}
@book{BaillieulBrockettDonald90,
Author = {J.~Baillieul and R.~Brockett and B.~R.~ Donald and others},
Title = {Robotics},
Volume = {41},
Series = {Symposia in Applied Mathematics},
Pages = {196},
Publisher = {American Mathematical Society Press},
Address = {Providence, RI},
Year = {1990},
Key = {BaillieulBrockettDonald90}
}
@book{Donald89,
Author = {B. R. Donald},
Title = {Error Detection and Recovery in Robotics},
Volume = {336},
Series = {Lecture Notes in Computer Science},
Pages = {314},
Publisher = {Springer-Verlag},
Address = {New York},
Year = {1989},
Key = {Donald89}
}
%% Papers Published
@article{fds343327,
Author = {Jou, JD and Holt, GT and Lowegard, AU and Donald,
BR},
Title = {Minimization-Aware Recursive K ∗ (MARK
∗ ): A Novel, Provable Algorithm that
Accelerates Ensemble-Based Protein Design and Provably
Approximates the Energy Landscape},
Journal = {Lecture Notes in Computer Science (Including Subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {11467 LNBI},
Pages = {101-119},
Year = {2019},
Month = {January},
ISBN = {9783030170820},
url = {http://dx.doi.org/10.1007/978-3-030-17083-7_7},
Abstract = {© 2019, Springer Nature Switzerland AG. Protein design
algorithms that model continuous sidechain flexibility and
conformational ensembles better approximate the in vitro and
in vivo behavior of proteins. The previous state of the art,
iMinDEE- A ∗ - K ∗ , computes provable ε
-approximations to partition functions of protein states
(e.g., bound vs. unbound) by computing provable, admissible
pairwise-minimized energy lower bounds on protein
conformations and using the A ∗ enumeration algorithm to
return a gap-free list of lowest-energy conformations.
iMinDEE-A ∗ - K ∗ runs in time sublinear in the number
of conformations, but can be trapped in loosely-bounded,
low-energy conformational wells containing many
conformations with highly similar energies. That is,
iMinDEE- A ∗ - K ∗ is unable to exploit the correlation
between protein conformation and energy: similar
conformations often have similar energy. We introduce two
new concepts that exploit this correlation:
Minimization-Aware Enumeration and Recursive K ∗ . We
combine these two insights into a novel algorithm,
Minimization-Aware Recursive K ∗ (MARK ∗ ), that
tightens bounds not on single conformations, but instead on
distinct regions of the conformation space. We compare the
performance of iMinDEE- A ∗ - K ∗ vs. MARK ∗ by
running the BBK ∗ algorithm, which provably returns
sequences in order of decreasing K ∗ score, using either
iMinDEE- A ∗ - K ∗ or MARK ∗ to approximate partition
functions. We show on 200 design problems that MARK ∗ not
only enumerates and minimizes vastly fewer conformations
than the previous state of the art, but also runs up to
two orders of magnitude faster. Finally, we show that MARK
∗ not only efficiently approximates the partition
function, but also provably approximates the energy
landscape. To our knowledge, MARK ∗ is the first algorithm
to do so. We use MARK ∗ to analyze the change in energy
landscape of the bound and unbound states of the HIV-1
capsid protein C-terminal domain in complex with camelid V H
H, and measure the change in conformational entropy induced
by binding. Thus, MARK ∗ both accelerates existing designs
and offers new capabilities not possible with previous
algorithms.},
Doi = {10.1007/978-3-030-17083-7_7},
Key = {fds343327}
}
@article{fds339564,
Author = {Hallen, MA and Martin, JW and Ojewole, A and Jou, JD and Lowegard, AU and Frenkel, MS and Gainza, P and Nisonoff, HM and Mukund, A and Wang, S and Holt, GT and Zhou, D and Dowd, E and Donald, BR},
Title = {OSPREY 3.0: Open-source protein redesign for you, with
powerful new features.},
Journal = {Journal of Computational Chemistry},
Volume = {39},
Number = {30},
Pages = {2494-2507},
Year = {2018},
Month = {November},
url = {http://dx.doi.org/10.1002/jcc.25522},
Abstract = {We present osprey 3.0, a new and greatly improved release of
the osprey protein design software. Osprey 3.0 features a
convenient new Python interface, which greatly improves its
ease of use. It is over two orders of magnitude faster than
previous versions of osprey when running the same algorithms
on the same hardware. Moreover, osprey 3.0 includes several
new algorithms, which introduce substantial speedups as well
as improved biophysical modeling. It also includes GPU
support, which provides an additional speedup of over an
order of magnitude. Like previous versions of osprey, osprey
3.0 offers a unique package of advantages over other design
software, including provable design algorithms that account
for continuous flexibility during design and model
conformational entropy. Finally, we show here empirically
that osprey 3.0 accurately predicts the effect of mutations
on protein-protein binding. Osprey 3.0 is available at
http://www.cs.duke.edu/donaldlab/osprey.php as free and
open-source software. © 2018 Wiley Periodicals,
Inc.},
Doi = {10.1002/jcc.25522},
Key = {fds339564}
}
@article{fds336327,
Author = {Qi, Y and Martin, JW and Barb, AW and Thélot, F and Yan, AK and Donald,
BR and Oas, TG},
Title = {Continuous Interdomain Orientation Distributions Reveal
Components of Binding Thermodynamics.},
Journal = {Journal of Molecular Biology},
Volume = {430},
Number = {18 Pt B},
Pages = {3412-3426},
Year = {2018},
Month = {September},
url = {http://dx.doi.org/10.1016/j.jmb.2018.06.022},
Abstract = {The flexibility of biological macromolecules is an important
structural determinant of function. Unfortunately, the
correlations between different motional modes are poorly
captured by discrete ensemble representations. Here, we
present new ways to both represent and visualize correlated
interdomain motions. Interdomain motions are determined
directly from residual dipolar couplings, represented as a
continuous conformational distribution, and visualized using
the disk-on-sphere representation. Using the disk-on-sphere
representation, features of interdomain motions, including
correlations, are intuitively visualized. The representation
works especially well for multidomain systems with broad
conformational distributions.This analysis also can be
extended to multiple probability density modes, using a
Bingham mixture model. We use this new paradigm to study the
interdomain motions of staphylococcal protein A, which is a
key virulence factor contributing to the pathogenicity of
Staphylococcus aureus. We capture the smooth transitions
between important states and demonstrate the utility of
continuous distribution functions for computing the
reorientational components of binding thermodynamics. Such
insights allow for the dissection of the dynamic structural
components of functionally important intermolecular
interactions.},
Doi = {10.1016/j.jmb.2018.06.022},
Key = {fds336327}
}
@article{fds337044,
Author = {Ojewole, AA and Jou, JD and Fowler, VG and Donald,
BR},
Title = {BBK* (Branch and Bound Over K*): A Provable and Efficient
Ensemble-Based Protein Design Algorithm to Optimize
Stability and Binding Affinity Over Large Sequence
Spaces.},
Journal = {Journal of Computational Biology : a Journal of
Computational Molecular Cell Biology},
Volume = {25},
Number = {7},
Pages = {726-739},
Year = {2018},
Month = {July},
url = {http://dx.doi.org/10.1089/cmb.2017.0267},
Abstract = {Computational protein design (CPD) algorithms that compute
binding affinity, Ka, search for sequences with an
energetically favorable free energy of binding. Recent work
shows that three principles improve the biological accuracy
of CPD: ensemble-based design, continuous flexibility of
backbone and side-chain conformations, and provable
guarantees of accuracy with respect to the input. However,
previous methods that use all three design principles are
single-sequence (SS) algorithms, which are very costly:
linear in the number of sequences and thus exponential in
the number of simultaneously mutable residues. To address
this computational challenge, we introduce BBK*, a new CPD
algorithm whose key innovation is the multisequence (MS)
bound: BBK* efficiently computes a single provable upper
bound to approximate Ka for a combinatorial number of
sequences, and avoids SS computation for all provably
suboptimal sequences. Thus, to our knowledge, BBK* is the
first provable, ensemble-based CPD algorithm to run in time
sublinear in the number of sequences. Computational
experiments on 204 protein design problems show that BBK*
finds the tightest binding sequences while approximating Ka
for up to 105-fold fewer sequences than the previous
state-of-the-art algorithms, which require exhaustive
enumeration of sequences. Furthermore, for 51 protein-ligand
design problems, BBK* provably approximates Ka up to
1982-fold faster than the previous state-of-the-art
iMinDEE/[Formula: see text]/[Formula: see text] algorithm.
Therefore, BBK* not only accelerates protein designs that
are possible with previous provable algorithms, but also
efficiently performs designs that are too large for previous
methods.},
Doi = {10.1089/cmb.2017.0267},
Key = {fds337044}
}
@article{fds336328,
Author = {Lavor, C and Liberti, L and Donald, B and Worley, B and Bardiaux, B and Malliavin, TE and Nilges, M},
Title = {Minimal NMR distance information for rigidity of protein
graphs},
Journal = {Discrete Applied Mathematics},
Year = {2018},
Month = {April},
url = {http://dx.doi.org/10.1016/j.dam.2018.03.071},
Abstract = {© 2018 Elsevier B.V. Nuclear Magnetic Resonance (NMR)
experiments provide distances between nearby atoms of a
protein molecule. The corresponding structure determination
problem is to determine the 3D protein structure by
exploiting such distances. We present a new order on the
atoms of the protein, based on information from the
chemistry of proteins and NMR experiments, which allows us
to formulate the problem as a combinatorial search.
Additionally, this order tells us what kind of NMR distance
information is crucial to understand the cardinality of the
solution set of the problem and its computational
complexity.},
Doi = {10.1016/j.dam.2018.03.071},
Key = {fds336328}
}
@article{fds328235,
Author = {Hallen, MA and Donald, BR},
Title = {CATS (Coordinates of Atoms by Taylor Series): protein design
with backbone flexibility in all locally feasible
directions},
Journal = {Bioinformatics},
Volume = {33},
Number = {14},
Pages = {i5-i12},
Year = {2017},
Month = {July},
url = {http://dx.doi.org/10.1093/bioinformatics/btx277},
Doi = {10.1093/bioinformatics/btx277},
Key = {fds328235}
}
@article{fds328236,
Author = {Jain, S and Jou, JD and Georgiev, IS and Donald, BR},
Title = {A critical analysis of computational protein design with
sparse residue interaction graphs.},
Journal = {PLoS computational biology},
Volume = {13},
Number = {3},
Pages = {e1005346},
Year = {2017},
Month = {March},
url = {http://dx.doi.org/10.1371/journal.pcbi.1005346},
Abstract = {Protein design algorithms enumerate a combinatorial number
of candidate structures to compute the Global Minimum Energy
Conformation (GMEC). To efficiently find the GMEC, protein
design algorithms must methodically reduce the
conformational search space. By applying distance and energy
cutoffs, the protein system to be designed can thus be
represented using a sparse residue interaction graph, where
the number of interacting residue pairs is less than all
pairs of mutable residues, and the corresponding GMEC is
called the sparse GMEC. However, ignoring some pairwise
residue interactions can lead to a change in the energy,
conformation, or sequence of the sparse GMEC vs. the
original or the full GMEC. Despite the widespread use of
sparse residue interaction graphs in protein design, the
above mentioned effects of their use have not been
previously analyzed. To analyze the costs and benefits of
designing with sparse residue interaction graphs, we
computed the GMECs for 136 different protein design problems
both with and without distance and energy cutoffs, and
compared their energies, conformations, and sequences. Our
analysis shows that the differences between the GMECs depend
critically on whether or not the design includes core,
boundary, or surface residues. Moreover, neglecting
long-range interactions can alter local interactions and
introduce large sequence differences, both of which can
result in significant structural and functional changes.
Designs on proteins with experimentally measured
thermostability show it is beneficial to compute both the
full and the sparse GMEC accurately and efficiently. To this
end, we show that a provable, ensemble-based algorithm can
efficiently compute both GMECs by enumerating a small number
of conformations, usually fewer than 1000. This provides a
novel way to combine sparse residue interaction graphs with
provable, ensemble-based algorithms to reap the benefits of
sparse residue interaction graphs while avoiding their
potential inaccuracies.},
Doi = {10.1371/journal.pcbi.1005346},
Key = {fds328236}
}
@article{fds326171,
Author = {Ojewole, AA and Jou, JD and Fowler, VG and Donald,
BR},
Title = {BBK* (Branch and bound over K*): A provable and efficient
ensemble-based algorithm to optimize stability and binding
affinity over large sequence spaces},
Journal = {Lecture notes in computer science},
Volume = {10229 LNCS},
Pages = {157-172},
Year = {2017},
Month = {January},
ISBN = {9783319569697},
url = {http://dx.doi.org/10.1007/978-3-319-56970-3_10},
Abstract = {© Springer International Publishing AG 2017.Protein design
algorithms that compute binding affinity search for
sequences with an energetically favorable free energy of
binding. Recent work shows that the following design
principles improve the biological accuracy of protein
design: ensemble-based design and continuous conformational
flexibility. Ensemble-based algorithms capture a measure of
entropic contributions to binding affinity, Ka. Designs
using backbone flexibility and continuous side-chain
flexibility better model conformational flexibility. A third
design principle, provable guarantees of accuracy, ensures
that an algorithm computes the best sequences defined by the
input model (i.e. input structures, energy function, and
allowed protein flexibility). However, previous provable
methods that model ensembles and continuous flexibility are
single-sequence algorithms, which are very costly: linear in
the number of sequences and thus exponential in the number
of mutable residues. To address these computational
challenges, we introduce a new protein design algorithm,
BBK*, that retains all aforementioned design principles yet
provably and efficiently computes the tightest-binding
sequences. A key innovation of BBK* is the multi-sequence
(MS) bound: BBK* efficiently computes a single provable
upper bound to approximate Ka for a combinatorial number of
sequences, and entirely avoids single-sequence computation
for all provably subop-timal sequences. Thus, to our
knowledge, BBK* is the first provable, ensemble-based Ka
algorithm to run in time sublinear in the number of
sequences. Computational experiments on 204 protein design
problems show that BBK* finds the tightest binding sequences
while approximating Ka for up to 105-fold fewer sequences
than exhaustive enumeration. Furthermore, for 51
protein-ligand design problems, BBK* provably approximates
Ka up to 1982-fold faster than the previous state-of-the-art
iMinDEE/A*/K* algorithm. Therefore, BBK* not only
accelerates protein designs that are possible with previous
provable algorithms, but also efficiently performs designs
that are too large for previous methods.},
Doi = {10.1007/978-3-319-56970-3_10},
Key = {fds326171}
}
@article{fds321932,
Author = {Zhou, Y and Donald, BR and Zeng, J},
Title = {Parallel Computational Protein Design.},
Journal = {Methods in molecular biology (Clifton, N.J.)},
Volume = {1529},
Pages = {265-277},
Year = {2017},
Month = {January},
Abstract = {Computational structure-based protein design (CSPD) is an
important problem in computational biology, which aims to
design or improve a prescribed protein function based on a
protein structure template. It provides a practical tool for
real-world protein engineering applications. A popular CSPD
method that guarantees to find the global minimum energy
solution (GMEC) is to combine both dead-end elimination
(DEE) and A* tree search algorithms. However, in this
framework, the A* search algorithm can run in exponential
time in the worst case, which may become the computation
bottleneck of large-scale computational protein design
process. To address this issue, we extend and add a new
module to the OSPREY program that was previously developed
in the Donald lab (Gainza et al., Methods Enzymol 523:87,
2013) to implement a GPU-based massively parallel A*
algorithm for improving protein design pipeline. By
exploiting the modern GPU computational framework and
optimizing the computation of the heuristic function for A*
search, our new program, called gOSPREY, can provide up to
four orders of magnitude speedups in large protein design
cases with a small memory overhead comparing to the
traditional A* search algorithm implementation, while still
guaranteeing the optimality. In addition, gOSPREY can be
configured to run in a bounded-memory mode to tackle the
problems in which the conformation space is too large and
the global optimal solution cannot be computed previously.
Furthermore, the GPU-based A* algorithm implemented in the
gOSPREY program can be combined with the state-of-the-art
rotamer pruning algorithms such as iMinDEE (Gainza et al.,
PLoS Comput Biol 8:e1002335, 2012) and DEEPer (Hallen et
al., Proteins 81:18-39, 2013) to also consider continuous
backbone and side-chain flexibility.},
Key = {fds321932}
}
@article{fds321933,
Author = {Ojewole, A and Lowegard, A and Gainza, P and Reeve, SM and Georgiev, I and Anderson, AC and Donald, BR},
Title = {OSPREY Predicts Resistance Mutations Using Positive and
Negative Computational Protein Design.},
Journal = {Methods in molecular biology (Clifton, N.J.)},
Volume = {1529},
Pages = {291-306},
Year = {2017},
Month = {January},
url = {http://dx.doi.org/10.1007/978-1-4939-6637-0_15},
Abstract = {Drug resistance in protein targets is an increasingly common
phenomenon that reduces the efficacy of both existing and
new antibiotics. However, knowledge of future resistance
mutations during pre-clinical phases of drug development
would enable the design of novel antibiotics that are robust
against not only known resistant mutants, but also against
those that have not yet been clinically observed.
Computational structure-based protein design (CSPD) is a
transformative field that enables the prediction of protein
sequences with desired biochemical properties such as
binding affinity and specificity to a target. The use of
CSPD to predict previously unseen resistance mutations
represents one of the frontiers of computational protein
design. In a recent study (Reeve et al. Proc Natl Acad Sci U
S A 112(3):749-754, 2015), we used our OSPREY (Open Source
Protein REdesign for You) suite of CSPD algorithms to
prospectively predict resistance mutations that arise in the
active site of the dihydrofolate reductase enzyme from
methicillin-resistant Staphylococcus aureus (SaDHFR) in
response to selective pressure from an experimental
competitive inhibitor. We demonstrated that our top
predicted candidates are indeed viable resistant mutants.
Since that study, we have significantly enhanced the
capabilities of OSPREY with not only improved modeling of
backbone flexibility, but also efficient multi-state design,
fast sparse approximations, partitioned continuous rotamers
for more accurate energy bounds, and a computationally
efficient representation of molecular-mechanics and
quantum-mechanical energy functions. Here, using SaDHFR as
an example, we present a protocol for resistance prediction
using the latest version of OSPREY. Specifically, we show
how to use a combination of positive and negative design to
predict active site escape mutations that maintain the
enzyme's catalytic function but selectively ablate binding
of an inhibitor.},
Doi = {10.1007/978-1-4939-6637-0_15},
Key = {fds321933}
}
@article{fds321934,
Author = {Pan, Y and Dong, Y and Zhou, J and Hallen, M and Donald, BR and Zeng, J and Xu, W},
Title = {cOSPREY: A Cloud-Based Distributed Algorithm for Large-Scale
Computational Protein Design.},
Journal = {Journal of Computational Biology},
Volume = {23},
Number = {9},
Pages = {737-749},
Year = {2016},
Month = {September},
url = {http://dx.doi.org/10.1089/cmb.2015.0234},
Abstract = {Finding the global minimum energy conformation (GMEC) of a
huge combinatorial search space is the key challenge in
computational protein design (CPD) problems. Traditional
algorithms lack a scalable and efficient distributed design
scheme, preventing researchers from taking full advantage of
current cloud infrastructures. We design cloud OSPREY
(cOSPREY), an extension to a widely used protein design
software OSPREY, to allow the original design framework to
scale to the commercial cloud infrastructures. We propose
several novel designs to integrate both algorithm and system
optimizations, such as GMEC-specific pruning, state search
partitioning, asynchronous algorithm state sharing, and
fault tolerance. We evaluate cOSPREY on three different
cloud platforms using different technologies and show that
it can solve a number of large-scale protein design problems
that have not been possible with previous
approaches.},
Doi = {10.1089/cmb.2015.0234},
Key = {fds321934}
}
@article{fds321935,
Author = {Gainza, P and Nisonoff, HM and Donald, BR},
Title = {Algorithms for protein design.},
Journal = {Current Opinion in Structural Biology},
Volume = {39},
Pages = {16-26},
Year = {2016},
Month = {August},
url = {http://dx.doi.org/10.1016/j.sbi.2016.03.006},
Abstract = {Computational structure-based protein design programs are
becoming an increasingly important tool in molecular
biology. These programs compute protein sequences that are
predicted to fold to a target structure and perform a
desired function. The success of a program's predictions
largely relies on two components: first, the input
biophysical model, and second, the algorithm that computes
the best sequence(s) and structure(s) according to the
biophysical model. Improving both the model and the
algorithm in tandem is essential to improving the success
rate of current programs, and here we review recent
developments in algorithms for protein design, emphasizing
how novel algorithms enable the use of more accurate
biophysical models. We conclude with a list of algorithmic
challenges in computational protein design that we believe
will be especially important for the design of therapeutic
proteins and protein assemblies.},
Doi = {10.1016/j.sbi.2016.03.006},
Key = {fds321935}
}
@article{fds321936,
Author = {Jou, JD and Jain, S and Georgiev, IS and Donald, BR},
Title = {BWM*: A Novel, Provable, Ensemble-based Dynamic Programming
Algorithm for Sparse Approximations of Computational Protein
Design.},
Journal = {Journal of Computational Biology},
Volume = {23},
Number = {6},
Pages = {413-424},
Year = {2016},
Month = {June},
url = {http://dx.doi.org/10.1089/cmb.2015.0194},
Abstract = {Sparse energy functions that ignore long range interactions
between residue pairs are frequently used by protein design
algorithms to reduce computational cost. Current dynamic
programming algorithms that fully exploit the optimal
substructure produced by these energy functions only compute
the GMEC. This disproportionately favors the sequence of a
single, static conformation and overlooks better binding
sequences with multiple low-energy conformations. Provable,
ensemble-based algorithms such as A* avoid this problem, but
A* cannot guarantee better performance than exhaustive
enumeration. We propose a novel, provable, dynamic
programming algorithm called Branch-Width Minimization*
(BWM*) to enumerate a gap-free ensemble of conformations in
order of increasing energy. Given a branch-decomposition of
branch-width w for an n-residue protein design with at most
q discrete side-chain conformations per residue, BWM*
returns the sparse GMEC in O([Formula: see text]) time and
enumerates each additional conformation in merely
O([Formula: see text]) time. We define a new measure, Total
Effective Search Space (TESS), which can be computed
efficiently a priori before BWM* or A* is run. We ran BWM*
on 67 protein design problems and found that TESS
discriminated between BWM*-efficient and A*-efficient cases
with 100% accuracy. As predicted by TESS and validated
experimentally, BWM* outperforms A* in 73% of the cases and
computes the full ensemble or a close approximation faster
than A*, enumerating each additional conformation in
milliseconds. Unlike A*, the performance of BWM* can be
predicted in polynomial time before running the algorithm,
which gives protein designers the power to choose the most
efficient algorithm for their particular design
problem.},
Doi = {10.1089/cmb.2015.0194},
Key = {fds321936}
}
@article{fds321937,
Author = {Hallen, MA and Donald, BR},
Title = {comets (Constrained Optimization of Multistate Energies by
Tree Search): A Provable and Efficient Protein Design
Algorithm to Optimize Binding Affinity and Specificity with
Respect to Sequence.},
Journal = {Journal of Computational Biology},
Volume = {23},
Number = {5},
Pages = {311-321},
Year = {2016},
Month = {May},
url = {http://dx.doi.org/10.1089/cmb.2015.0188},
Abstract = {Practical protein design problems require designing
sequences with a combination of affinity, stability, and
specificity requirements. Multistate protein design
algorithms model multiple structural or binding "states" of
a protein to address these requirements. comets provides a
new level of versatile, efficient, and provable multistate
design. It provably returns the minimum with respect to
sequence of any desired linear combination of the energies
of multiple protein states, subject to constraints on other
linear combinations. Thus, it can target nearly any
combination of affinity (to one or multiple ligands),
specificity, and stability (for multiple states if needed).
Empirical calculations on 52 protein design problems showed
comets is far more efficient than the previous state of the
art for provable multistate design (exhaustive search over
sequences). comets can handle a very wide range of protein
flexibility and can enumerate a gap-free list of the best
constraint-satisfying sequences in order of objective
function value.},
Doi = {10.1089/cmb.2015.0188},
Key = {fds321937}
}
@article{fds321938,
Author = {Hallen, MA and Jou, JD and Donald, BR},
Title = {LUTE (Local unpruned tuple expansion): Accurate continuously
flexible protein design with general energy functions and
rigid-rotamer-like efficiency},
Journal = {Lecture notes in computer science},
Volume = {9649},
Pages = {122-136},
Year = {2016},
Month = {January},
ISBN = {9783319319568},
url = {http://dx.doi.org/10.1007/978-3-319-31957-5_9},
Abstract = {© Springer International Publishing Switzerland 2016.Most
protein design algorithms search over discrete conformations
and an energy function that is residue-pairwise, i.e., a sum
of terms that depend on the sequence and conformation of at
most two residues. Although modeling of continuous
flexibility and of non-residuepairwise energies
significantly increases the accuracy of protein design,
previous methods to model these phenomena add a significant
asymptotic cost to design calculations. We now remove this
cost by modeling continuous flexibility and
non-residue-pairwise energies in a form suitable for direct
input to highly efficient, discrete combinatorial
optimization algorithms like DEE/A* or Branch-Width
Minimization. Our novel algorithm performs a local unpruned
tuple expansion (LUTE), which can efficiently represent both
continuous flexibility and general, possibly non-pairwise
energy functions to an arbitrary level of accuracy using a
discrete energy matrix. We show using 47 design calculation
test cases that LUTE provides a dramatic speedup in both
single-state and multistate continuously flexible
designs.},
Doi = {10.1007/978-3-319-31957-5_9},
Key = {fds321938}
}
@article{fds236348,
Author = {Roberts, KE and Gainza, P and Hallen, MA and Donald,
BR},
Title = {Fast gap-free enumeration of conformations and sequences for
protein design.},
Journal = {Proteins: Structure, Function and Bioinformatics},
Volume = {83},
Number = {10},
Pages = {1859-1877},
Year = {2015},
Month = {October},
ISSN = {0887-3585},
url = {http://dx.doi.org/10.1002/prot.24870},
Abstract = {Despite significant successes in structure-based
computational protein design in recent years, protein design
algorithms must be improved to increase the biological
accuracy of new designs. Protein design algorithms search
through an exponential number of protein conformations,
protein ensembles, and amino acid sequences in an attempt to
find globally optimal structures with a desired biological
function. To improve the biological accuracy of protein
designs, it is necessary to increase both the amount of
protein flexibility allowed during the search and the
overall size of the design, while guaranteeing that the
lowest-energy structures and sequences are found.
DEE/A*-based algorithms are the most prevalent provable
algorithms in the field of protein design and can provably
enumerate a gap-free list of low-energy protein
conformations, which is necessary for ensemble-based
algorithms that predict protein binding. We present two
classes of algorithmic improvements to the A* algorithm that
greatly increase the efficiency of A*. First, we analyze the
effect of ordering the expansion of mutable residue
positions within the A* tree and present a dynamic residue
ordering that reduces the number of A* nodes that must be
visited during the search. Second, we propose new methods to
improve the conformational bounds used to estimate the
energies of partial conformations during the A* search. The
residue ordering techniques and improved bounds can be
combined for additional increases in A* efficiency. Our
enhancements enable all A*-based methods to more fully
search protein conformation space, which will ultimately
improve the accuracy of complex biomedically relevant
designs.},
Doi = {10.1002/prot.24870},
Key = {fds236348}
}
@article{fds321939,
Author = {Paprotny, I and Levey, CG and Wright, PK and Donald,
BR},
Title = {Turning-rate selective control : A new method for
independent control of stress-engineered MEMS
microrobots},
Volume = {8},
Pages = {321-328},
Year = {2013},
Month = {January},
ISBN = {9780262519687},
Abstract = {© 2013 Massachusetts Institute of Technology.We present a
novel method for independently controlling multiple
stress-engineered MEMS microrobots called MicroStressBots
through a single, global, control signal. We call this
technique Turning-rate Selective Control (TSC). To implement
TSC, we fabricated MicroStressBots that exhibit different
turning rates. TSC specifically exploits these designed
variations in turning rates between individual microrobots
to differentiate their motion, and thereby obtain individual
control. Thus, even though all robots move simultaneously,
and are identical except for their turning rates, TSC can
individually and independently position the robots' centers
of rotation within a planar configuration space. This allows
the individual robots to be independently maneuverable to
within a distance r from an arbitrary desired goal point in
the plane. The distance r is the turning radius
(approximately half of a microrobot width). We describe the
theory behind TSC and, by using fabricated microrobots, show
experimental results that confirm the feasibility of TSC for
controlling multiple MicroStressBots through a single,
global, control signal. Our paper further validates the
multi-microrobot control paradigm called Global Control
Selective Response that we first introduced in 2007. We
conclude by discussing how TSC can extend the maximum number
of independently controllable MicroStressBots.},
Key = {fds321939}
}
@article{fds341950,
Author = {Donald, BR and Levey, CG and Paprotny, I},
Title = {Assembly of planar structures by parallel actuation of Mems
microrobots},
Journal = {Technical Digest Solid State Sensors, Actuators, and
Microsystems Workshop},
Pages = {202-207},
Year = {2008},
Month = {January},
ISBN = {9780964002494},
Abstract = {© 2008 TRF. Parallel motion and cooperation of multiple
microrobots has many potential applications, including
microassembly. In this paper, we present designs, theory and
the results of fabrication and testing for an untethered
multi-microrobotic system of stressengineered MEMS
microrobots that implements a novel microassembly scheme.
Our work constitutes the first implementation of an
untethered, mobile multi-microrobotic system. The robots are
designed such that multiple devices can be independently
maneuvered using a single, global control signal. We used a
novel stress-engineering fabrication process to build 15
microrobots and used these to demonstrate microassembly of
five types of planar structures from two classes of initial
conditions. The final assemblies matched their target shapes
by 96% (average), measured as the percentage of the area of
the target shape covered by the assembled
structure.},
Key = {fds341950}
}
@article{fds236461,
Author = {Donald, BR and Levey, CG and McGray, CD and Paprotny, I and Rus,
D},
Title = {A steerable, untethered, 250 × 60 µm MEMS mobile
micro-robot},
Journal = {Springer Tracts in Advanced Robotics},
Volume = {28},
Pages = {337-356},
Year = {2007},
Month = {January},
ISBN = {9783540481102},
ISSN = {1610-7438},
url = {http://dx.doi.org/10.1007/978-3-540-48113-3_31},
Abstract = {© Springer-Verlag Berlin Heidelberg 2007. We present a
steerable, electrostatic, untethered, MEMS micro-robot, with
dimensions of 60 µm by 250 µm by 10 µm. This micro-robot
is 1 to 2 orders of magnitude smaller in size than previous
micro-robotic systems. The device consists of a curved,
cantilevered steering arm, mounted on an untethered scratch
drive actuator. These two components are fabricated
monolithically from the same sheet of conductive
polysilicon, and receive a common power and control signal
through a capacitive coupling with an underlying electrical
grid. All locations on the grid receive the same power and
control signal, so that the devices can be operated without
knowledge of their position on the substrate and without
constraining rails or tethers. Control and power delivery
waveforms are broadcast to the device through the capacitive
power coupling, and are decoded by the electromechanical
response of the device body. Individual control of the
component actuators provides two distinct motion gaits
(forward motion and turning), which together allow full
coverage of a planar workspace (the robot is globally
controllable). These MEMS micro-robots demonstrate turning
error of less than 3.7°/mm during forward motion, turn with
radii as small as 176 µm, and achieve speeds of over 200
µsec, with an average step size of 12 nm. They have been
shown to operate open-loop for distances exceeding 35 cm
without failure, and can be controlled through teleoperation
to navigate complex paths.},
Doi = {10.1007/978-3-540-48113-3_31},
Key = {fds236461}
}
@article{jcb-poly06,
Author = {L. Wang and R. Mettu and B. R. Donald},
Title = {A Polynomial-Time Algorithm for {\em de novo} Protein
Backbone Structure Determination from {NMR}
Data},
Journal = {Journal of Computational Biology},
Volume = {13},
Number = {7},
Pages = {1276--1288},
Year = {2006},
Key = {jcb-poly06}
}
@article{jmems05,
Author = {B. R. Donald and C. Levey and C. McGray and I. Paprotny and D. Rus},
Title = {An Untethered, Electrostatic, Globally-Controllable {MEMS}
Micro-Robot},
Journal = {Journal of Microelectromechanical Systems},
Year = {2005},
Key = {jmems05}
}
@inproceedings{csb05-poly,
Author = {L. Wang and R. Mettu and B. R. Donald},
Title = {An Algebraic Geometry Approach to Protein Backbone Structure
Determination from {NMR} Data},
Pages = {235--246},
Booktitle = {Proceedings of the {IEEE} Computational Systems
Bioinformatics Conference ({CSB})},
Address = {Stanford, CA},
Year = {2005},
Key = {csb05-poly}
}
@inproceedings{isrr-05,
Author = {B. R. Donald and C. Levey and C. McGray and I. Paprotny and D. Rus},
Title = {A Steerable, Untethered, 250 $\times$ 60 $\mu$m {MEMS}
Mobile Micro-Robot},
Booktitle = {Proceedings of the 12th {\it International Symposium of
Robotics Research (ISRR)}},
Address = {San Francisco, CA.},
Year = {2005},
Key = {isrr-05}
}
@inproceedings{wafr04,
Author = {B. R. Donald},
Title = {Plenary lecture: {Algorithmic} Challenges in Structural
Molecular Biology and Proteomics},
Pages = {1--10},
Booktitle = {Proceedings of the Sixth International Workshop on the
Algorithmic Foundations of Robotics (WAFR)},
Publisher = {University of Utrecht},
Address = {Utrecht/Zeist, The Netherlands},
Year = {2004},
Key = {wafr04}
}
@inproceedings{recomb-04langmead-poster,
Author = {C. Langmead and B. R. Donald},
Title = {High-Throughput 3{D} homology Detection via {NMR} Resonance
Assignment},
Series = {Eighth Annual International Conference on Research in
Computational Molecular Biology ({RECOMB})},
Pages = {522},
Booktitle = {Currents in Computational Molecular Biology,
2004},
Address = {San Diego},
Editor = {A. Gramada and P. Bourne},
Year = {2004},
Key = {recomb-04langmead-poster}
}
@inproceedings{recomb-04a,
Author = {A. Yan and C. Langmead and B. R. Donald},
Title = {A Probability-Based Similarity Measure for Saupe Alignment
Tensors with Applications to Residual Dipolar Couplings in
{NMR} Structural Biology},
Series = {Eighth Annual International Conference on Research in
Computational Molecular Biology ({RECOMB})},
Pages = {437--438},
Booktitle = {Currents in Computational Molecular Biology,
2004},
Address = {San Diego},
Editor = {A. Gramada and P. Bourne},
Year = {2004},
Key = {recomb-04a}
}
@inproceedings{WangDonald-csb04,
Author = {L. Wang and B. R. Donald},
Title = {Analysis of a Systematic Search-Based Algorithm for
Determining Protein Backbone Structure from a Minimal Number
of Residual Dipolar Couplings},
Pages = {319--330},
Booktitle = {Proceedings of the {IEEE} Computational Systems
Bioinformatics Conference ({CSB})},
Address = {Stanford, CA},
Year = {2004},
Key = {WangDonald-csb04}
}
@inproceedings{ieeecsb-langmead03,
Author = {Langmead, CJ and Donald, BR},
Title = {3D structural homology detection via unassigned residual
dipolar couplings.},
Journal = {Proceedings / IEEE Computer Society Bioinformatics
Conference. IEEE Computer Society Bioinformatics
Conference},
Volume = {2},
Pages = {209-217},
Booktitle = {Proceedings of the {IEEE} Computer Society Bioinformatics
Conference ({CSB})},
Address = {Stanford},
Year = {2003},
Month = {January},
ISSN = {1555-3930},
Abstract = {Recognition of a protein's fold provides valuable
information about its function. While many sequence-based
homology prediction methods exist, an important challenge
remains: two highly dissimilar sequences can have similar
folds-- how can we detect this rapidly, in the context of
structural genomics? High-throughput NMR experiments,
coupled with novel algorithms for data analysis, can address
this challenge. We report an automated procedure for
detecting 3D structural homologies from sparse, unassigned
protein NMR data. Our method identifies the 3D structural
models in a protein structural database whose geometries
best fit the unassigned experimental NMR data. It does not
use sequence information and is thus not limited by sequence
homology. The method can also be used to confirm or refute
structural predictions made by other techniques such as
protein threading or sequence homology. The algorithm runs
in O(pnk(3)) time, where p is the number of proteins in the
database, n is the number of residues in the target protein,
and k is the resolution of a rotation search. The method
requires only uniform (15)N-labelling of the protein and
processes unassigned H(N)-(15)N residual dipolar couplings,
which can be acquired in a couple of hours. Our experiments
on NMR data from 5 different proteins demonstrate that the
method identifies closely related protein folds, despite
low-sequence homology between the target protein and the
computed model.},
Key = {ieeecsb-langmead03}
}
@inproceedings{ieeecsb03-wang,
Author = {Wang, L and Mettu, RR and Lilien, R and Donald, BR},
Title = {An exact algorithm for determining protein backbone
structure from NH residual dipolar couplings},
Journal = {Proceedings of the 2003 IEEE Bioinformatics Conference, CSB
2003},
Pages = {611-612},
Booktitle = {Proceedings of the {IEEE} Computer Society Bioinformatics
Conference ({CSB})},
Address = {Stanford},
Year = {2003},
Month = {January},
ISBN = {0769520006},
url = {http://dx.doi.org/10.1109/CSB.2003.1227422},
Abstract = {© 2003 IEEE.We have developed a novel algorithm for protein
backbone structure determination using global orientational
restraints on internuclear bond vectors derived from
residual dipolar couplings (RDCs) measured in solution NMR.
The algorithm is a depth-first search (DPS) strategy that is
built upon two low-degree polynomial equations for computing
the backbone (φ, ψ) angles, exactly and in constant time,
from two bond vectors in consecutive peptide
planes.},
Doi = {10.1109/CSB.2003.1227422},
Key = {ieeecsb03-wang}
}
@article{oneil-03,
Author = {R. O'Neil and R. Lilien and B. R. Donald and R. Stroud and A. Anderson},
Title = {Crystal structure of Dihydrofolate Reductase-Thymidylate
Synthase ({DHFR}-{TS}) from {{\em Cryptosporidium
hominis}}},
Year = {2003},
Key = {oneil-03}
}
@article{jmems03,
Author = {B. R. Donald and C. Levey and C. McGray and D. Rus and M.
Sinclair},
Title = {Power Delivery and Locomotion of Untethered
Micro-Actuators},
Journal = {Jour. of Microelectromechanical Systems},
Volume = {10},
Number = {6},
Pages = {947--959},
Year = {2003},
Key = {jmems03}
}
@inproceedings{isrr-03,
Author = {B. R. Donald and C. Levey and C. McGray and D. Rus and M.
Sinclair},
Title = {Untethered Micro-Actuators for Autonomous Micro-robot
Locomotion: Design, Fabrication, Control, and
Performance},
Booktitle = {Proceedings of the 11th {\it International Symposium of
Robotics Research}},
Address = {Siena, Italy},
Year = {2003},
Key = {isrr-03}
}
@inproceedings{recomb02-poster,
Author = {R. Lilien and A. Anderson and B. Donald},
Title = {Modeling Protein Flexibility for Structure-Based Active Site
Redesign},
Series = {The Sixth Annual International Conference on Research in
Computational Molecular Biology (RECOMB)},
Pages = {122-123},
Booktitle = {Currents in Computational Molecular Biology},
Address = {Washington DC},
Editor = {L. Florea and others},
Year = {2002},
Key = {recomb02-poster}
}
@inproceedings{lilien01,
Author = {R. Lilien and A. Anderson and B. R. Donald},
Title = {Modeling of Protein Flexibility for Computational Active
Site Redesign},
Booktitle = {The 16th Annual National M.D./Ph.D.~Conference},
Organization = {Given Institute , Aspen, Colorado},
Institution = {Given Institute , Aspen, Colorado},
Year = {2001},
Key = {lilien01}
}
@inproceedings{recomb00,
Author = {C. Bailey-Kellogg and A. Widge and J. J. {Kelley III} and M.
J. Berardi and J. H. Bushweller and B. R.
Donald},
Title = {The {NOESY} {Jigsaw}: Automated Protein Secondary Structure
and Main-Chain Assignment from Sparse, Unassigned {NMR}
Data},
Pages = {33--44},
Booktitle = {The Fourth Annual International Conference on Research in
Computational Molecular Biology ({RECOMB-2000})},
Year = {2000},
Key = {recomb00}
}
@inproceedings{BaileyKelloggZhaoDonald00,
Author = {C. Bailey-Kellogg and F. Zhao and B. R. Donald},
Title = {Spatial Aggregation in Scientific Data Mining},
Booktitle = {Proceedings of the First {SIAM} Conference on Computational
Science and Engineering},
Address = {Washington, DC},
Year = {2000},
Key = {BaileyKelloggZhaoDonald00}
}
@inproceedings{GariepyRusDonald99,
Author = {B. R. Donald and L. Gariepy and D. Rus},
Title = {Experiments in Constrained Prehensile Manipulation:
Distributed Manipulation with Ropes},
Booktitle = {Proceedings of the International Symposium on Experimental
Robotics {ISER}},
Address = {Sydney, Australia},
Year = {1999},
Key = {GariepyRusDonald99}
}
@article{BohringerDonaldMacDonald97A,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and N.~C.~MacDonald},
Title = {{\em Programmable Vector Fields for Distributed
Manipulation, with Applications to MEMS Actuator Arrays and
Vibratory Parts Feeders}},
Journal = {International Journal of Robotics Research},
Volume = {18},
Number = {2},
Year = {1999},
Key = {BohringerDonaldMacDonald97A}
}
@inproceedings{icra99b,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and F.~Lamiraux and L.~Kavraki},
Title = {Part Orientation with One or Two Stable Equilibria Using
Programmable Force Fields},
Booktitle = {IEEE International Conference on Robotics and Automation,
Workshop on Distributed Manipulation},
Year = {1999},
Key = {icra99b}
}
@inproceedings{BohringerLamirauxKavrakiDonald99,
Author = {K.-F. B{\"o}hringer and B. R. Donald and F. Lamiraux and L.
Kavraki},
Title = {Part Orientation with One or Two Stable Equilibria Using
Programmable Vector Fields},
Booktitle = {{IEEE} International Conference on Robotics and Automation,
Workshop on Distributed Manipulation},
Address = {Detroit},
Year = {1999},
Key = {BohringerLamirauxKavrakiDonald99}
}
@inproceedings{isrr99,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and F.~Lamiraux and L.~Kavraki},
Title = {A Single Universal Force Field Can Uniquely Pose Any Part Up
To Symmetry},
Booktitle = {9th International Symposium of Robotics Research
(ISRR)},
Year = {1999},
Key = {isrr99}
}
@inproceedings{GariepyRusDonald99B,
Author = {B. R. Donald and L. Gariepy and D. Rus},
Title = {Experiments in Constrained Prehensile Manipulation:
Distributed Manipulation with Ropes},
Booktitle = {{IEEE} International Conference on Robotics and Automation,
Workshop on Distributed Manipulation},
Address = {Detroit},
Year = {1999},
Key = {GariepyRusDonald99B}
}
@inproceedings{icra99a,
Author = {J.~Suh and B.~Darling and K.-F.~B{\"o}hringer and B.~R.~Donald and H.~Baltes and G.~Kovacs},
Title = {{CMOS} Integrated Organic Ciliary Actuator Array as a
General-Purpose Micromanipulation Tool},
Booktitle = {IEEE International Conference on Robotics and Automation,
Workshop on Distributed Manipulation},
Year = {1999},
Key = {icra99a}
}
@inproceedings{icra98,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald},
Title = {Micro Contacts and Micro Manipulation with {MEMS} Actuator
Arrays},
Booktitle = {IEEE International Conference on Robotics and Automation,
Workshop on Modeling, Contact Analysis, and Simulation of
Mechanical Systems in Robotics and Manufacturing},
Year = {1998},
Key = {icra98}
}
@inproceedings{BohringerDonald98,
Author = {K.-F. B{\"o}hringer and B. R. Donald},
Title = {Algorithmic {MEMS}},
Booktitle = {Proceedings of the 3rd International Workshop on the
Algorithmic Foundations of Robotics {WAFR}},
Address = {Houston, TX},
Year = {1998},
Key = {BohringerDonald98}
}
@inproceedings{BohringerDonaldHalperin97A,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and D.~Halperin},
Title = {{\em On the Area Bisectors of a Polygon}},
Booktitle = {Second CGC Workshop on Computational Geometry},
Organization = {Duke University},
Institution = {Duke University},
Address = {Durham, NC},
Year = {1997},
Month = {October},
Key = {BohringerDonaldHalperin97A}
}
@article{dcg97,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and D.~Halperin},
Title = {On the Area Bisectors of a Polygon},
Journal = {Discrete and Computational Geometry},
Volume = {22},
Pages = {269--285},
Year = {1997},
Key = {dcg97}
}
@inproceedings{BohringerDonaldHalperin97B,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and D.~Halperin},
Title = {The Area Bisectors of a Polygon and Force Equilibria in
Programmable Vector Fields},
Pages = {457--459},
Booktitle = {{\em Proc.~$13^{{\rm th}}$ ACM Symposium on Computational
Geometry}},
Address = {Nice, France},
Year = {1997},
Key = {BohringerDonaldHalperin97B}
}
@inproceedings{BohringerDonaldMacDonald96A,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and N.
MacDonald},
Title = {Upper and lower bounds for programmable vector fields with
applications to MEMS and vibratory plate parts
feeders},
Booktitle = {Proc.~{\em International Workshop on the Algorithmic
Foundations of Robotics (WAFR)}},
Address = {Toulouse, France},
Year = {1996},
Month = {July},
Key = {BohringerDonaldMacDonald96A}
}
@inproceedings{BohringerDonaldMacDonald96B,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and N.~C.~MacDonald},
Title = {Classification and Lower Bounds for MEMS Arrays and
Vibratory Parts Feeders: What Programmable Vector Fields Can
(and Cannot) Do},
Booktitle = {{\em IEEE International Conference on Robotics and
Automation (ICRA)}},
Address = {Minneapolis, Minnesota},
Year = {1996},
Month = {April},
Key = {BohringerDonaldMacDonald96B}
}
@inproceedings{BriggsDonald96,
Author = {A. Briggs and B. R. Donald},
Title = {Robust Geometric Algorithms for Sensor Planning},
Booktitle = {Proceedings of the International Workshop on the Algorithmic
Foundations of Robotics {WAFR}},
Address = {Toulouse, France},
Year = {1996},
Key = {BriggsDonald96}
}
@article{Donald95A,
Author = {B.~R.~Donald},
Title = {Information Invariants in Robotics},
Journal = {Artificial Intelligence},
Volume = {72},
Pages = {217--304},
Year = {1995},
Month = {January},
Key = {Donald95A}
}
@inproceedings{ISER95,
Author = {K.-F. B{\"o}hringer and R. Brown and B. R. Donald and J.
Jennings and D. Rus},
Title = {Distributed Robotic Manipulation: Experiments in
Minimalism},
Booktitle = {{\em International Symposium on Experimental Robotics}
(Experimental Robotics IV, Lecture Notes in Control and
Information Sciences 223; ed. O. Khatib et al., Springer
Verlag (Berlin) 1997. pp. 11-25)},
Address = {Stanford, CA},
Year = {1995},
Key = {ISER95}
}
@inproceedings{JenningsRusDonald95,
Author = {D. Rus and B. R. Donald and J. Jennings},
Title = {Moving Furniture with Teams of Autonomous Mobile
Robots},
Pages = {235--242},
Booktitle = {Proc. {IEEE}/Robotics Society of Japan International
Workshop on Intelligent Robots and Systems},
Address = {Pittsburgh, PA},
Year = {1995},
Key = {JenningsRusDonald95}
}
@inproceedings{Donald95,
Author = {B. R. Donald},
Title = {Distributed Robotic Manipulation: Experiments in
Minimalism},
Booktitle = {Proceedings of the International Symposium on Experimental
Robotics},
Address = {Stanford, CA},
Year = {1995},
Key = {Donald95}
}
@inproceedings{BohringerDonaldMacDonaldMihailovich94B,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and Noel C. MacDonald and R. Mihailovich},
Title = {A Theory of Manipulation and Control for Microfabricated
Actuator Arrays},
Booktitle = {Proc.~$7^{{\rm th}}$ IEEE Workshop on Micro Electro
Mechanical Systems ({\sc MEMS'94})},
Address = {Kanagawa, Japan},
Year = {1994},
Month = {January},
Key = {BohringerDonaldMacDonaldMihailovich94B}
}
@inproceedings{DonaldJenningsRus94A,
Author = {B.~R.~Donald and J.~Jennings and D.~Rus},
Title = {Information Invariants for Distributed Manipulation},
Booktitle = {{\em The First Workshop on the Algorithmic Foundations of
Robotics (WAFR)}},
Address = {San Fransisco, CA},
Year = {1994},
Key = {DonaldJenningsRus94A}
}
@article{PaiDonald93,
Author = {B. R. Donald and D. Pai},
Title = {The Motion of Planar Compliantly-Connected Rigid Bodies in
Contact, with Applications to Automatic Fastening},
Journal = {International Journal of Robotics Research},
Volume = {12},
Number = {4},
Pages = {307--338},
Year = {1993},
Key = {PaiDonald93}
}
@inproceedings{BrownChewDonald93,
Author = {R. Brown and P. Chew and B. R. Donald},
Title = {Mobile Robots, Map-making, Shape Metrics, and
Localization},
Booktitle = {Proceedings of the International Association of Science and
Technology for Development ({IASTED}) International
Conference on Robotics and Manufacturing},
Address = {Oxford, England},
Year = {1993},
Key = {BrownChewDonald93}
}
@inproceedings{JenningsRusDonald93B,
Author = {J. Jennings and D. Rus and B. R. Donald},
Title = {Experimental Information Invariants for Cooperating
Autonomous Mobile Robots},
Booktitle = {Proceedings of the International Joint Conference on
Artificial Intelligence ({IJCAI}) Workshop on Dynamically
Interacting Robots},
Address = {Chambery, France},
Year = {1993},
Key = {JenningsRusDonald93B}
}
@inproceedings{JenningsRusDonald93A,
Author = {B. R. Donald and J. Jennings and D. Rus},
Title = {Towards a Theory of Information Invariants for Cooperating
Autonomous Mobile Robots},
Booktitle = {Proceedings of the International Symposium of Robotics
Research {ISRR}},
Address = {Hidden Valley, PA},
Year = {1993},
Key = {JenningsRusDonald93A}
}
@article{ai-robotics-92,
Author = {B. R. Donald},
Title = {On Planning: What is to be Done?},
Journal = {Communication and Cognition-Artificial Intelligence},
Volume = {9},
Number = {1},
Pages = {89--132},
Booktitle = {Special Issue on {AI} and Robotics},
Year = {1992},
Key = {ai-robotics-92}
}
@article{ieee-92,
Author = {B. R. Donald},
Title = {Robot Motion Planning},
Journal = {{IEEE} Trans. on Robotics and Automation},
Volume = {8},
Number = {2},
Year = {1992},
Key = {ieee-92}
}
@inproceedings{CannyResslerDonald92,
Author = {J. Canny and B. R. Donald and G. Ressler},
Title = {A Rational Rotation Method for Robust Geometric
Algorithms},
Pages = {251--260},
Booktitle = {Proc. {ACM} Symposium on Computational Geometry},
Address = {Berlin},
Year = {1992},
Key = {CannyResslerDonald92}
}
@inproceedings{DonaldJennings91B,
Author = {B.~R.~Donald and J.~Jennings},
Title = {Perceptual Limits, Perceptual Equivalence Classes, and a
Robot's Sensori-Computational Capabilities},
Pages = {1397--1405},
Booktitle = {IEEE/Robotics Society of Japan International Workshop on
Intelligent Robots and Systems},
Address = {Osaka, Japan},
Year = {1991},
Month = {November},
Key = {DonaldJennings91B}
}
@inproceedings{JenningsDonald91A,
Author = {J. Jennings and B. R. Donald},
Title = {Programming Autonomous Agents: A theory of Perceptual
Equivalence},
Booktitle = {Proceedings of the 1st {AAAI} Fall Symposium on Sensory
Aspects of Robotic Intelligence},
Address = {Asilomar, CA},
Year = {1991},
Key = {JenningsDonald91A}
}
@inproceedings{XavierDonald89B,
Author = {B. R. Donald and P. Xavier},
Title = {A Provably Good Approximation Algorithm for Optimal-Time
Trajectory Planning},
Pages = {958--964},
Booktitle = {Proc. {IEEE} International Conference on Robotics and
Automation},
Address = {Scottsdale, AZ},
Year = {1989},
Key = {XavierDonald89B}
}
@article{fds331370,
Author = {Donald, BR},
Title = {The complexity of planar compliant motion planning Under
Uncertainty},
Journal = {Proceedings of the 4th Annual Symposium on Computational
Geometry, SCG 1988},
Pages = {309-318},
Year = {1988},
Month = {January},
ISBN = {0897912705},
url = {http://dx.doi.org/10.1145/73393.73425},
Abstract = {© 1988 ACM. We consider the computational complexity of
planning compliant motions in the plane, given geometric
bounds on the uncertainty in sensing and control. We can
give efficient algorithms for generating and verifying
compliant motion strategies that are guaranteed to succeed
as long as the sensing and control uncertainties lie within
the specified bounds. We also consider the case where a
compliant motion plan is required to succeed over some
parametric family of geometries. While these problems are
known to be intractable in 3D, we identify tractable
subclasses in the plane.},
Doi = {10.1145/73393.73425},
Key = {fds331370}
}
@inproceedings{Donald88,
Author = {B. R. Donald},
Title = {The Complexity of Planar Compliant Motion Planning with
Uncertainty},
Pages = {309--318},
Booktitle = {Proc. 4th {ACM} Symposium on Computational
Geometry},
Address = {Urbana. IL},
Year = {1988},
Key = {Donald88}
}
@inproceedings{CannyDonald87,
Author = {Canny, J and Donald, B},
Title = {Simplified voronoi diagrams},
Journal = {Proceedings of the 3rd Annual Symposium on Computational
Geometry, SCG 1987},
Pages = {153-161},
Booktitle = {Proc. Third {ACM} Symposium on Computational
Geometry},
Address = {Waterloo, Ontario},
Year = {1987},
Month = {October},
ISBN = {0897912314},
url = {http://dx.doi.org/10.1145/41958.41974},
Abstract = {© 1987 ACM. We are interested in Voronoi diagrams as a tool
in robot path planning, where the search for a path in anr
dimensional space may be simplified to a search on an r - 1
dimensional Voronoi diagram. We define a Voronoidiagram V
based on a measure of distance which is not a true metric.
This formulation has lower algebraiccomplexity than the
usual definition, which is a considerable advantage in
motion planning problems with manydegrees of freedom. In its
simplest form, the measure of distance between a point and a
polytope is the maximum of the distances of the point from
the half-spaces which pass through faces of the polytope.
More generally,the measure is defined in configuration
spaces which represent rotation. The Voronoi diagram defined
using this distance measure is no longer a strong
deformation retract of free space, but it has the following
usefulproperty, any path through free space which starts and
ends on the diagram ran be continuously deformed so that it
lies entirely on the diagram. Thus it is still complete for
motion planning, but it lias lower algebraiccomplexity than
a diagram based on the euclidean metric.},
Doi = {10.1145/41958.41974},
Key = {CannyDonald87}
}
@inproceedings{Donald86A,
Author = {B. R. Donald},
Title = {A Theory of Error Detection and Recovery: Robot Motion
Planning with Uncertainty in the Geometric Models of the
Robot and Environment},
Booktitle = {Proceedings of the International Workshop on Geometric
Reasoning},
Address = {Oxford University, England},
Year = {1986},
Key = {Donald86A}
}
@inproceedings{Donald85,
Author = {Donald, BR},
Title = {On motion planning with six degrees of freedoms solving the
intersection problems in configuration space},
Journal = {Proceedings Ieee International Conference on Robotics and
Automation},
Pages = {536-541},
Booktitle = {Proc. {IEEE} International Conference on Robotics and
Automation},
Address = {St. Louis, Missouri},
Year = {1985},
Month = {January},
ISBN = {0818606150},
url = {http://dx.doi.org/10.1109/ROBOT.1985.1087334},
Abstract = {© 1985 IEEE. The Movers' problem ia to find a continuous,
collision-free path for a moving object through an
environment containing obstacles. The classical formulation
of the three-dimensional Movers' problem is as follows:
given an arbitrary rigid polyhedral moving object P with
three translationl and three rotational degrees of' freedom,
find a continuous, collision-free path taking P from some
initial configuration to a desired goal configuration. The
six degree of freedom Movers' problem may be transformed
into a point navigation problem in a six-dimensional
configuration space (called C-S pace). The C-Space
obstacles, which characterize the physically unachievable
configurations, are directly represented by six-dimensional
manifolds whose boundaries are five dimensional C-surfaces.
By characterizing these surfaces and their intersections,
collision-free paths may be found by the closure of three
operators which (i) slide along 5-dinieiisional level
C-surfaces parallel to C-S pace obstacles; (ii) slide along
1-to A-dimensional intersections of level C-surfaces; and
(iii) jump between 6-dimonsional obstacles. We show how to
construct and represent C-surfaces and their intersection
manifold?. We also demonstrate how to intersect trajectories
with the boundaries of C-Space obstacles. The theory and
representations we develop extend to Cartesian manipulators
with six degrees of freedom.},
Doi = {10.1109/ROBOT.1985.1087334},
Key = {Donald85}
}
@inproceedings{Donald83,
Author = {B. R. Donald},
Title = {The Mover's Problem in Automated Structural
Design},
Booktitle = {Proc. Harvard Computer Graphics Conference},
Address = {Cambridge, MA},
Year = {1983},
Key = {Donald83}
}
%% Papers Accepted
@misc{gordon04-poster-langmead,
Author = {C. Langmead and B. R. Donald},
Title = {A Framework for Automated {NMR} Resonance Assignments and
3{D} Structural Homology Detection},
Address = {Ventura, CA},
Year = {2004},
Key = {gordon04-poster-langmead}
}
@misc{gordon04-poster-wang,
Author = {L. Wang and R. Mettu and R. Lilien and A. Yan and B. R.
Donald},
Title = {Exact Solutions for Internuclear Vectors and Dihedral Angles
from Two {RDC}s and Their Application in a Systematic Search
Algorithm for Determining Protein Backbone
Structure},
Address = {Ventura, CA},
Year = {2004},
Key = {gordon04-poster-wang}
}
@misc{acs03-poster-anderson,
Author = {A. Anderson and R. Lilien and V. Popov and B. R.
Donald},
Title = {Ensembles of Active Site Conformations Allow Structure-Based
Redesign and Drug Design},
Address = {New Orleans},
Year = {2003},
Key = {acs03-poster-anderson}
}
@misc{ismb00-poster-langmead,
Author = {C. J. Langmead and B. R. Donald},
Title = {Time-frequency Analysis of Protein {NMR}
Data},
Year = {2000},
Key = {ismb00-poster-langmead}
}
@misc{ismb00-poster-cbk,
Author = {C. Bailey-Kellogg and A. Widge and J. J. {Kelley III} and M.
J. Berardi and J. H. Bushweller and B. R.
Donald},
Title = {The {NOESY} {Jigsaw}: Automated Protein Secondary Structure
and Main-Chain Assignment from Sparse, Unassigned {NMR}
Data},
Year = {2000},
Key = {ismb00-poster-cbk}
}
@misc{ismb00-poster-lilien,
Author = {R. Lilien and M. Sridharan and X. Huang and J. H. Bushweller and B. R. Donald},
Title = {Computational Screening Studies for Core Binding Factor
Beta: Use of Multiple Conformations to Model Receptor
Flexibility},
Year = {2000},
Key = {ismb00-poster-lilien}
}
@misc{JenningsRusDonald-poster-94,
Author = {B. R. Donald and J. Jennings and D. Rus},
Title = {Cooperating Autonomous Mobile Robots: Theory and
Experiments},
Address = {{MIT}, Cambridge, MA},
Year = {1994},
Key = {JenningsRusDonald-poster-94}
}
%% Other
@techreport{Dartmouth:TR2004-492,
Author = {Ryan H. Lilien and Mohini Sridharan and Bruce R.
Donald},
Title = {{Identification of Novel Small Molecule Inhibitors of
Core-Binding Factor Dimerization by Computational Screening
against NMR Molecular Ensembles}},
Number = {TR2004-492},
Organization = {Dartmouth College, Computer Science},
Institution = {Dartmouth College, Computer Science},
Address = {Hanover, NH},
Year = {2004},
url = {ftp://ftp.cs.dartmouth.edu/TR/TR2004-492.pdf},
Key = {Dartmouth:TR2004-492}
}
@techreport{Dartmouth:TR2004-494,
Author = {Christopher J. Langmead and Bruce R. Donald},
Title = {{An Improved Nuclear Vector Replacement Algorithm for
Nuclear Magnetic Resonance Assignment}},
Number = {TR2004-494},
Organization = {Dartmouth College, Computer Science},
Institution = {Dartmouth College, Computer Science},
Address = {Hanover, NH},
Year = {2003},
url = {ftp://ftp.cs.dartmouth.edu/TR/TR2004-494.pdf},
Key = {Dartmouth:TR2004-494}
}
%% Edited journal or collection PUBLISHED
@inbook{distr-manip00b,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald and F.~Lamiraux and L.~Kavraki},
Title = {Distributed Manipulation},
Publisher = {Kluwer Academic Publishing},
Editor = {K.~B{\"o}hringer et al.},
Chapter = {A Distributed, Universal Device for Plan},
Year = {2000},
Key = {distr-manip00b}
}
@inbook{distr-manip00c,
Author = {B.~R.~Donald and L.~Gariepy and D.~Rus},
Title = {Distributed Manipulation},
Publisher = {Kluwer Academic Publishing},
Editor = {K.~B{\"o}hringer et al.},
Chapter = {Constrained Prehensile Manipulation: Dis},
Year = {2000},
Key = {distr-manip00c}
}
@inbook{distr-manip00a,
Author = {J.~Suh and R.~B.~Darling and K.-F.~B{\"o}hringer and B.~R.~Donald and H.~Baltes and G.~Kovacs},
Title = {Distributed Manipulation},
Publisher = {Kluwer Academic Publishing},
Editor = {K.~B{\"o}hringer et al.},
Chapter = {{CMOS} Integrated Organic Ciliary Actuat},
Year = {2000},
Key = {distr-manip00a}
}
@incollection{robot-research00,
Author = {K.-F. B{\"o}hringer and B. R. Donald and F. Lamiraux and L.
Kavraki},
Title = {A Single Universal Force Field Can Uniquely Orient
Non-symmetric Parts},
Pages = {395--402},
Booktitle = {Robotics Research},
Publisher = {Springer-Verlag},
Address = {London},
Editor = {J. Hollerbach and D. Koditschek},
Year = {2000},
Key = {robot-research00}
}
@incollection{experimental-robotics00,
Author = {B. R. Donald and L. Gariepy and D. Rus},
Title = {Experiments in Constrained Prehensile Manipulation:
Distributted Manipulation with Ropes},
Volume = {250},
Series = {Lecture Notes in Control and Information
Sciences},
Pages = {25--36},
Booktitle = {Experimental Robotics {VI}},
Publisher = {Springer-Verlag},
Editor = {P. Corke et al.},
Year = {2000},
Key = {experimental-robotics00}
}
@inbook{algo-mems98,
Author = {K.-F.~B{\"o}hringer and B.~R.~Donald},
Title = {Robotics: The Algorithmic Perspective},
Pages = {1--20},
Publisher = {A.~K.~Peters},
Editor = {P.~Agarwal et al.},
Chapter = {Algorithmic {MEMS}},
Year = {1998},
Key = {algo-mems98}
}
@incollection{BohringerMacDonaldDonald97,
Author = {K.-F. B{\"o}hringer and B. R. Donald and N.
MacDonald},
Title = {Upper and lower bounds for programmable vector fields with
applications to {MEMS} and vibratory plate parts
feeders},
Pages = {255--276},
Booktitle = {Algorithms for Robotic Motion and Manipulation},
Publisher = {A. K. Peters},
Address = {Wellesley, MA},
Editor = {J. P. Laumond and M. Overmars},
Year = {1997},
Key = {BohringerMacDonaldDonald97}
}
@incollection{BriggsDonald97,
Author = {A.~Briggs and B.~R.~Donald},
Title = {Robust geometric algorithms for sensor planning},
Pages = {197--212},
Booktitle = {Algorithms for Robotic Motion and Manipulation},
Publisher = {A.~K.~Peters},
Address = {Wellesley, MA},
Editor = {J.~P.~Laumond and M.~Overmars},
Year = {1997},
Key = {BriggsDonald97}
}
@incollection{JenningsRusDonald95B,
Author = {B. R. Donald and J. Jennings and D. Rus},
Title = {Information Invariants for Distributed Manipulation},
Pages = {431--458},
Booktitle = {Algorithmic Foundations of Robotics},
Publisher = {A. K. Peters},
Address = {Boston, MA},
Editor = {K. Goldberg et al.},
Year = {1995},
Key = {JenningsRusDonald95B}
}
@incollection{PaiDonald92,
Author = {B. R. Donald and D. Pai},
Title = {Symbolic Methods for the Simulation of Planar Mechanical
Systems in Design},
Pages = {245--258},
Booktitle = {Symbolic and Numerical Computation for Artificial
Intelligence},
Publisher = {Academic Press, Harcourt Jovanovich},
Address = {London},
Editor = {B. Donald et al.},
Year = {1992},
Key = {PaiDonald92}
}
@incollection{CannyDonald90,
Author = {J. Canny and B. R. Donald},
Title = {Simplified Voronoi Diagrams},
Pages = {272--289},
Booktitle = {Autonomous Robot Vehicles},
Publisher = {Springer-Verlag},
Address = {New York},
Year = {1990},
Key = {CannyDonald90}
}
@incollection{Donald89B,
Author = {B. R. Donald},
Title = {A Geometric Approach to Error Detection and Recovery for
Robot Motion Planning with Uncertainty},
Pages = {223--274},
Booktitle = {Geometric Reasoning},
Publisher = {{MIT} Press},
Address = {Cambridge},
Year = {1989},
Key = {Donald89B}
}
|
| 
Mathematics Department