On some algorithms for reverse engineering certain finite dynamical systems

Abstract

There are two general problems related to finite dynamical systems (FDS): the analysis and the synthesis (also known as the reverse engineering) problems. In the former, we are interested in uncovering the sequential structure of a given FDS. In the latter, given a prescribed structure, we have to find an appropriate FDS that accomplishes the intended behavior. In this work we reverse engineer FDSs related to two recent applications. On is the problem of finding an optimal linear (i.e., a matrix) FDS over the integers mod a prime p to efficiently compute FFTs with linear symmetries. For this, we propose O(p2logp) and o(p3logp) time algorithms for the two and three dimensional cases as opposed to O(p6) and O(p12) time of exhaustive searches, respectively. Also, we characterize those important cases for which he symmetric FFT with prime edge-length can be computed through a single cyclic convolution. For the second problem, the reverse engineering problem in bioinformatics, we study and compare two finite field models for genetic networks and provide algorithms for converting one model into the other via a DFT. Also, we develop efficient methods for performing arithmetic over finite fields. We propose a new efficient parallel algorithm based in the Chines remaindering theorem to interpolate over finite fields.

<p>Con respecto a sistemas dinámicos finitos (SDF), se consideran dos problemas generales: el problema del análisis y el problema de síntesis (también conocido como "reverse engineering"). En el primero, dado un SDF, el interés es descubrir la estructura secuencial del mismo. Para el segundo problema, dada una estructura secuencial, se requiere hallar un SDF que cumpla con todos los requisitos previamente impuestos. Esta investigación trata el problema del "reverse engineering" relacionado a dos aplicaciones recientes. La primera aplicación consiste en encontrar un SDF lineal sobre los enteros módulo un primo p que optimice el cómputo de una transformada rápida de Fourier (FFT, por sus siglas en inglés) con simetrías lineales. Para resolver este problema en dos y tres dimensiones, las búsquedas exaustivas usadas anteriormente tenían complejidades del tipo O(p⁶) y O(p¹²). Este trabajo desarrolla algoritmos cuyas complejidades son del tipo O(p²logp) y O(p³logp), respectivamente. Además, este trabajo caracteriza aquellos casos donde la FFT simétrica de longitud prima puede ser computada a través de una sola convolución cíclica. Para el segundo problema, conocido como el problema del "reverse engineering" en bioinformática, este trabajo estudia y compara dos modelos de redes genéticas sobre cuerpos finitos y da algoritmos que convierten un modelo al otro usando una transformada discreta de Fourier. Además, este trabajo desarrolla métodos eficientes para llevar a cabo aritmética sobre cuerpos finitos y propone un algoritmo paralelo nuevo y eficiente para interpolar sobre cuerpos finitos el cual está basado en el teorema del residuo chino.</p>