Browsing by Author "Orponen, Pekka"

Filter results by typing the first few letters
Now showing 1 - 20 of 59
  • Algorithmic design of 3D wireframe RNA polyhedra
    (2022-09-30) Elonen, Antti; Natarajan, Ashwin Karthick; Kawamata, Ibuki; Oesinghaus, Lukas; Mohammed, Abdulmelik; Seitsonen, Jani; Suzuki, Yuki; Simmel, Friedrich C.; Kuzyk, Anton; Orponen, Pekka
     A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
    We address the problem of de novo design and synthesis of nucleic acid nanostructures, a challenge that has been considered in the area of DNA nanotechnology since the 1980s and more recently in the area of RNA nanotechnology. Toward this goal, we introduce a general algorithmic design process and software pipeline for rendering 3D wireframe polyhedral nanostructures in single-stranded RNA. To initiate the pipeline, the user creates a model of the desired polyhedron using standard 3D graphic design software. As its output, the pipeline produces an RNA nucleotide sequence whose corresponding RNA primary structure can be transcribed from a DNA template and folded in the laboratory. As case examples, we design and characterize experimentally three 3D RNA nanostructures: a tetrahedron, a triangular bipyramid, and a triangular prism. The design software is openly available and also provides an export of the targeted 3D structure into the oxDNA molecular dynamics simulator for easy simulation and visualization.
  • Algorithmic design of cotranscriptionally folding 2D RNA origami structures
    (2018-05-31) Mohammed, Abdulmelik; Orponen, Pekka; Pai, Sachith
     A4 Artikkeli konferenssijulkaisussa
    We address a biochemical folding obstacle of “polymerase trapping” that arises in the remarkable RNA origami tile design framework of Geary, Rothemund and Andersen (Science 2014). We present a combinatorial formulation of this obstacle, together with an optimisation procedure that yields designs minimising the risk of encountering the corresponding topological trap in the tile folding phase. The procedure has been embedded in an automated software pipeline, and we provide examples of designs produced by the software, including an optimised version of the RNA smiley-face tile proposed by Geary and Andersen (DNA 2014).
  • Algorithmic design of RNA polyhedra
    (2018-10-08) Elonen, Antti
     Perustieteiden korkeakoulu | Master's thesis
    The field of bottom-up nanotechnology has been the subject of much research in the recent years. Most of that research has focused on creating nano-scale shapes and structures using multiple strands. DNA origamis and various tile-based schemes are perhaps the most famous examples. No such robust design schemes exist for the design of single stranded RNA structures, however, despite their potential to offer a cheap and sound approach to nanomanufacturing. In this thesis, we study the problem of designing single-stranded RNA polyhedral wireframes, i.e., such RNA strands that fold into the wireframe of a given polyhedron. We introduce a kissing-loop based design scheme, which routes an RNA strand around a spanning tree of a polyhedron, and we show how to do the routing on arbitrary polyhedra while avoiding knots. We also introduce a design tool, Sterna, which is based on these principles. It allows the user to convert a 3D model of a polyhedron into an RNA secondary and tertiary structures, which can be further developed into a primary structure with the additional scripts we have provided. Finally, we design three RNA polyhedra, which are synthesized and imaged in a project related to this master's thesis. The resulting images lend credence to the soundness of Sterna and the underlying design process.
  • Analyzing and comparing arrangements of temporal intervals
    (2011) Kostakis, Orestis
     School of Science | Master's thesis
    This thesis focuses on comparing and analysing arrangements of temporal intervals. Such arrangements are sets of concurrent events that are not instantaneous, but are characterized by duration. We study two major problems. The first problem is comparing arrangements of event-intervals and acquiring their distance. To the best of our knowledge, we are the first to formally define the problem. Furthermore, we present three polynomial-time distance functions which we study and benchmark through rigorous experimentation. The proposed methods were tested on three datasets: American Sign Language utterances, sensor data and Hepatitis patient data. In addition, we provide a linear-time lower bound for one of the distance measures. The distance measures can be applied to event-interval sequences, too. In this case, neither the event-interval durations nor the absolute time values are considered. The second problem which we study is finding the longest common sub-pattern (LCSP) of arrangements of temporal intervals. We prove hardness results for the problem and devise an exact algorithm for computing the LCSP of pairs of arrangements.
  • Applications of combinatorial algorithms in statistical physics
    (2009) Savola, Petri
     Helsinki University of Technology | Master's thesis
    Yksi keskeisistä tilastollisen mekaniikan malleista on Ising-malli. Malli koostuu spineistä, jotka voivat saada arvon 1 tai -1, ja spin-parien välisistä vuorovaikutuksista. Spin-systeemin energiamaasto on monimutkainen ja sellaista systeemin tilaa, joka minimoi tyytymättömien vuorovaikutusten määrän, on erittäin vaikea löytää. Tässä diplomityössä esitellään uusi menetelmä, jolla voidaan generoida kaikki annetun spin-systeemin metastabiilit tilat. Menetelmää voidaan käyttää esimerkiksi systeemin energiamaaston tutkimiseen. Menetelmä perustuu binääripuuhun, joka generoidaan siten, että jokainen polku juuresta lehteen vastaa yksikäsitteisesti yhtä tilaa. Kun tarkastellaan yksinkertaisia spin-systeemejä, kuten kaksiulotteista heksagonaalista hilaa, voidaan hakupuuta karsia tehokkaasti siten, että kukin metastabiili tila voidaan löytää ilman peruuttamista. Työssä osoitetaan numeerisesti, että metastabiilien tilojen lukumäärä on eksponentiaalinen spinien lukumäärän funktiona käyttämällä klassista hakupuun koon arviointimenetelmää. Lisäksi tulosten luotettavuutta arvioidaan sekä analyyttisesti että kokeellisesti. Työssä tarkastellaan myös joitain muita menetelmän käyttökohteita, kuten metastabiilien tilojen tasaista otantaa. Esitetään algoritmi, jolla voidaan generoida tiloja melkein tasaisesti ja tutkitaan sen avulla tilojen energiajakaumaa. Lopuksi tutkitaan vielä, vaikuttaako spin-lasisysteemien ja ferromagneettisten systeemien välinen faasitransitio esimerkiksi metastabiilien tilojen lukumäärään.
  • Automated Rendering of Multi-stranded DNA Complexes with Pseudoknots
    (2024) Nowicka, Małgorzata; Gautam, Vinay K.; Orponen, Pekka
     A4 Artikkeli konferenssijulkaisussa
    We present a general method for rendering representations of multi-stranded DNA complexes from textual descriptions into 2D diagrams. The complexes can be arbitrarily pseudoknotted, and if a planar rendering is possible, the method will determine one in time which is essentially linear in the size of the textual description. (That is, except for a final stochastic fine-tuning step.) If a planar rendering is not possible, the method will compute a visually pleasing approximate rendering in quadratic time. Examples of diagrams produced by the method are presented in the paper.
  • Bayesian student modeling in a learning game
    (2010) Ruohonen, Rauli
     School of Science | Master's thesis
    The possibility of early identification of dyslexia has motivated the development of the computer game "Graphogame", which is designed for the early prevention of reading difficulties. It is important that the learning content in the game is adapted for individual players so that the game will be neither too difficult nor too easy. For this purpose, it is helpful to have a precisely defined statistical model of the player. In this thesis, we present a Bayesian model of the player. The model can be used for the selection of effective game content and for tracking the players' progress. The model is essentially a combination of factor analysis and the logistic model. In the game, the players are presented with choice situations, where the letters of the alphabet are displayed on the screen. The task is to select the letter that corresponds to the sound that is played at the same time. Information about the choice situations and the choices the players make is stored in game logs, which we use to fit the model. We are basically performing a factor analysis on the skills of the players, which are observable only through the choices the players make. There are three pre-existing statistical player models for Graphogame, but in all of them only one player is taken into account at a time, independently of all the other players. In contrast, in the model proposed in this thesis all the players are considered simultaneously, allowing the model to learn statistical properties of the player population. The pre-existing model best suited for the analysis of the game data is used to construct baseline models in this thesis. The employed model and fitting method are tested using simple simulations as well as real game log data. The model works well in the simulations, if there is enough data of each player. The model also predicts player choices in the real data better than the baseline models.
  • A Census of Steiner Triple Systems and Some Related Combinatorial Objects
    (2002) Kaski, Petteri
     Helsinki University of Technology | Licentiate thesis
  • Combinatorial algorithms for the design of nanoscale systems
    (2014) Mohammed, Abdulmelik
     Perustieteiden korkeakoulu | Master's thesis
    Over the past 30 years, DNA, with its exquisitely specific Watson-Crick base pairing rules, has found a novel use as a nanoscale construction material in DNA nanotechnology. DNA origami is a popular recent technique in DNA nanotechnology for the design and synthesis of DNA nanoscale shapes and patterns. DNA origami operates by the folding of a single long strand of DNA called a scaffold with the help of numerous shorter strands of DNA called staples. Recently, DNA origami design for polyhedral beam-frameworks has been proposed where a scaffold strand is conceptually routed over the beams of a polyhedron so that complementary strands potentially fold the scaffold to the framework in a solution. In this work, we modelled the problem of finding a scaffold routing path for polyhedral frameworks in graph-theoretic terms whereby the routing path was found to coincide with a specific type of Eulerian trail, called an A-trail, on the polyhedral skeleton. We studied the complexity of deciding whether an A-trail exists with an emphasis on rigid triangular frameworks or equivalently on plane triangulations. While the decision problem was found to be NP-complete in general, we learned that Eulerian triangulations always have A-trails if a long standing conjecture by Barnette on the Hamiltonicity of bipartite cubic polyhedral graphs holds. Given the general NP-completeness result, we developed a backtracking search algorithm for finding A-trails. To improve the backtrack search; we introduced an enumeration heuristic, tuned in particular to Eulerian triangulations, to schedule the nodes in the search tree. The algorithm, guided by the heuristic, efficiently found A-trails for a family of Eulerian triangulations as well as a family of braced grid graphs. Furthermore, we implemented a software package, BScOR (Beam Scaffolded-Origami Routing), which generates an A-trail, or equivalently a scaffold routing path, given a three-dimensional object description in a Polygon File Format.
  • Computation by DNA Strand Displacement Systems
    (2021-04-16) Nguyen, Khoa
     Perustieteiden korkeakoulu | Bachelor's thesis
  • A computational framework for DNA sequencing microscopy
    (2019-09-04) Hoffecker, Ian T.; Yang, Yunshi; Bernardinelli, Giulio; Orponen, Pekka; Högberg, Björn
     A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
    We describe a method whereby microscale spatial information such as the relative positions of biomolecules on a surface can be transferred to a sequence-based format and reconstructed into images without conventional optics. Barcoded DNA “polymerase colony” (polony) amplification techniques enable one to distinguish specific locations of a surface by their sequence. Image formation is based on pairwise fusion of uniquely tagged and spatially adjacent polonies. The network of polonies connected by shared borders forms a graph whose topology can be reconstructed from pairs of barcodes fused during a polony cross-linking phase, the sequences of which are determined by recovery from the surface and next-generation (next-gen) sequencing. We developed a mathematical and computational framework for this principle called polony adjacency reconstruction for spatial inference and topology and show that Euclidean spatial data may be stored and transmitted in the form of graph topology. Images are formed by transferring molecular information from a surface of interest, which we demonstrated in silico by reconstructing images formed from stochastic transfer of hypothetical molecular markers. The theory developed here could serve as a basis for an automated, multiplexable, and potentially superresolution imaging method based purely on molecular information.
  • Computer-aided production of scaffolded DNA nanostructures from flat sheet meshes
    (2016) Benson, Erik; Mohammed, Abdulmelik; Bosco, Alessandro; Teixeira, Ana I.; Orponen, Pekka; Högberg, Björn
     A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
    The use of DNA as a nanoscale construction material has been a rapidly developing field since the 1980s, in particular since the introduction of scaffolded DNA origami in 2006. Although software is available for DNA origami design, the user is generally limited to architectures where finding the scaffold path through the object is trivial. Herein, we demonstrate the automated conversion of arbitrary two-dimensional sheets in the form of digital meshes into scaffolded DNA nanostructures. We investigate the properties of DNA meshes based on three different internal frameworks in standard folding buffer and physiological salt buffers. We then employ the triangulated internal framework and produce four 2D structures with complex outlines and internal features. We demonstrate that this highly automated technique is capable of producing complex DNA nanostructures that fold with high yield to their programmed configurations, covering around 70 % more surface area than classic origami flat sheets.
  • Cooperative Heuristic Search with Software Agents
    (2014-06-02) Halme, Antti
     Perustieteiden korkeakoulu | Master's thesis
    Parallel algorithms extend the notion of sequential algorithms by permitting the simultaneous execution of independent computational steps. When the independence constraint is lifted and executions can freely interact and intertwine, parallel algorithms become concurrent and may behave in a nondeterministic way. Parallelism has over the years slowly risen to be a standard feature of high-performance computing, but concurrency, being even harder to reason about, is still considered somewhat notorious and undesirable. As such, the implicit randomness available in concurrency is rarely made use of in algorithms. This thesis explores concurrency as a means to facilitate algorithmic cooperation in a heuristic search setting. We use agents, cooperating software entities, to build a single-source shortest path (SSSP) search algorithm based on parallelized A∗, dubbed A!. We show how asynchronous information sharing gives rise to implicit randomness, which cooperating agents use in A! to maintain a collective secondary ranking heuristic and focus search space exploration. We experimentally show that A! consistently outperforms both vanilla A∗ and a noncooperative, explicitly randomized A∗ variant in the standard n-puzzle sliding tile problem context. The results indicate that A! performance increases with the addition of more agents, but that the returns are diminishing. A! is observed to be sensitive to heuristic improvement, but also constrained by search overhead from limited path diversity. A hybrid approach combining both implicit and explicit randomness is also evaluated and found to not be an improvement over A! alone. The studied A! implementation based on vanilla A∗ is not as such competitive against state-of-the-art parallel A∗ algorithms, but rather a first step in applying concurrency to speed up heuristic SSSP search. The empirical results imply that concurrency and nondeterministic cooperation can successfully be harnessed in algorithm design, inviting further inquiry into algorithms of this kind.
  • A design framework for carbon nanotube circuits affixed on DNA origami tiles
    (2011) Czeizler, Eugen; Lempiäinen, Tuomo; Orponen, Pekka
     A3 Kirjan tai muun kokoomateoksen osa
  • Design methods for 3D wireframe DNA nanostructures
    (2018-03) Orponen, Pekka
     A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
    The field of structural DNA nanotechnology aims at the systematic development of self-assembling nanostructures using DNA as the construction material. Research in this area is progressing rapidly, and the controlled, computer-aided design of increasingly complex structures is becoming feasible. One thread of this endeavour is the design and characterisation of self-assembling 3D nanostructures based on wireframe polyhedral models. This article aims to illustrate some of the key developments in this direction, in sufficient detail so that the reader can achieve a general understanding of the main concepts and approaches. The emphasis is on the design principles rather than experimental methodology, and the role of computer science and computational tools is set forth.
  • Designing 3D RNA Origami Nanostructures with a Minimum Number of Kissing Loops
    (2024-09) Elonen, Antti; Orponen, Pekka
     A4 Artikkeli konferenssijulkaisussa
    We present a general design technique for rendering any 3D wireframe model, that is any connected graph linearly embedded in 3D space, as an RNA origami nanostructure with a minimum number of kissing loops. The design algorithm, which applies some ideas and methods from topological graph theory, produces renderings that contain at most one kissing-loop pair for many interesting model families, including for instance all fully triangulated wireframes and the wireframes of all Platonic solids. The design method is already implemented and available for use in the design tool DNAforge (https://dnaforge.org).
  • Differential compression for efficient software updating
    (2007) Larvala, Samuli
     Helsinki University of Technology | Master's thesis
  • DNA microscopy
    (2021-05-04) Kivalo, Oula
     Perustieteiden korkeakoulu | Bachelor's thesis
  • DNA rendering of polyhedral meshes at the nanoscale
    (2015) Benson, Erik; Mohammed, Abdulmelik; Gardell, Johan; Masich, Sergej; Czeizler, Eugen; Orponen, Pekka; Högberg, Björn
     A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
    It was suggested1 more than thirty years ago that Watson–Crick base pairing might be used for the rational design of nanometre-scale structures from nucleic acids. Since then, and especially since the introduction of the origami technique2, DNA nanotechnology has enabled increasingly more complex structures3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18. But although general approaches for creating DNA origami polygonal meshes and design software are available14,16,17,19,20,21, there are still important constraints arising from DNA geometry and sense/antisense pairing, necessitating some manual adjustment during the design process. Here we present a general method of folding arbitrary polygonal digital meshes in DNA that readily produces structures that would be very difficult to realize using previous approaches. The design process is highly automated, using a routeing algorithm based on graph theory and a relaxation simulation that traces scaffold strands through the target structures. Moreover, unlike conventional origami designs built from close-packed helices, our structures have a more open conformation with one helix per edge and are therefore stable under the ionic conditions usually used in biological assays.
  • DNA-tiedontallennus
    (2020-04-17) Karppinen, Eetu
     Perustieteiden korkeakoulu | Bachelor's thesis