Department of Mathematics Search | Help | Login | |

Math @ Duke

 ....................... ....................... Webpage

Publications of John Harer    :chronological  alphabetical  combined listing:

%% Books
@book{fds324398,
Author = {Edelsbrunner, H and Harer, J},
Title = {Computational Topology - an Introduction.},
Publisher = {American Mathematical Society},
Year = {2010},
ISBN = {978-0-8218-4925-5},
Abstract = {This book is an introduction to computational topology for
students in Computer Science and Mathematics.},
Key = {fds324398}
}

@book{fds10018,
Author = {Penner, R. C. and Harer, J. L.},
Title = {Combinatorics of train tracks},
Journal = {pp. xii+216, 1992, Princeton University Press, Princeton,
NJ},
MRNUMBER = {94b:57018},
url = {http://www.ams.org/mathscinet-getitem?mr=94b:57018},
Key = {fds10018}
}

%% Papers Published
@article{fds335536,
Author = {Garagić, D and Peskoe, J and Liu, F and Claffey, MS and Bendich, P and Hineman, J and Borggren, N and Harer, J and Zulch, P and Rhodes,
BJ},
Title = {Upstream fusion of multiple sensing modalities using machine
learning and topological analysis: An initial
exploration},
Journal = {Ieee Aerospace Conference Proceedings},
Volume = {2018-March},
Pages = {1-8},
Year = {2018},
Month = {June},
ISBN = {9781538620144},
url = {http://dx.doi.org/10.1109/AERO.2018.8396737},
Abstract = {© 2018 IEEE. This paper presents a processing pipeline for
fusing 'raw' and / or feature-level multi-sensor data -
upstream fusion - and initial results from this pipeline
to determine which tracked object, among several, hosts an
emitter of interest. Correctly making this determination
requires fusing data across these modalities. Our approach
performs better than standard fusion approaches that make
detection / characterization decisions for each modality
individually and then try to fuse those decisions -
downstream (or post-decision) fusion. Our approach (1) fully
exploits the inter-modality dependencies and phenomenologies
inherent in different sensing modes, (2) automatically
discovers compressive hierarchical representations that
integrate structural and statistical characteristics to
enhance target / event discriminability, and (3) completely
obviates the need to specify features, manifolds, or model
scope a priori. This approach comprises a unique synthesis
of Deep Learning (DL), topological analysis over probability
measure (TAPM), and hierarchical Bayesian non-parametric
(HBNP) recognition models. Deep Generative Networks (DGNs -
a deep generative statistical form of DL) create probability
measures that provide a basis for calculating homologies
(topological summaries over the probability measures). The
statistics of the resulting persistence diagrams are inputs
to HBNP methods that learn to discriminate between target
types and distinguish emitting targets from non-emitting
targets, for example. HBNP learning obviates batch-mode
off-line learning. This approach overcomes the inadequacy of
pre-defined features as a means for creating efficient,
discriminating, low-dimensional representations from
high-dimensional multi-modality sensor data collected under
difficult, dynamic sensing conditions. The invariant
properties in the resulting compact representations afford
multiple compressive sensing benefits, including concise
information sharing and enhanced performance. Machine
learning makes adaptivity a central feature of our approach.
Adaptivity is critical because it enables flexible
processing that automatically accommodates a broad range of
challenges that non-adaptive, standard fusion approaches
would typically require manual intervention to begin to
address. These include (a) interest in unknown or
unanticipated targets, (b) desire to be rapidly able to fuse
between different combinations of sensor modalities, and (c)
potential need to transfer information between platforms
that host different sensors. This paper presents results
that demonstrate our approach enables accurate, real-time
target detection, tracking, and recognition of known and
unknown moving or stationary targets or events and their
activities evolving over space and time.},
Doi = {10.1109/AERO.2018.8396737},
Key = {fds335536}
}

@article{fds332374,
Author = {Tralie, CJ and Smith, A and Borggren, N and Hineman, J and Bendich, P and Zulch, P and Harer, J},
Title = {Geometric Cross-Modal Comparison of Heterogeneous Sensor
Data},
Journal = {Proceedings of the 39th IEEE Aerospace Conference},
Year = {2018},
Month = {March},
Abstract = {In this work, we address the problem of cross-modal
comparison of aerial data streams. A variety of simulated
automobile trajectories are sensed using two different
modalities: full-motion video, and radio-frequency (RF)
signals received by detectors at various locations. The
information represented by the two modalities is compared
using self-similarity matrices (SSMs) corresponding to
time-ordered point clouds in feature spaces of each of these
data sources; we note that these feature spaces can be of
entirely different scale and dimensionality. Several metrics
for comparing SSMs are explored, including a cutting-edge
time-warping technique that can simultaneously handle local
time warping and partial matches, while also controlling for
the change in geometry between feature spaces of the two
modalities. We note that this technique is quite general,
and does not depend on the choice of modalities. In this
particular setting, we demonstrate that the cross-modal
distance between SSMs corresponding to the same trajectory
type is smaller than the cross-modal distance between SSMs
corresponding to distinct trajectory types, and we formalize
this observation via precision-recall metrics in
experiments. Finally, we comment on promising implications
of these ideas for future integration into
multiple-hypothesis tracking systems.},
Key = {fds332374}
}

@article{fds330518,
Author = {Hughes, ME and Abruzzi, KC and Allada, R and Anafi, R and Arpat, AB and Asher, G and Baldi, P and de Bekker, C and Bell-Pedersen, D and Blau, J and Brown, S and Ceriani, MF and Chen, Z and Chiu, JC and Cox, J and Crowell,
AM and DeBruyne, JP and Dijk, D-J and DiTacchio, L and Doyle, FJ and Duffield, GE and Dunlap, JC and Eckel-Mahan, K and Esser, KA and FitzGerald, GA and Forger, DB and Francey, LJ and Fu, Y-H and Gachon, F and Gatfield, D and de Goede, P and Golden, SS and Green, C and Harer, J and Harmer, S and Haspel, J and Hastings, MH and Herzel, H and Herzog, ED and Hoffmann, C and Hong, C and Hughey, JJ and Hurley, JM and de la Iglesia,
HO and Johnson, C and Kay, SA and Koike, N and Kornacker, K and Kramer, A and Lamia, K and Leise, T and Lewis, SA and Li, J and Li, X and Liu, AC and Loros,
JJ and Martino, TA and Menet, JS and Merrow, M and Millar, AJ and Mockler,
T and Naef, F and Nagoshi, E and Nitabach, MN and Olmedo, M and Nusinow,
DA and Ptáček, LJ and Rand, D and Reddy, AB and Robles, MS and Roenneberg, T and Rosbash, M and Ruben, MD and Rund, SSC and Sancar, A and Sassone-Corsi, P and Sehgal, A and Sherrill-Mix, S and Skene, DJ and Storch, K-F and Takahashi, JS and Ueda, HR and Wang, H and Weitz, C and Westermark, PO and Wijnen, H and Xu, Y and Wu, G and Yoo, S-H and Young, M and Zhang, EE and Zielinski, T and Hogenesch, JB},
Title = {Guidelines for Genome-Scale Analysis of Biological
Rhythms.},
Journal = {Journal of Biological Rhythms},
Volume = {32},
Number = {5},
Pages = {380-393},
Year = {2017},
Month = {October},
url = {http://dx.doi.org/10.1177/0748730417728663},
Abstract = {Genome biology approaches have made enormous contributions
to our understanding of biological rhythms, particularly in
identifying outputs of the clock, including RNAs, proteins,
and metabolites, whose abundance oscillates throughout the
day. These methods hold significant promise for future
discovery, particularly when combined with computational
modeling. However, genome-scale experiments are costly and
laborious, yielding "big data" that are conceptually and
statistically difficult to analyze. There is no obvious
consensus regarding design or analysis. Here we discuss the
relevant technical considerations to generate reproducible,
statistically sound, and broadly useful genome-scale data.
Rather than suggest a set of rigid rules, we aim to codify
principles by which investigators, reviewers, and readers of
the primary literature can evaluate the suitability of
different experimental designs for measuring different
aspects of biological rhythms. We introduce CircaInSilico, a
web-based application for generating synthetic genome
biology data to benchmark statistical methods for studying
biological rhythms. Finally, we discuss several unmet
analytical needs, including applications to clinical
medicine, and suggest productive avenues to address
them.},
Doi = {10.1177/0748730417728663},
Key = {fds330518}
}

@article{fds324397,
Author = {Bendich, P and Chin, SP and Clark, J and Desena, J and Harer, J and Munch,
E and Newman, A and Porter, D and Rouse, D and Strawn, N and Watkins,
A},
Title = {Topological and statistical behavior classifiers for
tracking applications},
Journal = {Ieee Transactions on Aerospace and Electronic
Systems},
Volume = {52},
Number = {6},
Pages = {2644-2661},
Year = {2016},
Month = {December},
url = {http://dx.doi.org/10.1109/TAES.2016.160405},
Abstract = {© 1965-2011 IEEE.This paper introduces a method to
integrate target behavior into the multiple hypothesis
tracker (MHT) likelihood ratio. In particular, a periodic
track appraisal based on behavior is introduced. The track
appraisal uses elementary topological data analysis coupled
with basic machine-learning techniques, and it adjusts the
traditional kinematic data association likelihood (i.e.,
track score) using an established formulation for
feature-aided data association. The proposed method is
tested and demonstrated on synthetic vehicular data
representing an urban traffic scene generated by the
Simulation of Urban Mobility package. The vehicles in the
scene exhibit different driving behaviors. The proposed
method distinguishes those behaviors and shows improved data
association decisions relative to a conventional, kinematic
MHT.},
Doi = {10.1109/TAES.2016.160405},
Key = {fds324397}
}

@article{fds332375,
Author = {Bendich, P and Gasparovic, E and Harer, J and Tralie,
C},
Title = {Geometric Models for Musical Audio Data},
Journal = {Proceedings of the 32st International Symposium on
Computational Geometry (SOCG)},
Year = {2016},
Month = {June},
Key = {fds332375}
}

@article{fds321990,
Author = {Bendich, P and Gasparovic, E and Harer, J and Tralie,
C},
Title = {Geometric models for musical audio data},
Journal = {Leibniz International Proceedings in Informatics,
Lipics},
Volume = {51},
Pages = {65.1-65.5},
Year = {2016},
Month = {June},
ISBN = {9783959770095},
url = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.65},
Abstract = {© Paul Bendich, Ellen Gasparovic, John Harer, and
Christopher Tralie. We study the geometry of sliding window
embeddings of audio features that summarize perceptual
information about audio, including its pitch and timbre.
These embeddings can be viewed as point clouds in high
dimensions, and we add structure to the point clouds using a
cover tree with adaptive thresholds based on multi-scale
local principal component analysis to automatically assign
points to clusters. We connect neighboring clusters in a
scaffolding graph, and we use knowledge of stratified space
structure to refine our estimates of dimension in each
cluster, demonstrating in our music applications that
choruses and verses have higher dimensional structure, while
transitions between them are lower dimensional. We showcase
our technique with an interactive web-based application
synchronized with a principal component analysis embedding
of the point cloud down to 3D. We also render the clusters
and the scaffolding on top of this projection to visualize
the transitions between different sections of the
music.},
Doi = {10.4230/LIPIcs.SoCG.2016.65},
Key = {fds321990}
}

@article{fds243563,
Author = {Perea, JA and Deckard, A and Haase, SB and Harer,
J},
Title = {SW1PerS: Sliding windows and 1-persistence scoring;
discovering periodicity in gene expression time series
data.},
Journal = {Bmc Bioinformatics},
Volume = {16},
Pages = {257},
Year = {2015},
Month = {August},
url = {http://dx.doi.org/10.1186/s12859-015-0645-6},
Abstract = {Identifying periodically expressed genes across different
processes (e.g. the cell and metabolic cycles, circadian
rhythms, etc) is a central problem in computational biology.
Biological time series may contain (multiple) unknown signal
shapes of systemic relevance, imperfections like noise,
damping, and trending, or limited sampling density. While
there exist methods for detecting periodicity, their design
biases (e.g. toward a specific signal shape) can limit their
applicability in one or more of these situations.We present
in this paper a novel method, SW1PerS, for quantifying
periodicity in time series in a shape-agnostic manner and
with resistance to damping. The measurement is performed
directly, without presupposing a particular pattern, by
evaluating the circularity of a high-dimensional
representation of the signal. SW1PerS is compared to other
algorithms using synthetic data and performance is
quantified under varying noise models, noise levels,
sampling densities, and signal shapes. Results on biological
data are also analyzed and compared.On the task of
periodic/not-periodic classification, using synthetic data,
SW1PerS outperforms all other algorithms in the low-noise
regime. SW1PerS is shown to be the most shape-agnostic of
the evaluated methods, and the only one to consistently
classify damped signals as highly periodic. On biological
data, and for several experiments, the lists of top 10%
genes ranked with SW1PerS recover up to 67% of those
generated with other popular algorithms. Moreover, the list
of genes from data on the Yeast metabolic cycle which are
highly-ranked only by SW1PerS, contains evidently non-cosine
patterns (e.g. ECM33, CDC9, SAM1,2 and MSH6) with highly
periodic expression profiles. In data from the Yeast cell
cycle SW1PerS identifies genes not preferred by other
algorithms, hence not previously reported as periodic, but
found in other experiments such as the universal growth rate
response of Slavov. These genes are BOP3, CDC10, YIL108W,
YER034W, MLP1, PAC2 and RTT101.In biological systems with
low noise, i.e. where periodic signals with interesting
shapes are more likely to occur, SW1PerS can be used as a
powerful tool in exploratory analyses. Indeed, by having an
initial set of periodic genes with a rich variety of signal
types, pattern/shape information can be included in the
study of systems and the generation of hypotheses regarding
the structure of gene regulatory networks.},
Doi = {10.1186/s12859-015-0645-6},
Key = {fds243563}
}

@article{fds303544,
Author = {Munch, E and Turner, K and Bendich, P and Mukherjee, S and Mattingly, J and Harer, J},
Title = {Probabilistic Fréchet Means for Time Varying Persistence
Diagrams},
Volume = {9},
Number = {1},
Pages = {1173-1204},
Year = {2015},
Month = {January},
url = {http://arxiv.org/abs/1307.6530v3},
Abstract = {In order to use persistence diagrams as a true statistical
tool, it would be very useful to have a good notion of mean
and variance for a set of diagrams. In 2011, Mileyko and his
collaborators made the first study of the properties of the
Fr\'echet mean in $(\mathcal{D}_p,W_p)$, the space of
persistence diagrams equipped with the p-th Wasserstein
metric. In particular, they showed that the Fr\'echet mean
of a finite set of diagrams always exists, but is not
necessarily unique. The means of a continuously-varying set
of diagrams do not themselves (necessarily) vary
continuously, which presents obvious problems when trying to
extend the Fr\'echet mean definition to the realm of
vineyards. We fix this problem by altering the original
definition of Fr\'echet mean so that it now becomes a
probability measure on the set of persistence diagrams; in a
nutshell, the mean of a set of diagrams will be a weighted
sum of atomic measures, where each atom is itself a
persistence diagram determined using a perturbation of the
input diagrams. This definition gives for each $N$ a map
$(\mathcal{D}_p)^N \to \mathbb{P}(\mathcal{D}_p)$. We show
that this map is H\"older continuous on finite diagrams and
thus can be used to build a useful statistic on time-varying
persistence diagrams, better known as vineyards.},
Doi = {10.1214/15-EJS1030},
Key = {fds303544}
}

@article{fds321992,
Author = {Rouse, D and Watkins, A and Porter, D and Harer, J and Bendich, P and Strawn, N and Munch, E and Desena, J and Clarke, J and Gilbert, J and Chin,
S and Newman, A},
Title = {Feature-aided multiple hypothesis tracking using topological
and statistical behavior classifiers},
Journal = {Smart Structures and Materials 2005: Active Materials:
Behavior and Mechanics},
Volume = {9474},
Year = {2015},
Month = {January},
ISBN = {9781628415902},
ISSN = {10.1117/12.2179555},
url = {http://dx.doi.org/10.1117/12.2179555},
Abstract = {© 2015 SPIE. This paper introduces a method to integrate
target behavior into the multiple hypothesis tracker (MHT)
likelihood ratio. In particular, a periodic track appraisal
based on behavior is introduced that uses elementary
topological data analysis coupled with basic machine
learning techniques. The track appraisal adjusts the
traditional kinematic data association likelihood (i.e.,
track score) using an established formulation for
classification-aided data association. The proposed method
is tested and demonstrated on synthetic vehicular data
representing an urban traffic scene generated by the
Simulation of Urban Mobility package. The vehicles in the
scene exhibit different driving behaviors. The proposed
method distinguishes those behaviors and shows improved data
association decisions relative to a conventional, kinematic
MHT.},
Doi = {10.1117/12.2179555},
Key = {fds321992}
}

@article{fds243564,
Author = {Farr, RS and Harer, JL and Fink, TMA},
Title = {Easily repairable networks: reconnecting nodes after
damage.},
Journal = {Physical Review Letters},
Volume = {113},
Number = {13},
Pages = {138701},
Year = {2014},
Month = {September},
ISSN = {0031-9007},
url = {http://dx.doi.org/10.1103/physrevlett.113.138701},
Abstract = {We introduce a simple class of distribution networks that
withstand damage by being repairable instead of redundant.
damage, we ask how easy it is to reconnect nodes after
damage. We prove that optimal networks on regular lattices
have an expected cost of reconnection proportional to the
lattice length, and that such networks have exactly three
levels of structural hierarchy. We extend our results to
networks subject to repeated attacks, in which the repairs
themselves must be repairable. We find that, in exchange for
a modest increase in repair cost, such networks are able to
withstand any number of attacks.},
Doi = {10.1103/physrevlett.113.138701},
Key = {fds243564}
}

@article{fds323579,
Author = {Bristow, SL and Leman, AR and Simmons Kovacs and LA and Deckard, A and Harer, J and Haase, SB},
Title = {Checkpoints couple transcription network oscillator dynamics
to cell-cycle progression.},
Journal = {Genome Biology},
Volume = {15},
Number = {9},
Pages = {446},
Year = {2014},
Month = {September},
url = {http://dx.doi.org/10.1186/s13059-014-0446-7},
Abstract = {The coupling of cyclin dependent kinases (CDKs) to an
intrinsically oscillating network of transcription factors
has been proposed to control progression through the cell
cycle in budding yeast, Saccharomyces cerevisiae. The
transcription network regulates the temporal expression of
many genes, including cyclins, and drives cell-cycle
progression, in part, by generating successive waves of
distinct CDK activities that trigger the ordered program of
cell-cycle events. Network oscillations continue
autonomously in mutant cells arrested by depletion of CDK
activities, suggesting the oscillator can be uncoupled from
cell-cycle progression. It is not clear what mechanisms, if
any, ensure that the network oscillator is restrained when
progression in normal cells is delayed or arrested. A recent
proposal suggests CDK acts as a master regulator of
cell-cycle processes that have the potential for autonomous
oscillatory behavior.Here we find that mitotic CDK is not
sufficient for fully inhibiting transcript oscillations in
arrested cells. We do find that activation of the DNA
replication and spindle assembly checkpoints can fully
arrest the network oscillator via overlapping but distinct
mechanisms. Further, we demonstrate that the DNA replication
checkpoint effector protein, Rad53, acts to arrest a portion
of transcript oscillations in addition to its role in
halting cell-cycle progression.Our findings indicate that
checkpoint mechanisms, likely via phosphorylation of network
transcription factors, maintain coupling of the network
oscillator to progression during cell-cycle
arrest.},
Doi = {10.1186/s13059-014-0446-7},
Key = {fds323579}
}

@article{fds243565,
Author = {Turner, K and Mileyko, Y and Mukherjee, S and Harer,
J},
Title = {Fréchet Means for Distributions of Persistence
Diagrams},
Journal = {Discrete & Computational Geometry},
Volume = {52},
Number = {1},
Pages = {44-70},
Year = {2014},
Month = {July},
ISSN = {0179-5376},
url = {http://dx.doi.org/10.1007/s00454-014-9604-7},
Abstract = {Given a distribution ρ on persistence diagrams and
observations X1,...Xn∼iidρ we introduce an algorithm in
this paper that estimates a Fr\'echet mean from the set of
diagrams X1,...Xn. If the underlying measure ρ is a
combination of Dirac masses ρ=1m∑mi=1δZi then we prove
the algorithm converges to a local minimum and a law of
large numbers result for a Fr\'echet mean computed by the
algorithm given observations drawn iid from ρ. We
illustrate the convergence of an empirical mean computed by
the algorithm to a population mean by simulations from
Gaussian random fields.},
Doi = {10.1007/s00454-014-9604-7},
Key = {fds243565}
}

@article{fds221199,
Author = {Elizabeth Munch and Paul Bendich and Katharine Turner and Sayan
Mukherjee, Jonathan Mattingly and John Harer},
Title = {Probabilistic Fréchet Means and Statistics on
Vineyards},
Year = {2014},
Abstract = {In order to use persistence diagrams as a true statistical
tool, it would be very useful to have a good notion of mean
and variance for a set of diagrams. Mileyko and his
collaborators made the first study of the properties of the
Fr\'{e}chet mean in (Dp,Wp), the space of persistence
diagrams equipped with the p-th Wasserstein metric. In
particular, they showed that the Fr\'{e}chet mean of a
finite set of diagrams always exists, but is not necessarily
unique. As an unfortunate consequence, one sees that the
means of a continuously-varying set of diagrams do not
themselves vary continuously, which presents obvious
problems when trying to extend the Fr\'{e}chet mean
definition to the realm of vineyards. We fix this problem by
altering the original definition of Fr\'{e}chet mean so that
it now becomes a probability measure on the set of
persistence diagrams; in a nutshell, the mean of a set of
diagrams will be a weighted sum of atomic measures, where
each atom is itself the (Fr\'{e}chet mean) persistence
diagram of a perturbation of the input diagrams. We show
that this new definition defines a (H\"older) continuous
map, for each k, from (Dp)k→P(Dp), and we present several
examples to show how it may become a useful statistic on
vineyards.},
Key = {fds221199}
}

@article{fds243562,
Author = {Perea, JA and Harer, J},
Title = {Sliding Windows and Persistence: An Application of
Topological Methods to Signal Analysis},
Journal = {Foundations of Computational Mathematics},
Volume = {15},
Number = {3},
Pages = {799-838},
Year = {2014},
ISSN = {1615-3375},
url = {http://dx.doi.org/10.1007/s10208-014-9206-z},
Abstract = {© 2014, SFoCM.We develop in this paper a theoretical
framework for the topological study of time series data.
Broadly speaking, we describe geometrical and topological
properties of sliding window embeddings, as seen through the
lens of persistent homology. In particular, we show that
maximum persistence at the point-cloud level can be used to
quantify periodicity at the signal level, prove structural
and convergence theorems for the resulting persistence
diagrams, and derive estimates for their dependency on
window size and embedding dimension. We apply this
methodology to quantifying periodicity in synthetic data
sets and compare the results with those obtained using
state-of-the-art methods in gene expression analysis. We
call this new method SW1PerS, which stands for Sliding
Windows and 1-Dimensional Persistence Scoring.},
Doi = {10.1007/s10208-014-9206-z},
Key = {fds243562}
}

@article{fds243594,
Author = {Deckard, A and Anafi, RC and Hogenesch, JB and Haase, SB and Harer,
J},
Title = {Design and analysis of large-scale biological rhythm
studies: a comparison of algorithms for detecting periodic
signals in biological data.},
Journal = {Bioinformatics (Oxford, England)},
Volume = {29},
Number = {24},
Pages = {3174-3180},
Year = {2013},
Month = {December},
url = {http://dx.doi.org/10.1093/bioinformatics/btt541},
Abstract = {To discover and study periodic processes in biological
systems, we sought to identify periodic patterns in their
gene expression data. We surveyed a large number of
available methods for identifying periodicity in time series
data and chose representatives of different mathematical
perspectives that performed well on both synthetic data and
biological data. Synthetic data were used to evaluate how
each algorithm responds to different curve shapes, periods,
phase shifts, noise levels and sampling rates. The
biological datasets we tested represent a variety of
periodic processes from different organisms, including the
cell cycle and metabolic cycle in Saccharomyces cerevisiae,
circadian rhythms in Mus musculus and the root clock in
Arabidopsis thaliana.From these results, we discovered that
each algorithm had different strengths. Based on our
findings, we make recommendations for selecting and applying
these methods depending on the nature of the data and the
periodic patterns of interest. Additionally, these results
can also be used to inform the design of large-scale
biological rhythm experiments so that the resulting data can
be used with these algorithms to detect periodic signals
more effectively.},
Doi = {10.1093/bioinformatics/btt541},
Key = {fds243594}
}

@article{fds303543,
Author = {Perea, J and Harer, J},
Title = {Sliding Windows and Persistence: An Application of
Topological Methods to Signal Analysis},
Year = {2013},
Month = {July},
url = {http://arxiv.org/abs/1307.6188v2},
Abstract = {We develop in this paper a theoretical framework for the
topological study of time series data. Broadly speaking, we
describe geometrical and topological properties of sliding
window (or time-delay) embeddings, as seen through the lens
of persistent homology. In particular, we show that maximum
persistence at the point-cloud level can be used to quantify
periodicity at the signal level, prove structural and
convergence theorems for the resulting persistence diagrams,
and derive estimates for their dependency on window size and
embedding dimension. We apply this methodology to
quantifying periodicity in synthetic data sets, and compare
the results with those obtained using state-of-the-art
methods in gene expression analysis. We call this new method
SW1PerS which stands for Sliding Windows and 1-dimensional
Persistence Scoring.},
Key = {fds303543}
}

@article{fds243566,
Author = {Topp, CN and Iyer-Pascuzzi, AS and Anderson, JT and Lee, C-R and Zurek,
PR and Symonova, O and Zheng, Y and Bucksch, A and Mileyko, Y and Galkovskyi, T and Moore, BT and Harer, J and Edelsbrunner, H and Mitchell-Olds, T and Weitz, JS and Benfey, PN},
Title = {3D phenotyping and quantitative trait locus mapping identify
core regions of the rice genome controlling root
architecture.},
Journal = {Proceedings of the National Academy of Sciences of the
United States of America},
Volume = {110},
Number = {18},
Pages = {E1695-E1704},
Year = {2013},
Month = {April},
url = {http://www.ncbi.nlm.nih.gov/pubmed/23580618},
Abstract = {Identification of genes that control root system
architecture in crop plants requires innovations that enable
high-throughput and accurate measurements of root system
architecture through time. We demonstrate the ability of a
semiautomated 3D in vivo imaging and digital phenotyping
pipeline to interrogate the quantitative genetic basis of
root system growth in a rice biparental mapping population,
Bala × Azucena. We phenotyped >1,400 3D root models and
>57,000 2D images for a suite of 25 traits that quantified
the distribution, shape, extent of exploration, and the
intrinsic size of root networks at days 12, 14, and 16 of
growth in a gellan gum medium. From these data we identified
89 quantitative trait loci, some of which correspond to
those found previously in soil-grown plants, and provide
evidence for genetic tradeoffs in root growth allocations,
such as between the extent and thoroughness of exploration.
We also developed a multivariate method for generating and
mapping central root architecture phenotypes and used it to
identify five major quantitative trait loci (r(2) = 24-37%),
two of which were not identified by our univariate analysis.
Our imaging and analytical platform provides a means to
identify genes with high potential for improving root traits
and agronomic qualities of crops.},
Doi = {10.1073/pnas.1304354110},
Key = {fds243566}
}

@article{fds221197,
Author = {Christopher N Topp and Anjali S Iyer-Pascuzzi and Jill T Anderson and Cheng-Ruei Lee and Paul R Zurek and Olga Symonova and Ying Zheng and Alexander Bucksch and Yuriy Milyeko and Taras Galkovskyi and Brad
Moore, John Harer and Herbert Edelsbrunner and Thomas Mitchell
Olds and Joshua S Weitz and Philip N Benfey},
Title = {3-dimensional phenotyping of growing root systems combined
with QTL mapping identifies core regions of the rice genome
controlling root architecture},
Journal = {PNAS},
Year = {2013},
Abstract = {Identification of genes that control root system
architecture in crop plants requires innovations that enable
high-throughput and accurate measurements of root system
architecture through time. We demonstrate the ability of a
semiautomated 3D in vivo imaging and digital phenotyping
pipeline to interrogate the quantitative genetic basis of
root system growth in a rice biparental mapping population,
Bala × Azucena. We phenotyped >1,400 3D root models and
>57,000 2D images for a suite of 25 traits that quantified
the distribution, shape, extent of exploration, and the
intrinsic size of root networks at days 12, 14, and 16 of
growth in a gellan gum medium. From these data we identified
89 quantitative trait loci, some of which correspond to
those found previously in soil-grown plants, and provide
evidence for genetic tradeoffs in root growth allocations,
such as between the extent and thoroughness of exploration.
We also developed a multivariate method for generating and
mapping central root architecture phenotypes and used it to
identify five major quantitative trait loci (r2 = 24–37%),
two of which were not identified by our univariate analysis.
Our imaging and analytical platform provides a means to
identify genes with high potential for improving root traits
and agronomic qualities of crops.},
Key = {fds221197}
}

@article{fds243595,
Author = {Topp, and CN, and Iyer-Pascuzzi, AS and Anderson, JT and Lee, C-R and Zurek, PR and Symonova, O and Zheng, Y and Bucksch, A and Milyeko, Y and Galkovskyi, T and Moore, BT and Harer, J and Edelsbrunner, H and Mitchell-Olds, T and Weitz, JS and Benfey, PN},
Title = {3-dimensional phenotyping of growing root systems and QTL
mapping identifies core regions of the rice genome
controlling root architecture},
Journal = {PNAS},
Volume = {110},
Pages = {E1695-1704},
Year = {2013},
Key = {fds243595}
}

@article{fds311264,
Author = {Munch, E and Shapiro, M and Harer, J},
Title = {Failure filtrations for fenced sensor networks},
Journal = {International Journal of Robotics Research},
Volume = {31},
Number = {9},
Pages = {1044-1056},
Year = {2012},
Month = {August},
url = {http://arxiv.org/abs/1109.6535v1},
Abstract = {In this paper we consider the question of sensor network
coverage for a 2-dimensional domain. We seek to compute the
probability that a set of sensors fails to cover given only
non-metric, local (who is talking to whom) information and a
probability distribution of failure of each node. This
builds on the work of de Silva and Ghrist who analyzed this
problem in the deterministic situation. We first show that a
it is part of a slightly larger class of problems which is
#P-complete, and thus fast algorithms likely do not exist
unless P$=$NP. We then give a deterministic algorithm which
is feasible in the case of a small set of sensors, and give
a dynamic algorithm for an arbitrary set of sensors failing
over time which utilizes a new criterion for coverage based
on the one proposed by de Silva and Ghrist. These algorithms
build on the theory of topological persistence.},
Doi = {10.1177/0278364912451671},
Key = {fds311264}
}

@article{fds303545,
Author = {Turner, K and Mileyko, Y and Mukherjee, S and Harer,
J},
Title = {Fréchet Means for Distributions of Persistence
diagrams},
Year = {2012},
Month = {June},
url = {http://arxiv.org/abs/1206.2790v2},
Abstract = {Given a distribution $\rho$ on persistence diagrams and
observations $X_1,...X_n \stackrel{iid}{\sim} \rho$ we
introduce an algorithm in this paper that estimates a
Fr\'echet mean from the set of diagrams $X_1,...X_n$. If the
underlying measure $\rho$ is a combination of Dirac masses
$\rho = \frac{1}{m} \sum_{i=1}^m \delta_{Z_i}$ then we prove
the algorithm converges to a local minimum and a law of
large numbers result for a Fr\'echet mean computed by the
algorithm given observations drawn iid from $\rho$. We
illustrate the convergence of an empirical mean computed by
the algorithm to a population mean by simulations from
Gaussian random fields.},
Key = {fds303545}
}

@article{fds243596,
Author = {Galkovskyi, T and Mileyko, Y and Bucksch, A and Moore, B and Symonova,
O and Price, CA and Topp, CN and Iyer-Pascuzzi, AS and Zurek, PR and Fang,
S and Harer, J and Benfey, PN and Weitz, JS},
Title = {GiA Roots: software for the high throughput analysis of
plant root system architecture.},
Journal = {Bmc Plant Biology},
Volume = {12},
Number = {116},
Pages = {116},
Year = {2012},
Month = {January},
url = {http://www.ncbi.nlm.nih.gov/pubmed/22834569},
Abstract = {BACKGROUND: Characterizing root system architecture (RSA) is
essential to understanding the development and function of
vascular plants. Identifying RSA-associated genes also
represents an underexplored opportunity for crop
improvement. Software tools are needed to accelerate the
pace at which quantitative traits of RSA are estimated from
images of root networks. RESULTS: We have developed GiA
Roots (General Image Analysis of Roots), a semi-automated
software tool designed specifically for the high-throughput
analysis of root system images. GiA Roots includes
user-assisted algorithms to distinguish root from background
and a fully automated pipeline that extracts dozens of root
system phenotypes. Quantitative information on each
phenotype, along with intermediate steps for full
reproducibility, is returned to the end-user for downstream
analysis. GiA Roots has a GUI front end and a command-line
interface for interweaving the software into large-scale
workflows. GiA Roots can also be extended to estimate novel
phenotypes specified by the end-user. CONCLUSIONS: We
demonstrate the use of GiA Roots on a set of 2393 images of
rice roots representing 12 genotypes from the species Oryza
sativa. We validate trait measurements against prior
analyses of this image set that demonstrated that RSA traits
are likely heritable and associated with genotypic
differences. Moreover, we demonstrate that GiA Roots is
extensible and an end-user can add functionality so that GiA
Roots can estimate novel RSA traits. In summary, we show
that the software can function as an efficient tool as part
of a workflow to move from large numbers of root images to
downstream analysis.},
Doi = {10.1186/1471-2229-12-116},
Key = {fds243596}
}

@article{fds243591,
Author = {Munch, E and Shapiro, M and Harer, J},
Title = {Failure filtrations for fenced sensor networks},
Journal = {International Journal of Robotics Research},
Volume = {31},
Number = {9},
Pages = {1044-1056},
Year = {2012},
ISSN = {0278-3649},
url = {http://arxiv.org/abs/1109.6535v1},
Abstract = {In this paper we consider the question of sensor network
coverage for a two-dimensional domain. We seek to compute
the probability that a set of sensors fails to cover given
only non-metric, local (who is talking to whom) information
and a probability distribution of failure of each node. This
builds on the work of de Silva and Ghrist who analyzed this
problem in the deterministic situation. We first show that
it is part of a slightly larger class of problems which is
#P-hard, and thus fast algorithms likely do not exist unless
P = NP. The question of whether the specific problem is, in
fact, #P-hard remains open. We then give a deterministic
algorithm which is feasible in the case of a small set of
sensors, and give a dynamic algorithm for an arbitrary set
of sensors failing over time which utilizes a new criterion
for coverage to give an early warning of potential failure.
These algorithms build on the theory of topological
Doi = {10.1177/0278364912451671},
Key = {fds243591}
}

@article{fds243597,
Author = {Bendich, P and Harer, J},
Title = {Persistent Intersection Homology},
Journal = {Foundations of Computational Mathematics},
Volume = {11},
Number = {3},
Pages = {305-336},
Year = {2011},
Month = {June},
ISSN = {1615-3375},
url = {http://dx.doi.org/10.1007/s10208-010-9081-1},
Abstract = {The theory of intersection homology was developed to study
the singularities of a topologically stratified space. This
paper incorporates this theory into the already developed
framework of persistent homology. We demonstrate that
persistent intersection homology gives useful information
about the relationship between an embedded stratified space
and its singularities. We give an algorithm for the
computation of the persistent intersection homology groups
of a filtered simplicial complex equipped with a
stratification by subcomplexes, and we prove its
correctness. We also derive, from Poincaré Duality, some
structural results about persistent intersection homology.
Doi = {10.1007/s10208-010-9081-1},
Key = {fds243597}
}

@article{fds199103,
Author = {Anjali S. Iyer-Pascuzzi and Christopher N. Topp and Jill T.
Anderson and Cheng-Ruei Lee and Olga Symonova and Yuriy Mileyko and Taras Galkovsky and Ying Zheng and Randy Clark and Leon Kochian and Herbert Edelsbrunner and Joshua S. Weitz and Thomas Mitchell-Olds and John Harer and Philip N. Benfey},
Title = {Quantitative Genetic Analysis of Root System Architecture in
Rice Plant and Animal Genomes},
Journal = {XX Genome Conference},
Year = {2011},
Key = {fds199103}
}

@article{fds243598,
Author = {Bendich, P and Galkovskyi, T and Harer, J},
Title = {Improving homology estimates with random
walks},
Journal = {Inverse Problems},
Volume = {27},
Number = {12},
Pages = {16},
Year = {2011},
ISSN = {0266-5611},
url = {http://dx.doi.org/10.1088/0266-5611/27/12/124002},
Abstract = {This experimental paper makes the case for a new approach to
the use of persistent homology in the study of shape and
feature in datasets. By introducing ideas from diffusion
geometry and random walks, we discover that homological
features can be enhanced and more effectively extracted from
spaces that are sampled densely and evenly, and with a small
amount of noise. This study paves the way for a more
theoretical analysis of how random walk metrics affect
persistence diagrams, and provides evidence that combining
topological data analysis with techniques inspired by
diffusion geometry holds great promise for new analyses of a
wide variety of datasets. © 2011 IOP Publishing
Ltd.},
Doi = {10.1088/0266-5611/27/12/124002},
Key = {fds243598}
}

@article{fds243599,
Author = {Mileyko, Y and Mukherjee, S and Harer, J},
Title = {Probability measures on the space of persistence
diagrams},
Journal = {Inverse Problems},
Volume = {27},
Number = {12},
Pages = {25},
Year = {2011},
ISSN = {0266-5611},
url = {http://dx.doi.org/10.1088/0266-5611/27/12/124007},
Abstract = {This paper shows that the space of persistence diagrams has
properties that allow for the definition of probability
measures which support expectations, variances, percentiles
and conditional probabilities. This provides a theoretical
basis for a statistical treatment of persistence diagrams,
for example computing sample averages and sample variances
of persistence diagrams. We first prove that the space of
persistence diagrams with the Wasserstein metric is complete
and separable. We then prove a simple criterion for
compactness in this space. These facts allow us to show the
existence of the standard statistical objects needed to
extend the theory of topological persistence to a much
larger set of applications. © 2011 IOP Publishing
Ltd.},
Doi = {10.1088/0266-5611/27/12/124007},
Key = {fds243599}
}

@article{fds243600,
Author = {Bini, G and Harer, J},
Title = {Euler characteristics of moduli spaces of
curves},
Journal = {Journal of the European Mathematical Society},
Volume = {13},
Number = {2},
Pages = {487-512},
Year = {2011},
ISSN = {1435-9855},
url = {http://dx.doi.org/10.4171/JEMS/259},
Abstract = {Let Mng be the moduli space of n-pointed Riemann surfaces of
genus g. Denote by M̄ng the Deligne-Mumford
compactification of Mng. In the present paper, we calculate
the orbifold and the ordinary Euler characteristics of M̄ng
for any g and n such that n &gt; 2 - 2g. © 2011 European
Mathematical Society.},
Doi = {10.4171/JEMS/259},
Key = {fds243600}
}

@article{fds243601,
Author = {Cohen-Steiner, D and Edelsbrunner, H and Harer, J and Mileyko,
Y},
Title = {Lipschitz Functions Have L p -Stable Persistence},
Journal = {Foundations of Computational Mathematics},
Volume = {10},
Number = {2},
Pages = {127-139},
Year = {2010},
Month = {April},
ISSN = {1615-3375},
url = {http://www.cs.duke.edu/~edels/Topology/},
Abstract = {We prove two stability results for Lipschitz functions on
triangulable, compact metric spaces and consider
applications of both to problems in systems biology. Given
two functions, the first result is formulated in terms of
the Wasserstein distance between their persistence diagrams
and the second in terms of their total persistence. © 2010
SFoCM.},
Doi = {10.1007/s10208-010-9060-6},
Key = {fds243601}
}

@article{fds243602,
Author = {Iyer-Pascuzzi, AS and Symonova, O and Mileyko, Y and Hao, Y and Belcher,
H and Harer, J and Weitz, JS and Benfey, PN},
Title = {Imaging and analysis platform for automatic phenotyping and
trait ranking of plant root systems.},
Journal = {Plant Physiology},
Volume = {152},
Number = {3},
Pages = {1148-1157},
Year = {2010},
Month = {March},
url = {http://www.ncbi.nlm.nih.gov/pubmed/20107024},
Abstract = {The ability to nondestructively image and automatically
phenotype complex root systems, like those of rice (Oryza
sativa), is fundamental to identifying genes underlying root
system architecture (RSA). Although root systems are central
to plant fitness, identifying genes responsible for RSA
remains an underexplored opportunity for crop improvement.
Here we describe a nondestructive imaging and analysis
system for automated phenotyping and trait ranking of RSA.
Using this system, we image rice roots from 12 genotypes. We
automatically estimate RSA traits previously identified as
important to plant function. In addition, we expand the
suite of features examined for RSA to include traits that
more comprehensively describe monocot RSA but that are
difficult to measure with traditional methods. Using 16
automatically acquired phenotypic traits for 2,297 images
from 118 individuals, we observe (1) wide variation in
phenotypes among the genotypes surveyed; and (2) greater
intergenotype variance of RSA features than variance within
a genotype. RSA trait values are integrated into a
computational pipeline that utilizes supervised learning
methods to determine which traits best separate two
genotypes, and then ranks the traits according to their
contribution to each pairwise comparison. This trait-ranking
step identifies candidate traits for subsequent quantitative
trait loci analysis and demonstrates that depth and average
radius are key contributors to differences in rice RSA
within our set of genotypes. Our results suggest a strong
genetic component underlying rice RSA. This work enables the
automatic phenotyping of RSA of individuals within mapping
populations, providing an integrative framework for
quantitative trait loci analysis of RSA.},
Doi = {10.1104/pp.109.150748},
Key = {fds243602}
}

@article{fds243584,
Author = {Cohen-Steiner, D and Edelsbrunner, H and Harer, J and Morozov,
D},
Title = {Persistent homology for kernels, images, and
cokernels},
Journal = {Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms},
Pages = {1011-1020},
Year = {2009},
url = {http://www.cs.duke.edu/~edels/Topology/},
Abstract = {Motivated by the measurement of local homology and of
functions on noisy domains, we extend the notion of
persistent homology to sequences of kernels, images, and
cokernels of maps induced by inclusions in a filtration of
pairs of spaces. Specifically, we note that persistence in
this context is well defined, we prove that the persistence
diagrams are stable, and we explain how to compute them.
Key = {fds243584}
}

@article{fds243585,
Author = {Edelsbrunner, H and Harer, J},
Title = {The persistent Morse complex segmentation of a
3-manifold},
Journal = {Lecture Notes in Computer Science (Including Subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {5903 LNCS},
Series = {Lecture Notes Comp. Sci.},
Pages = {36-50},
Booktitle = {3D Physiological Human Workshop, 2009},
Publisher = {Springer-Verlag, Berlin},
Editor = {N. Magnenat-Thalmann},
Year = {2009},
ISSN = {0302-9743},
url = {http://dx.doi.org/10.1007/978-3-642-10470-1_4},
Abstract = {We describe an algorithm for segmenting three-dimensional
medical imaging data modeled as a continuous function on a
3-manifold. It is related to watershed algorithms developed
in image processing but is closer to its mathematical roots,
which are Morse theory and homological algebra. It allows
for the implicit treatment of an underlying mesh, thus
combining the structural integrity of its mathematical
foundations with the computational efficiency of image
2009.},
Doi = {10.1007/978-3-642-10470-1_4},
Key = {fds243585}
}

@article{fds243586,
Author = {Cohen-Steiner, D and Edelsbrunner, H and Harer,
J},
Title = {Extending persistence using poincaré and lefschetz duality
(Foundations of Computational Mathematics DOI
10.1007/s10208-008-9027-z)},
Journal = {Foundations of Computational Mathematics},
Volume = {9},
Number = {1},
Pages = {133-134},
Year = {2009},
ISSN = {1615-3375},
url = {http://dx.doi.org/10.1007/s10208-008-9038-9},
Doi = {10.1007/s10208-008-9038-9},
Key = {fds243586}
}

@article{fds243603,
Author = {Cohen-Steiner, D and Edelsbrunner, H and Harer,
J},
Title = {Extending persistence using poincaré and lefschetz
duality},
Journal = {Foundations of Computational Mathematics},
Volume = {9},
Number = {1},
Pages = {79-103},
Year = {2009},
ISSN = {1615-3375},
url = {http://dx.doi.org/10.1007/s10208-008-9027-z},
Abstract = {Persistent homology has proven to be a useful tool in a
variety of contexts, including the recognition and
measurement of shape characteristics of surfaces in 3.
Persistence pairs homology classes that are born and die in
a filtration of a topological space, but does not pair its
actual homology classes. For the sublevelset filtration of a
surface in 3, persistence has been extended to a pairing of
essential classes using Reeb graphs. In this paper, we give
an algebraic formulation that extends persistence to
essential homology for any filtered space, present an
algorithm to calculate it, and describe how it aids our
ability to recognize shape features for codimension 1
submanifolds of Euclidean space. The extension derives from
Poincaré duality but generalizes to nonmanifold spaces. We
prove stability for general triangulated spaces and duality
as well as symmetry for triangulated manifolds. © 2008
SFoCM.},
Doi = {10.1007/s10208-008-9027-z},
Key = {fds243603}
}

@article{fds324399,
Author = {Edelsbrunner, H and Harer, J},
Title = {Persistent homology - a survey},
Journal = {Surveys on Discrete and Computational Geometry: Twenty Years
Later},
Volume = {453},
Pages = {257-+},
Publisher = {AMER MATHEMATICAL SOC},
Editor = {Goodman, JE and Pach, J and Pollack, R},
Year = {2008},
Month = {January},
ISBN = {978-0-8218-4239-3},
url = {http://math.duke.edu/~harer/public_html/papers/survey.pdf},
Abstract = {This paper surveys the current state of the art in
computational topology. It is intended for computational
geometers and combinatorialists.},
Key = {fds324399}
}

@article{fds243583,
Author = {Edelsbrunner, H and Harer, J and Patel, AK},
Title = {Reeb spaces of piecewise linear mappings},
Journal = {Proceedings of the Annual Symposium on Computational
Geometry},
Pages = {242-250},
Year = {2008},
url = {http://dx.doi.org/10.1145/1377676.1377720},
Abstract = {Generalizing the concept of a Reeb graph, the Reeb space of
a multivariate continuous mapping identifies points of the
domain that belong to a common component of the preimage of
a point in the range. We study the local and global
structure of this space for generic, piecewise linear
mappings on a combinatorial manifold. Copyright 2008
ACM.},
Doi = {10.1145/1377676.1377720},
Key = {fds243583}
}

@article{fds243605,
Author = {Edelsbrunner, H and Harer, J and Mascarenhas, A and Pascucci, V and Snoeyink, J},
Title = {Time-varying Reeb graphs for continuous space-time
data},
Journal = {Computational Geometry},
Volume = {41},
Number = {3},
Pages = {149-166},
Year = {2008},
ISSN = {0925-7721},
url = {http://dx.doi.org/10.1016/j.comgeo.2007.11.001},
Abstract = {The Reeb graph is a useful tool in visualizing real-valued
data obtained from computational simulations of physical
processes. We characterize the evolution of the Reeb graph
of a time-varying continuous function defined in
three-dimensional space. We show how to maintain the Reeb
graph over time and compress the entire sequence of Reeb
graphs into a single, partially persistent data structure,
and augment this data structure with Betti numbers to
describe the topology of level sets and with path seeds to
assist in the fast extraction of level sets for
Doi = {10.1016/j.comgeo.2007.11.001},
Key = {fds243605}
}

@article{fds243606,
Author = {Cohen-Steiner, D and Edelsbrunner, H and Harer,
J},
Title = {Stability of Persistence Diagrams},
Journal = {Discrete & Computational Geometry},
Volume = {37},
Number = {1},
Pages = {103-120},
Year = {2007},
Month = {January},
ISSN = {0179-5376},
url = {http://dx.doi.org/10.1007/s00454-006-1276-5},
Abstract = {The persistence diagram of a real-valued function on a
topological space is a multiset of points in the extended
plane. We prove that under mild assumptions on the function,
the persistence diagram is stable: small changes in the
function imply only small changes in the diagram. We apply
this result to estimating the homology of sets in a metric
space and to comparing and classifying geometric shapes. ©
2006 Springer.},
Doi = {10.1007/s00454-006-1276-5},
Key = {fds243606}
}

@article{fds243581,
Author = {Attali, D and Edelsbrunner, H and Harer, J and Mileyko,
Y},
Title = {Alpha-beta witness complexes},
Journal = {Lecture Notes in Computer Science (Including Subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {4619 LNCS},
Pages = {386-397},
Year = {2007},
ISSN = {0302-9743},
Abstract = {Building on the work of Martinetz, Schulten and de Silva,
Carlsson, we introduce a 2-parameter family of witness
complexes and algorithms for constructing them. This family
can be used to determine the gross topology of point cloud
data in ℝ d or other metric spaces. The 2-parameter family
is sensitive to differences in sampling density and thus
amenable to detecting patterns within the data set. It also
lends itself to theoretical analysis. For example, we can
prove that in the limit, when the witnesses cover the entire
domain, witness complexes in the family that share the
first, scale parameter have the same homotopy type. ©
Springer-Verlag Berlin Heidelberg 2007.},
Key = {fds243581}
}

@article{fds243582,
Author = {Bendice, P and Cohen-Steiner, D and Edelsbrunner, H and Harer, J and Morozov, D},
Title = {Inferring local homology from sampled stratified
spaces},
Journal = {Annual Symposium on Foundations of Computer Science
(Proceedings)},
Pages = {536-546},
Year = {2007},
ISSN = {0272-5428},
url = {http://www.cs.duke.edu/~edels/Topology/},
Abstract = {We study the reconstruction of a stratified space from a
possibly noisy point sample. Specifically, we use the
vineyard of the distance function restricted to a
1-parameter family of neighborhoods of a point to assess the
local homology of the stratified space at that point. We
prove the correctness of this assessment under the
assumption of a sufficiently dense sample. We also give an
algorithm that constructs the vineyard and makes the local
assessment in time at most cubic in the size of the Delaunay
triangulation of the point sample. © 2007
IEEE.},
Doi = {10.1109/FOCS.2007.4389523},
Key = {fds243582}
}

@article{fds324400,
Author = {Bendich, P and Cohen-Steiner, D and Edelsbrunner, H and Harer, J and Morozov, D},
Title = {Inferring Local Homology from Sampled Stratified
Spaces.},
Journal = {FOCS},
Pages = {536-546},
Publisher = {IEEE Computer Society},
Year = {2007},
ISBN = {978-0-7695-3010-9},
url = {http://dx.doi.org/10.1109/FOCS.2007.33},
Doi = {10.1109/FOCS.2007.33},
Key = {fds324400}
}

@article{fds324401,
Author = {Bendich, P and Cohen-Steiner, D and Edelsbrunner, H and Harer, J and Morozov, D},
Title = {Inferring local homology from sampled stratified
spaces},
Journal = {Annual Symposium on Foundations of Computer Science
(Proceedings)},
Pages = {536-546},
Year = {2007},
ISBN = {978-0-7695-3010-9},
url = {http://dx.doi.org/10.1109/FOCS.2007.45},
Doi = {10.1109/FOCS.2007.45},
Key = {fds324401}
}

@article{fds243590,
Author = {Agarwal, PK and Edelsbrunner, H and Harer, J and Wang,
Y},
Title = {Extreme elevation on a 2-manifold},
Journal = {Discrete & Computational Geometry},
Volume = {36},
Number = {4},
Pages = {553-572},
Year = {2006},
ISSN = {0179-5376},
url = {http://dx.doi.org/10.1007/s00454-006-1265-8},
Abstract = {Given a smoothly embedded 2-manifold in ℝ3, we define the
elevation of a point as the height difference to a
canonically defined second point on the same manifold. Our
definition is invariant under rigid motions and can be used
to define features such as lines of discontinuous or
continuous but non-smooth elevation. We give an algorithm
for finding points of locally maximum elevation, which we
suggest mark cavities and protrusions and are useful in
matching shapes as for example in protein docking. ©
Springer 2006.},
Doi = {10.1007/s00454-006-1265-8},
Key = {fds243590}
}

@article{fds243580,
Author = {Cohen-Steiner, D and Edelsbrunner, H and Harer,
J},
Title = {Stability of persistence diagrams},
Journal = {Proceedings of the Annual Symposium on Computational
Geometry},
Pages = {263-271},
Year = {2005},
url = {http://dx.doi.org/10.1145/1064092.1064133},
Abstract = {The persistence diagram of a real-valued function on a
topological space is a multiset of points in the extended
plane. We prove that under mild assumptions on the function,
the persistence diagram is stable: small changes in the
function imply only small changes in the diagram. We apply
this result to estimating the homology of sets in a metric
space and to comparing and classifying geometric shapes.
Doi = {10.1145/1064092.1064133},
Key = {fds243580}
}

@article{fds243578,
Author = {J. Harer and Edelsbrunner, H and Harer, J and Mascarenhas, A and Pascucci,
V},
Title = {Time-varying Reeb graphs for continuous space-time
data},
Journal = {Proceedings of the Annual Symposium on Computational
Geometry},
Pages = {366-372},
Year = {2004},
Abstract = {We study the evolution of the Reeb graph of a time-varying
continuous function defined in three-dimensional space.
While maintaining the Reeb graph, we compress the evolving
sequence into a single, partially persistent data structure.
We envision this data structure as a useful tool in
visualizing real-valued space-time data obtained from
computational simulations of physical processes.},
Key = {fds243578}
}

@article{fds243579,
Author = {J. Harer and Edelsbrunner, H and Harer, J and Natarajan, V and Pascucci,
V},
Title = {Local and global comparison of continuous
functions},
Journal = {IEEE Visualization 2004 - Proceedings, VIS
2004},
Pages = {275-280},
Year = {2004},
Abstract = {We introduce local and global comparison measures for a
collection of k ≤ d real-valued smooth functions on a
common d-dimensional Riemannian manifold. For k = d = 2 we
relate the measures to the set of critical points of one
function restricted to the level sets of the other. The
definition of the measures extends to piecewise linear
functions for which they are easy to compute. The
computation of the measures forms the centerpiece of a
software tool which we use to study scientific datasets. ©
2004 IEEE.},
Key = {fds243579}
}

@article{fds243589,
Author = {J. Harer and Agarwal, PK and Edelsbrunner, H and Harer, J and Wang,
Y},
Title = {Extreme elevation on a 2-manifold},
Journal = {Proceedings of the Annual Symposium on Computational
Geometry},
Pages = {357-365},
Year = {2004},
Abstract = {Given a smoothly embedded 2-manifold in ℝ 3, we define the
elevation of a point as the height difference to a
canonically defined second point on the same manifold. Our
definition is invariant under rigid motions and can be used
to define features such as lines of discontinuous or
continuous but non-smooth elevation. We give an algorithm
for finding points of locally maximum elevation, which we
suggest mark cavities and protrusions and are useful in
matching shapes as for example in protein
docking.},
Key = {fds243589}
}

@article{fds243607,
Author = {J. Harer and Cole-McLaughlin, K and Edelsbrunner, H and Harer, J and Natarajan, V and Pascucci, V},
Title = {Loops in Reeb graphs of 2-manifolds},
Journal = {Discrete and Computanional Geometry},
Volume = {32},
Number = {2},
Pages = {231-244},
Year = {2004},
Abstract = {Given a Morse function f over a 2-manifold with or without
boundary, the Reeb graph is obtained by contracting the
connected components of the level sets to points. We prove
tight upper and lower bounds on the number of loops in the
Reeb graph that depend on the genus, the number of boundary
components, and whether or not the 2-manifold is orientable.
We also give an algorithm that constructs the Reeb graph in
time O(n log n), where n is the number of edges in the
triangulation used to represent the 2-manifold and the Morse
function.},
Key = {fds243607}
}

@article{fds318291,
Author = {Cole-McLaughlin, K and Edelsbrunner, H and Harer, J and Natarajan, V and Pascucci, V},
Title = {Loops in Reeb graphs of 2-manifolds},
Journal = {Proceedings of the Annual Symposium on Computational
Geometry},
Pages = {344-350},
Year = {2003},
Month = {July},
Abstract = {Given a Morse function f over a 2-manifold with or without
boundary, the Reeb graph is obtained by contracting the
connected components of the level sets to points. We prove
tight upper and lower bounds on the number of loops in the
Reeb graph that depend on the genus, the number of boundary
components, and whether or not the 2-manifold is orientable.
We also give an algorithm that constructs the Reeb graph in
time O(n log n), where n is the number of edges in the
triangulation used to represent the 2-manifold and the Morse
function.},
Key = {fds318291}
}

@article{fds243576,
Author = {J. Harer and Edelsbrunner, H and Harer, J and Natarajan, V and Pascucci,
V},
Title = {Morse-Smale complexes for piecewise linear
3-manifolds},
Journal = {Proceedings of the Annual Symposium on Computational
Geometry},
Pages = {361-370},
Year = {2003},
Abstract = {We define the Morse-Smale complex of a Morse function over a
3-manifold as the overlay of the descending and ascending
manifolds of all critical points. In the generic case, its
3-dimensional cells are shaped like crystals and are
separated by quadrangular faces. In this paper, we give a
combinatorial algorithm for constructing such complexes for
piecewise linear data.},
Key = {fds243576}
}

@article{fds243577,
Author = {Edelsbrunner, H and Harer, J and Zomorodian, A},
Title = {Hierarchical Morse-Smale complexes for piecewise linear
2-manifolds},
Journal = {Discrete & Computational Geometry},
Volume = {30},
Number = {1},
Pages = {87-107},
Year = {2003},
ISSN = {0179-5376},
url = {http://dx.doi.org/10.1007/s00454-003-2926-5},
Abstract = {We present algorithms for constructing a hierarchy of
increasingly coarse Morse-Smale complexes that decompose a
piecewise linear 2-manifold. While these complexes are
defined only in the smooth category, we extend the
construction to the piecewise linear category by ensuring
structural integrity and simulating differentiability. We
then simplify Morse-Smale complexes by canceling pairs of
critical points in order of increasing persistence.},
Doi = {10.1007/s00454-003-2926-5},
Key = {fds243577}
}

@article{fds243588,
Author = {J. Harer and Collins, AD and Agarwal, PK and Harer, JL},
Title = {HPRM: A hierarchical PRM},
Journal = {Proceedings - IEEE International Conference on Robotics and
Automation},
Volume = {3},
Pages = {4433-4438},
Year = {2003},
Abstract = {We introduce a hierarchical variant of the probabilistic
roadmap method for motion planning. By recursively refining
an initially sparse sampling in neighborhoods of the
C-obstacle boundary, our algorithm generates a smaller
roadmap that is more likely to find narrow passages than
uniform sampling. We analyze the failure probability and
computation time, relating them to path length, path
clearance, roadmap size, recursion depth, and a local
property of the free space. The approach is general, and can
be tailored to any variety of robots. In particular, we
describe algorithmic details for a planar articulated
arm.},
Key = {fds243588}
}

@article{fds29135,
Author = {J. Harer and H. Edelsbrunner.},
Title = {Jacobi sets of multiple Morse functions.},
Journal = {Foundations of Computational Mathematics, Minneapolis, eds.
F. Cucker, R. DeVore, P. Olver and E. Sueli, Cambridge Univ.
Press, England,},
Pages = {37-57},
Year = {2002},
Abstract = {The Jacobi set of two Morse functions defined on a common
d-manifold is the set of critical points of the restrictions
of one function to the level sets of the other function.
Equivalently, it is the set of points where the gradients of
the functions are parallel. For a generic pair of Morse
functions, the Jacobi set is a smoothly embedded 1-manifold.
We give a polynomial-time algorithm that computes the
piecewise linear analog of the Jacobi set for functions
specified at the vertices of a triangulation, and we
generalize all results to more than two but at most d Morse
functions.},
Key = {fds29135}
}

@article{fds243573,
Author = {Goulden, IP and Harer, JL and Jackson, DM},
Title = {A geometric parametrization for the virtual euler
characteristics of the moduli spaces of real and complex
algebraic curves},
Journal = {Transactions of the American Mathematical
Society},
Volume = {353},
Number = {11},
Pages = {4405-4427},
Year = {2001},
ISSN = {0002-9947},
MRNUMBER = {1851176},
url = {http://www.ams.org/mathscinet-getitem?mr=1851176},
Abstract = {We determine an expression ξgs(γ) for the virtual Euler
characteristics of the moduli spaces of s-pointed real (7 =
1/2) and complex (7 = 1) algebraic curves. In particular,
for the space of real curves of genus g with a fixed point
free involution, we find that the Euler characteristic is
(-2)s-1(1-2q-1)(g+s-2)!Bg/g! where gth is the gth Bernoulli
number. This complements the result of Harer and Zagier that
the Euler characteristic of the moduli space of complex
algebraic curves is (-1)s(g+s-2)!Bg+1/(g+1)(g- 1)! The proof
uses Strcbel differentials to triangulate the moduli spaces
and some recent techniques for map enumeration to count
cells. The approach involves a parameter γ that permits
specialization of the formula to the real and complex cases.
This suggests that ξgs(γ) itself may describe the Eulcr
characteristics of some related moduli spaces, although we
do not yet know what these spaces might be. ©2001 American
Mathematical Society.},
Key = {fds243573}
}

@article{fds243574,
Author = {Edelsbrunner, H and Harer, J and Zomorodian, A},
Title = {Hierarchical Morse complexes for piecewise linear
2-manifolds},
Journal = {Proceedings of the Annual Symposium on Computational
Geometry},
Pages = {70-79},
Year = {2001},
Abstract = {We present algorithms for constructing a hierarchy of
increasingly coarse Morse complexes that decompose a
piecewise linear 2-manifold. While Morse complexes are
defined only in the smooth category, we extend the
construction to the piecewise linear category by ensuring
structural integrity and simulating differentiability. We
then simplify Morse complexes by cancelling pairs of
critical points in order of increasing persistence.},
Key = {fds243574}
}

@article{fds243587,
Author = {Agarwal, PK and Collins, AD and Harer, JL},
Title = {Minimal trap design},
Journal = {Proceedings - IEEE International Conference on Robotics and
Automation},
Volume = {3},
Pages = {2243-2248},
Year = {2001},
Abstract = {This paper addresses the issue of trap design for sensorless
automated assembly. First, we present a simple algorithm
that determines in O(nm α(nm) log(nm)) time whether an
n-sided polygonal part will fall through an m-sided
polygonal trap. We then introduce the notion of a minimal
trap for a polygonal part, and develop an algorithm to
design a family of minimal feeders built from these traps.
The algorithm runs in O(kn3+ε) time, where k is the number
of stable orientations of P. Moreover, it is complete in the
sense that we can always find a feeder, provided that one
exists that rejects and supports the appropriate poses of
the part.},
Key = {fds243587}
}

@article{fds321993,
Author = {HARER, J},
Title = {THE 3RD HOMOLOGY GROUP OF THE MODULI SPACE OF
CURVES},
Journal = {Duke Mathematical Journal},
Volume = {63},
Number = {1},
Pages = {25-55},
Year = {1991},
Month = {June},
url = {http://dx.doi.org/10.1215/S0012-7094-91-06302-7},
Doi = {10.1215/S0012-7094-91-06302-7},
Key = {fds321993}
}

@article{fds243572,
Author = {Harer, JL},
Title = {Stability of the homology of the moduli spaces of Riemann
surfaces with spin structure},
Journal = {Mathematische Annalen},
Volume = {287},
Number = {1},
Pages = {323-334},
Year = {1990},
ISSN = {0025-5831},
MRNUMBER = {91e:57002},
url = {http://dx.doi.org/10.1007/BF01446896},
Doi = {10.1007/BF01446896},
Key = {fds243572}
}

@article{fds324402,
Author = {HARER, J and KAS, A and KIRBY, R},
Title = {HANDLEBODY STRUCTURES FOR COMPLEX-SURFACES},
Journal = {Memoirs of the American Mathematical Society},
Volume = {62},
Number = {350},
Pages = {1-102},
Year = {1986},
Month = {July},
Key = {fds324402}
}

@article{fds243570,
Author = {HARER, J},
Title = {The virtual cohomological dimension of the mapping class
group of an orientable surface},
Journal = {Invent. Math.},
Volume = {84},
Number = {1},
Pages = {157-176},
Year = {1986},
ISSN = {0020-9910},
MRNUMBER = {87c:32030},
url = {http://dx.doi.org/10.1007/BF01388737},
Doi = {10.1007/BF01388737},
Key = {fds243570}
}

@article{fds243571,
Author = {Harer, J and Zagier, D},
Title = {The Euler characteristic of the moduli space of
curves},
Journal = {Inventiones Mathematicae},
Volume = {85},
Number = {3},
Pages = {457-485},
Year = {1986},
ISSN = {0020-9910},
MRNUMBER = {87i:32031},
url = {http://dx.doi.org/10.1007/BF01390325},
Doi = {10.1007/BF01390325},
Key = {fds243571}
}

@article{fds243569,
Author = {Harer, J},
Title = {The second homology group of the mapping class group of an
orientable surface},
Journal = {Inventiones Mathematicae},
Volume = {72},
Number = {2},
Pages = {221-239},
Year = {1983},
Month = {June},
ISSN = {0020-9910},
MRNUMBER = {84g:57006},
url = {http://dx.doi.org/10.1007/BF01389321},
Doi = {10.1007/BF01389321},
Key = {fds243569}
}

@article{fds324403,
Author = {HARER, JL},
Title = {The second homology group of the mapping class group of an
orientable surface},
Journal = {Invent.Math.},
Volume = {72},
Pages = {221-239},
Year = {1983},
url = {http://dx.doi.org/10.1007/BF01389321},
Doi = {10.1007/BF01389321},
Key = {fds324403}
}

@article{fds243567,
Author = {HARER, J},
Title = {How to construct all fibered knots and links},
Journal = {Topology},
Volume = {21},
Number = {3},
Pages = {263-280},
Year = {1982},
ISSN = {0040-9383},
MRNUMBER = {83e:57007},
url = {http://dx.doi.org/10.1016/0040-9383(82)90009-X},
Doi = {10.1016/0040-9383(82)90009-X},
Key = {fds243567}
}

@article{fds324404,
Author = {HARER, J},
Title = {REPRESENTING ELEMENTS OF PI-1M3 BY FIBERED
KNOTS},
Journal = {Cambridge Philosophical Society: Mathematical
Proceedings},
Volume = {92},
Number = {JUL},
Pages = {133-138},
Year = {1982},
url = {http://dx.doi.org/10.1017/S030500410005979X},
Doi = {10.1017/S030500410005979X},
Key = {fds324404}
}

@article{fds321994,
Author = {Casson, A and Harer, J},
Title = {Some homology lens spaces which bound rational homology
balls},
Journal = {Pacific Journal of Mathematics},
Volume = {96},
Number = {1},
Pages = {23-36},
Year = {1981},
Month = {September},
MRNUMBER = {83h:57013},
url = {http://dx.doi.org/10.2140/pjm.1981.96.23},
Doi = {10.2140/pjm.1981.96.23},
Key = {fds321994}
}

@article{fds243568,
Author = {Harer, J},
Title = {On handlebody structures for hypersurfaces in
ℂ3 and ℂP3},
Journal = {Mathematische Annalen},
Volume = {238},
Number = {1},
Pages = {51-58},
Year = {1978},
ISSN = {0025-5831},
MRNUMBER = {80d:57020},
url = {http://dx.doi.org/10.1007/BF01351453},
Doi = {10.1007/BF01351453},
Key = {fds243568}
}

@article{fds10017,
Author = {Harer, John L.},
Title = {The rational Picard group of the moduli space of Riemann
surfaces with spin structure},
Journal = {Mapping class groups and moduli spaces of Riemann surfaces
(Gottingen, 1991/Seattle, WA, 1991), pp. 107--136, 1993,
Amer. Math. Soc., Providence, RI},
MRNUMBER = {94h:14008},
url = {http://www.ams.org/mathscinet-getitem?mr=94h:14008},
Key = {fds10017}
}

@article{fds10019,
Author = {Harer, John},
Title = {The third homology group of the moduli space of
curves},
Journal = {Duke Math. J., vol. 63, no. 1, pp. 25--55,
1991},
MRNUMBER = {92d:57012},
url = {http://www.ams.org/mathscinet-getitem?mr=92d:57012},
Key = {fds10019}
}

@article{fds10021,
Author = {Harer, John L.},
Title = {The cohomology of the moduli space of curves},
Journal = {Theory of moduli (Montecatini Terme, 1985), pp. 138--221,
1988, Springer, Berlin},
MRNUMBER = {90a:32026},
url = {http://www.ams.org/mathscinet-getitem?mr=90a:32026},
Key = {fds10021}
}

@article{fds10022,
Author = {Harer, John and Kas, Arnold and Kirby, Robion},
Title = {Handlebody decompositions of complex surfaces},
Journal = {Mem. Amer. Math. Soc., vol. 62, no. 350, pp. iv+102,
1986},
MRNUMBER = {88e:57030},
url = {http://www.ams.org/mathscinet-getitem?mr=88e:57030},
Key = {fds10022}
}

@article{fds10024,
Author = {Harer, John L.},
Title = {Stability of the homology of the mapping class groups of
orientable surfaces},
Journal = {Ann. of Math. (2), vol. 121, no. 2, pp. 215--249,
1985},
MRNUMBER = {87f:57009},
url = {http://www.ams.org/mathscinet-getitem?mr=87f:57009},
Key = {fds10024}
}

@article{fds10026,
Title = {Geometry and topology},
Journal = {Proceedings of the special year held at the University of
Maryland, College Park, Md., 1983/84, edited by Alexander,
J. and Harer, J., pp. vi+292, 1985, Springer-Verlag,
Berlin},
MRNUMBER = {87a:57003},
url = {http://www.ams.org/mathscinet-getitem?mr=87a:57003},
Key = {fds10026}
}

@article{fds10027,
Author = {Harer, John},
Title = {The homology of the mapping class group and its connection
to surface bundles over surfaces},
Journal = {Four-manifold theory (Durham, N.H., 1982), pp. 311--314,
1984, Amer. Math. Soc., Providence, RI},
MRNUMBER = {86c:57010},
url = {http://www.ams.org/mathscinet-getitem?mr=86c:57010},
Key = {fds10027}
}

@article{fds10029,
Author = {Harer, John},
Title = {Representing elements of pi1(M3)
by fibred knots},
Journal = {Math. Proc. Cambridge Philos. Soc., vol. 92, no. 1, pp.
133--138, 1982},
MRNUMBER = {83j:57005},
url = {http://www.ams.org/mathscinet-getitem?mr=83j:57005},
Key = {fds10029}
}

%% Papers Accepted
@article{fds321991,
Author = {Bendich, P and Gasparovic, E and Harer, J and Izmailov, R and Ness,
L},
Title = {Multi-scale local shape analysis and feature selection in
machine learning applications},
Journal = {Proceedings of the International Joint Conference on Neural
Networks},
Volume = {2015-September},
Year = {2015},
Month = {September},
url = {http://dx.doi.org/10.1109/IJCNN.2015.7280428},
Abstract = {© 2015 IEEE. We introduce a method called multi-scale local
shape analysis for extracting features that describe the
local structure of points within a dataset. The method uses
both geometric and topological features at multiple levels
of granularity to capture diverse types of local information
for subsequent machine learning algorithms operating on the
dataset. Using synthetic and real dataset examples, we
demonstrate significant performance improvement of
classification algorithms constructed for these datasets
with correspondingly augmented features.},
Doi = {10.1109/IJCNN.2015.7280428},
Key = {fds321991}
}

@article{fds225825,
Author = {E. Munch and P. Bendich and K. Turner and S. Mukherjee and J. Mattingly and J. Harer},
Title = {Probabilistic Frechet Means and Statistics on
Vineyards},
Journal = {Foundations of Computational Math},
Year = {2014},
Abstract = {In order to use persistence diagrams as a true statistical
tool, it would be very useful to have a good notion of mean
and variance for a set of diagrams. In [21], Mileyko and his
collaborators made the first study of the properties of the
Fr ́echet mean in (Dp,Wp), the space of persistence
diagrams equipped with the p-th Wasserstein metric. In
particular, they showed that the Fr ́echet mean of a finite
set of diagrams always exists, but is not necessarily
unique. As an unfortunate consequence, one sees that the
means of a continuously-varying set of diagrams do not
themselves vary continuously, which presents obvious
problems when trying to extend the Fr ́echet mean
definition to the realm of vineyards. We fix this problem by
altering the original definition of Fr ́echet mean so that
it now becomes a probability measure on the set of
persistence diagrams; in a nutshell, the mean of a set of
diagrams will be a weighted sum of atomic measures, where
each atom is itself the (Fr ́echet mean) persistence
diagram of a perturbation of the input diagrams. We show
that this new definition defines a (H ̈older) continuous
map, for each k, from (Dp)k → P(Dp), and we present
several examples to show how it may become a useful
statistic on vineyards.},
Key = {fds225825}
}

%% Papers Submitted
@article{fds321989,
Author = {McGoff, KA and Guo, X and Deckard, A and Kelliher, CM and Leman, AR and Francey, LJ and Hogenesch, JB and Haase, SB and Harer,
JL},
Title = {The Local Edge Machine: inference of dynamic models of gene
regulation.},
Journal = {Genome Biology},
Volume = {17},
Number = {1},
Pages = {214},
Year = {2016},
Month = {October},
url = {http://dx.doi.org/10.1186/s13059-016-1076-z},
Abstract = {We present a novel approach, the Local Edge Machine, for the
inference of regulatory interactions directly from
time-series gene expression data. We demonstrate its
performance, robustness, and scalability on in silico
datasets with varying behaviors, sizes, and degrees of
complexity. Moreover, we demonstrate its ability to
incorporate biological prior information and make
informative predictions on a well-characterized in vivo
system using data from budding yeast that have been
synchronized in the cell cycle. Finally, we use an atlas of
transcription data in a mammalian circadian system to
illustrate how the method can be used for discovery in the
context of large complex networks.},
Doi = {10.1186/s13059-016-1076-z},
Key = {fds321989}
}

@article{fds225821,
Author = {J. Perea and A. Deckard and S. Haase and J. Harer},
Title = {Sliding Windows and 1-Persistence Scoring; Discovering
Periodicity in Gene Expression Time Series
Data},
Journal = {BMC Bioinformatics},
Year = {2014},
Abstract = {Motivation: Identifying periodically expressed genes across
different processes such as the cell cy- cle, circadian
rhythms, and metabolic cycles, is a central problem in
computational biology. Biological time series data may
contain (multiple) unknown sig- nal shapes, have
imperfections such as noise, damp- ing, and trending, or
have limited sampling density. While many methods exist for
detecting periodicity, their design biases can limit their
applicability in one or more of these situations. Methods:
We present in this paper a novel method, SW1PerS, for
quantifying periodicity in time se- ries data. The
measurement is performed directly, without presupposing a
particular shape or pattern, by evaluating the circularity
of a high-dimensional representation of the signal. SW1PerS
is compared to other algorithms using synthetic data and
perfor- mance is quantified under varying noise levels, sam-
pling densities, and signal shapes. Results on biolog- ical
data are also analyzed and compared; this data includes
different periodic processes from various or- ganisms: the
cell and metabolic cycles in S. cere- visiae, and the
circadian rhythms in M. musculus. ∗Department of
Mathematics, Duke University, USA and Institute for
Mathematics and its Applications, University of Minnesota,
USA. †Program in Computational Biology and Bioinformatics,
Duke University, USA. ‡Center for Systems Biology,
Institute for Genome Sciences & Policy, Duke University,
USA. §Departments of Mathematics, Computer Science and
Elec- trical and Computer Engineering, Duke University, USA.
Results: On the task of periodic/not-periodic clas-
sification, using synthetic data, SW1PerS performs on par
with successful methods in periodicity detec- tion.
Moreover, it outperforms Lomb-Scargle and JTK CYCLE in the
high-noise/low-sampling range. SW1PerS is shown to be the
most shape-agnostic of the evaluated methods, and the only
one to consis- tently classify damped signals as highly
periodic. On biological data, and for several experiments,
the lists of top 10% genes ranked with SW1PerS recover up to
67% of those generated with other popular algo- rithms.
Moreover, lists of genes which are highly- ranked only by
SW1PerS contain non-cosine patterns (e.g. ECM33, CDC9,
SAM1,2 and MSH6 in the Yeast metabolic cycle data of Tu et
al. (2005)) which are highly periodic. In the Yeast cell
cycle data SW1PerS identifies genes not preferred by other
algorithms, not previously reported in Orlando et al.
(2008); Spell- man et al. (1998), but found in other
experiments such as the universal growth rate response of
Slavov and Botstein (2011). These genes are BOP3, CDC10,
YIL108W, YER034W, MLP1, PAC2 and RTT101.},
Key = {fds225821}
}

@article{fds225822,
Author = {K.A. McGoff and X. Guo and A. Deckard and A.R. Leman and C.M. Kelliher and S.B. Haase and J.L. Harer},
Title = {The Local Edge Machine: Inference of dynamic models of gene
regulation},
Journal = {Nature Methods},
Year = {2014},
Abstract = {This paper develops the state of the art methodology for
inferring gene regulatory networks from gene expression data
for periodic processes. Application is made to finding
networks for cell cycle and circadian clocks.},
Key = {fds225822}
}

@article{fds225823,
Author = {P. Bendich and S. Chin and J. Clarke and J. deSena, J. Harer and E.
Munch, A. Newman and D. Porter and D. Rouse and N. Strawn and A.
Watkins},
Title = {Topological and Statistical Behavior Classifiers for
Tracking Applications},
Journal = {IEEE Trans. on Aerospace and Electronic Systems},
Year = {2014},
Abstract = {We introduce the first unified theory for target tracking
using Multiple Hypothesis Tracking, Topological Data
Analysis, and machine learning. Our string of innovations
are 1) robust topological features are used to encode
behavioral information, 2) statistical models are fitted to
distributions over these topological features, and 3) the
target type classification methods of Wigren and Bar Shalom
et al. are employed to exploit the resulting likelihoods for
topological features inside of the tracking procedure. To
demonstrate the efficacy of our approach, we test our
procedure on synthetic vehicular data generated by the
Simulation of Urban Mobility package.},
Key = {fds225823}
}

@article{fds225826,
Author = {P. Bendich and Jacob Harer and John Harer},
Title = {A Persistent Homology Based Geodesic Distance
Estimator},
Journal = {Journal of Machine Learning Research},
Year = {2014},
Key = {fds225826}
}

@article{fds221211,
Author = {J. Perea and A. Deckard and S. Haase and J. Harer},
Title = {Applications of SWiPerS to the discovery of periodic
genes},
Year = {2013},
Key = {fds221211}
}

@article{fds221202,
Author = {Sara Bristow and Laura A. Simmons Kovacs and Anastasia Deckard and John Harer and Steven B. Haase},
Title = {Checkpoint Pathways Couple the CDK-Independent
Transcriptional Oscillations to Cell Cycle
Progression},
Year = {2013},
Abstract = {A study of how checkpoint pathways control the yeast cell
cycle, derived from methods of finding periodic genes and
cell cycle experiments from the Haase Lab.},
Key = {fds221202}
}

@article{fds243592,
Author = {Bendich, P and Harer, J and Harer, J},
Title = {Persistent Homology Enhanced Dimension Reduction},
Journal = {Foundations of Computational Mathematics},
Year = {2012},
Key = {fds243592}
}

@article{fds243593,
Author = {Michael Jenista},
Title = {Realizing Boolean Dynamics in Switching Networks},
Journal = {Siam Journal of Applied Dynamical Systems},
Pages = {12},
Year = {2012},
Abstract = {Switching networks are a common model for biological
systems, especially for genetic transcription networks.
Stuart Kaufman originally proposed the usefulness of the
Boolean framework, but much of the dynamical features there
are not realizable in a continuous analogue. We introduce
the notion of braid-like dynamics as a bridge between
Boolean and continuous dynamics and study its importance in
the local dynamics of ring and ring-like networks. We
discuss a near-theorem on the global dynamics of general
feedback networks, and in the nal chapter study the main
ideas of this thesis in models of a yeast cell transcription
network.},
Key = {fds243593}
}

@article{fds166039,
Author = {P. Bendich and J. Harer},
Title = {Elevation for singular spaces using persistent intersection
homology},
Year = {2009},
Key = {fds166039}
}

@article{fds166033,
Author = {Mehak Aziz and Siobhan M. Brady and David Orlando and Appu Kuruvilla and Scott Spillias and José R. Dinneny and Terri A. Long and John Harer and Uwe Ohler and Philip N. Benfey},
Title = {Gene Expression Clustering Analysis: How to Choose the Best
Parameters and Clustering Algorithm},
Year = {2008},
Abstract = {This paper is the result of a summer research project
supported by the Howard Hughes summer program in systems
biology.},
Key = {fds166033}
}

%% Preprints
@article{fds243604,
Author = {Fink, T and Ahnert, S and Bar On and R and Harer, J},
Title = {Exact dynamics of Boolean networks with connectivity
one},
Journal = {PRL},
Year = {2009},
Abstract = {We study boolean dynamics on the simplest class of network
topologies: those in which each node has a single input (K =
1). Despite their simplicity, they exhibit highly intricate
bahaviour. We give the exact solution for the size and
number of attractors on a loop and multiple loops of the
same size. By expressing the dynamics of a network as a
composition of the dynamics of its modules, we give a
detailed solution to the critical K = 1 Kauﬀman model, and
show that the minimum number of attractors scales as
2n−√2n log2 √2n , where n is the number of nodes in
loops.},
Key = {fds243604}
}

@article{fds8935,
Author = {John Harer},
Title = {Algorithms for Enumerating Triangulations and Other Maps in
Surfaces},
Journal = {1998},
Key = {fds8935}
}

@article{fds8938,
Author = {John Harer},
Title = {An Alternative Approach to Trap Design for Vibratory Bowl
Feeders},
Journal = {1998},
Key = {fds8938}
}

@article{fds8940,
Author = {John Harer},
Title = {The Euler Characteristic of the Deligne-Mumford
Compactification of the Moduli Space of Curves},
Journal = {1996},
Key = {fds8940}
}

%% Other
@misc{fds29132,
Author = {J. Harer and H. Edelsbrunner},
Title = {Persistent Morse Complex Segmentation of a
3-Manifold},
Journal = {Raindrop Geomagic Technical Report},
Volume = {066},
Year = {2004},
Abstract = {We describe a new algorithm for segmenting 3-dimensional
medical imaging data, which we abstract as continuous
functions on 3-manifolds. The algorithm is related to
watershed algorithms developed in image processing but is
closer to its mathematical roots, which are Morse theory and
homological algebra. It allows for the implicit treatment of
its mathematical foundations with the computational
efficiency of image processing.},
Key = {fds29132}
}



dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320