Models for DNA-based Tile Self-Assembly
- Series
- Research Horizons Seminar
- Time
- Wednesday, October 23, 2019 - 12:20 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Daniel Cruz – Georgia Tech
A central pervasive challenge in genomics is that RNA/DNA must be reconstructed from short, often noisy subsequences. In this talk, we describe a new digraph algorithm which enables this "assembly" when analyzing high-throughput transcriptomic sequencing data. Specifically, the Flow Decomposition problem on a directed ayclic graph asks for the smallest set of weighted paths that “cover” a flow (a weight function on the edges where the amount coming into any vertex is equal to the amount leaving). We describe a new linear-time algorithm solving *k*-Flow Decomposition, the variant where exactly *k* paths are used. Further, we discuss how we implemented and engineered a general Flow Decomposition solver based on this algorithm, and describe its performance on RNA-sequence data. Crucially, our solver finds exact solutions while achieving runtimes competitive with a state-of-the-art heuristic, and we discuss the implications of our results on the original model selection for transcript assembly in this setting.
I will present a new method of analysis for Einstein’s
constraint equations, referred to as the Seed-to-Solution Method, which
leads to the existence of asymptotically Euclidean manifolds with
prescribed asymptotic behavior. This method generates a (Riemannian)
Einstein manifold from any seed data set consisting of (1): a Riemannian
metric and a symmetric two-tensor prescribed on a topological manifold
with finitely many asymptotically Euclidean ends, and (2): a density
field and a momentum vector field representing the matter content. By
distinguishing between several classes of seed data referred to as tame
or strongly tame, the method encompasses metrics with the weakest
possible decay (infinite ADM mass) or the strongest possible decay
(Schwarzschild behavior). This analysis is based on a linearization of
the Einstein equations (involving several curvature operators from
Riemannian geometry) around a tame seed data set. It is motivated by
Carlotto and Schoen’s pioneering work on the so-called localization
problem for the Einstein equations. Dealing with manifolds with possibly
very low decay and establishing estimates beyond the critical level of
decay requires significantly new ideas to be presented in this talk. As
an application of our method, we introduce and solve a new problem,
referred to as the asymptotic localization problem, at the critical
level of decay. Collaboration with T. Nguyen. Blog: philippelefloch.org
This is quick tutorial on bounding the mixing time of a finite Markov chain in terms of functional inequalities defining the spectral gap and the entropy constant of a Markov chain. The lecture will include some examples, including bounding the mixing time of the random transposition shuffle and (time permitting) that of the basis-exchange walk on a balanced matroid.
This is intended as a review lecture before Nima Anari’s lectures (during Nov. 4-6) on applications of Lorentzian polynomials, including recent breakthrough analyses of the basis-exchange walk on an arbitrary matroid.
Mori Dream Spaces are generalizations of toric varieties and, as the name suggests, Mori's minimal model program can be run for every divisor. It is known that for n≥5, the blow-up of Pn at r very general points is a Mori Dream Space iff r≤n+3. In this talk we proceed to blow up points as well as lines, by considering the blow-up X of P3 at 6 points in very general position and all the 15 lines through the 6 points. We find that the unique anticanonical section of X is a Jacobian K3 Kummer surface S of Picard number 17. We prove that there exists an infinite-order pseudo-automorphism of X, whose restriction to S is one of the 192 infinite-order automorphisms constructed by Keum. A consequence is that there are infinitely many extremal effective divisors on X; in particular, X is not a Mori Dream Space. We show an application to the blow-up of Pn (n≥3) at (n+3) points and certain lines. We relate this pseudo-automorphism to the structure of the birational automorphism group of P3. This is a joint work with Lei Yang.
We consider the strong chain recurrent set and the generalized recurrent set for continuous maps of compact metric spaces. Recent work by Fathi and Pageault has shown a connection between the two sets, and has led to new results on them. We discuss a structure theorem for transitive/mixing maps, and classify maps that permit explosions in the size of the recurrent sets.
As a geometric group theorist, my favorite type of manifold is a surface and my favorite way to study surfaces is by considering the mapping class group, which is the collection of symmetries of a surface. In this talk, we will think bigger than your average low-dimensional topologist and consider surfaces of infinite type and their associated “big” mapping class groups.
While producing subgroups of a group by specifying generators is easy, understanding the structure of such a subgroup is notoriously difficult problem. In the case of hyperbolic groups, Gitik utilized a local-to-global property for geodesics to produce an elegant condition that ensures a subgroup generated by two elements (or more generally generated by two subgroups) will split as an amalgamated free product over the intersection of the generators. We show that the mapping class group of a surface and many other important groups have a similar local-to-global property from which an analogy of Gitik's result can be obtained. In the case of the mapping class group, this produces a combination theorem for the dynamically and topologically important convex cocompact subgroups. Joint work with Davide Spriano and Hung C. Tran.
This talk is based on work in progress with Sara Lamboglia and Faye Simon. We study the tropical convex hull of convex sets and of tropical curves. Basic definitions of tropical convexity and tropical curves will be presented, followed by an overview of our results on the interaction between tropical and classical convexity. Lastly, we study a tropical analogue of an inequality bounding the degree of a projective variety in classical algebraic geometry; we show a tropical proof of this result for a special class of tropical curves.