Search results for " Complexity"
showing 10 items of 623 documents
An efficient upper bound of the rotation distance of binary trees
2000
A polynomial time algorithm is developed for computing an upper bound for the rotation distance of binary trees and equivalently for the diagonal-flip distance of convex polygons triangulations. Ordinal tools are used.
Networks in biological systems: An investigation of the Gene Ontology as an evolving network
2009
Many biological systems can be described as networks where diFFerent elements interact, in order to perform biological processes. We introduce a network associated with the Gene Ontology. Specifically, we construct a correlation-based network where the vertices are the terms of the Gene Ontology and the link between each two terms is weighted on the basis of the number of genes that they have in common. We analyze a filtered network obtained from the correlation-based network and we characterize its evolution over different releases of the Gene Ontology.
Textual data compression in computational biology: Algorithmic techniques
2012
Abstract In a recent review [R. Giancarlo, D. Scaturro, F. Utro, Textual data compression in computational biology: a synopsis, Bioinformatics 25 (2009) 1575–1586] the first systematic organization and presentation of the impact of textual data compression for the analysis of biological data has been given. Its main focus was on a systematic presentation of the key areas of bioinformatics and computational biology where compression has been used together with a technical presentation of how well-known notions from information theory have been adapted to successfully work on biological data. Rather surprisingly, the use of data compression is pervasive in computational biology. Starting from…
The evolution of metazoan α-carbonic anhydrases and their roles in calcium carbonate biomineralization
2014
The carbonic anhydrase (CA; EC 4.2.1.1) superfamily is a class of ubiquitous metallo-enzymes that catalyse the reversible hydration of carbon dioxide. The ?-CA family, present in all metazoan clades, is a key enzyme involved in a wide range of physiological functions including pH regulation, respiration, photosynthesis, and biocalcification. This paper reviews the evolution of the ?-CA family, with an emphasis on metazoan ?-CA members involved in biocalcification. Phylogenetic analyses reveal a complex evolutionary history of ?-CAs, and suggest ?-CA was independently co-opted into a variety of skeleton forming roles (e.g. as a provider of HCO3? ions, a structural protein, a nucleation activ…
Experimental demonstration of phase bistability in a broad-area optical oscillator with injected signal
2015
We demonstrate experimentally that a broad-area laserlike optical oscillator (a nondegenerate photorefractive oscillator) with structured injected signal displays two-phase patterns. The technique [de Valc\'arcel and Staliunas, Phys. Rev. Lett. 105, 054101 (2010)] consists in spatially modulating the injection, so that its phase alternates periodically between two opposite values, i.e., differing by $\ensuremath{\pi}$.
Precīzie kvantu algoritmi, izmantojot 1-kvantu-vaicājuma izsaukumus
2018
Darbā ir analizēti zināmi unikāli precīzie kvantu algoritmi, kuru īpašības ir atšķirīgas no citiem literatūrā atrodamiem algoritmiem, un uzsākts pētīt iespējas vispārināt šajos algoritmos esošos paņēmienus. Darbā ir noformulēts jauns skaitļošanas modelis, kas ir saistīts ar precīzo kvantu vaicājumu modeli. Veikti skaitliski aprēķini, lai palīdzētu saprast jaunā modeļa iespējas un ierobežojumus. Izteiktas hipotēzes un virzieni, kādos turpināt analīzi un pētījumu.
A Fast GPU-Based Motion Estimation Algorithm for H.264/AVC
2012
H.264/AVC is the most recent predictive video compression standard to outperform other existing video coding standards by means of higher computational complexity. In recent years, heterogeneous computing has emerged as a cost-efficient solution for high-performance computing. In the literature, several algorithms have been proposed to accelerate video compression, but so far there have not been many solutions that deal with video codecs using heterogeneous systems. This paper proposes an algorithm to perform H.264/AVC inter prediction. The proposed algorithm performs the motion estimation, both with full-pixel and sub-pixel accuracy, using CUDA to assist the CPU, obtaining remarkable time …
Anomaly detection in dynamic systems using weak estimators
2011
Accepted version of an article from the journal: ACM transactions on internet technology. Published version available from the ACM: http://dx.doi.org/10.1145/1993083.1993086 Anomaly detection involves identifying observations that deviate from the normal behavior of a system. One of the ways to achieve this is by identifying the phenomena that characterize “normal” observations. Subsequently, based on the characteristics of data learned from the “normal” observations, new observations are classified as being either “normal” or not. Most state-of-the-art approaches, especially those which belong to the family of parameterized statistical schemes, work under the assumption that the underlying…
Symbolic control for underactuated differentially flat systems
2006
In this paper we address the problem of generating input plans to steer complex dynamical systems in an obstacle-free environment. Plans considered admit a finite description length and are constructed by words on an alphabet of input symbols, which could be e.g. transmitted through a limited capacity channel to a remote system, where they can be decoded in suitable control actions. We show that, by suitable choice of the control encoding, finite plans can be efficiently built for a wide class of dynamical systems, computing arbitrarily close approximations of a desired equilibrium in polynomial time. Moreover, we illustrate by simulations the power of the proposed method, solving the steer…
Do too many choices have negative consequences? An empirical review
2013
Various experiments demonstrated that having too much choice has negative consequences on the motivation to choose and on the satisfaction with the chosen option. However, the literature reports conflicting results showing that choosing from large assortments has advantages. This paper reviews the main empirical results in favor and against the negative effect of too much choice and identifies possible directions for further research. Copyright © 2013 by Società editrice il Mulino.