Browsing by Issue Date

Sort by: Order: Results:

Now showing items 1-20 of 382
  • Ojala, Heikki; Korsbäck, Anders; Wallin, Anders E.; Hæggström, Edward (Applied Physics Letters, 2009)
    We increase the effective stiffness of optical tweezers by position clamping a polystyrene bead with a predictive feedback control algorithm. This algorithm mitigates the effect of feedback loop delay. Hence, higher gain than with proportional control can be employed, which results in higher effective trap stiffness, without trap instability. In experiments (initial trap stiffness 0.056 pN/nm with a 1.78 μm diameter polystyrene bead) predictive control increased the effective trap stiffness by 55% relative to proportional control. We also derive theoretical expressions for the power spectra of the bead position controlled by our algorithm.
  • Sirén, Jouni (2009)
    We present a fast space-efficient algorithm for constructing compressed suffix arrays (CSA). The algorithm requires O(n log n) time in the worst case, and only O(n) bits of extra space in addition to the CSA. As the basic step, we describe an algorithm for merging two CSAs. We show that the construction algorithm can be parallelized in a symmetric multiprocessor system, and discuss the possibility of a distributed implementation. We also describe a parallel implementation of the algorithm, capable of indexing several gigabytes per hour.
  • Polishchuk, Valentin; Suomela, Jukka (Elsevier, 2009)
    We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.
  • Kauppi, P.E. (Helsingin yliopisto, 2009)
  • Kauppi, P.E. (Economist Newspaper Ltd., 2009)
    SIR – In looking for cost-efficient CCS, please step up and walk to your window, where you may see a tree. The evolution of woody plants has solved the problem of capture (photosynthesis) and storage (formation of durable cells) at minimal cost. After what is called “forest transition”, woody resources of a country cease to shrink and start to expand. Forest transition implies a shift of the landscape from a carbon source to a carbon sink, thus marking the onset of organic, cheap CCS. Alexander Mather of the University of Aberdeen predicted in 1992 that forest transition is the likely future of tropical countries, too. Since then, however, biofuel clearings and other pressures have created new concerns. Organic CCS will again become an issue as climate negotiators reconvene to consider a post-Kyoto treaty in Copenhagen in December this year. Pekka Kauppi Professor of environmental science and policy University of Helsinki Helsinki
  • Lodenius, Martin; Josefsson, Jussi; Heliövaara, Kari; Tulisalo, Esa; Nummelin, Matti (Wiley-Blackwell, 2009)
    Ash fertilization of forests returns nutrients to forest ecosystems and has a positive effect on soil pH, but it also may elevate Cd concentrations of forest biota. Cadmium concentrations of some forest insects (Formica ants, carabids and Coleopteran larvae from decaying wood) were investigated in southern Finland, where two plots were fertilized with wood ash, while two other plots represented unfertilized control plots. In ants, mean Cd concentration was 3.6 ± 1.4 mg/kg, with nest workers having significantly higher concentrations than workers trapped in pitfall traps. Concentrations at fertilized and unfertilized plots were similar. In carabid beetles, the average Cd concentration of Carabus glabratus was 0.44 ± 0.36 mg/kg, with no significant difference between control plots and fertilized plots. In another carabid beetle, Pterostichus niger, mean Cd concentration was higher at fertilized plots compared to control plots. We conclude that the variation of Cd concentrations in the insects studied is more efficiently controlled by species-specific differences than fertilization history of the forest floor.
  • Fischer, Johannes; Mäkinen, Veli; Välimäki, Niko (IEEE, 2008)
    Let D1 and D2 be two databases (i.e. multisets) of d strings, over an alphabet S, with overall length n. We study the problem of mining discriminative patterns between D1 and D2, e.g., patterns that are frequent in one database but not in the other, emerging patterns, or patterns satisfying other frequency-related constraints. Using the algorithmic framework by Hui (CPM 1992), one can solve several variants of this problem in the optimal linear time with the aid of suffix trees or suffix arrays. This stands in high contrast to other pattern domains such as itemsets or subgraphs, where super-linear lower bounds are known. However, the space requirement of existing solutions is O(n log n) bits, which is not optimal for |S| << n (in particular for constant |S|), as the databases themselves occupy only n log |S| bits. Because in many real-life applications space is a more critical resource than time, the aim of this article is to reduce the space, at the cost of an increased running time. In particular, we give a solution for the above problems that uses O(n log n+d log n) bits, while the time requirement is increased from the optimal linear time to O(n log n). Our new method is tested extensively on a biologically relevant datasets and shown to be usable even on a genome-scale data.
  • Kauppi, P.E.; Lehtonen, A.; Liski, J. (Sanoma, 2008)
  • Kauppi, P.E.; Kettunen, J. (Talentum Media, 2008)
  • Fischer, Johannes; Mäkinen, Veli; Navarro, Gonzalo (Springer-Verlag, 2008)
    Suffix trees are one of the most important data structures in stringology, with myriads of applications in fluorishing areas like bioinformatics. As their main problem is space usage, recent efforts have focused on compressed suffix tree representations, which obtain large space reductions in exchange for moderate slowdowns. Such a smaller suffix tree could fit in a faster memory, outweighting by far the theoretical slowdown. We present a novel compressed suffix tree. Compared to the current compressed suffix trees, it is the first achieving at the same time sublogarithmic complexity for the operations, and space usage which goes to zero as the entropy of the text does. Our development contains several novel ideas, such as compressing the longest common prefix information, and totally getting rid of the suffix tree topology, expressing all the suffix tree operations using range minimum queries and a new primitive called next/previous smaller value in a sequence.
  • Kauppi, P.E. (Helsingin yliopisto, 2008)
  • Kauppi, P.E. (Talentum Media, 2008)
  • Mäkinen, Veli; Navarro, Gonzalo (IEEE Computer Society, 2008)
    Recent advances in compressed data structures have led to the new concept of self-indexing; it is possible to represent a sequence of symbols compressed in a form that enables fast queries on the content of the sequence. This paper studies different analogies of self-indexing on images. First, we show that a key ingredient of many self-indexes for sequences, namely the wavelet tree, can be used to obtain both lossless and lossy compression with random access to pixel values. Second, we show how to use self-indexes for sequences as a black-box to provide self-indexes for images with filtering-type query capabilities. Third, we develop a tailor-made self-index for images by showing how to compress two-dimensional suffix arrays. Experimental results are provided to compare the compressibility to standard compression methods.
  • Voigt, H.-R. (Centralförbundet för Fiskerihushållning, 2008)
  • Voigt, H.-R. (Societas pro Flora et Fauna Fennica, 2008)
  • Kettunen, J.; Kauppi, P.E.; Smolander, H. (Talentum, 2008)
    Metsätalous ja -teollisuus tarjoavat tehokkaita keinoja Suomen kasvuhuonepäästöjen vähentämiseksi. Brysselin päättäjät on vain saatava ymmärtämään metsien merkitys.
  • Böcker, Sebastian; Mäkinen, Veli (IEEE/ACM, 2008)
    Mass spectrometry has become one of the most popular analysis techniques in Proteomics and Systems Biology. With the creation of larger datasets, the automated recalibration of mass spectra becomes important to ensure that very peak in the sample spectrum is correctly assigned to some peptide and protein. Algorithms for recalibrating mass spectra have to be robust with respect to wrongly assigned peaks, as well as efficient due to the amount of mass spectrometry data. The recalibration of mass spectra leads us to the problem of finding an optimal matching between mass spectra under measurement errors. We have developed two deterministic methods that allow robust computation of such a matching: The first approach uses a computational geometry interpretation of the problem, and tries to find two parallel lines with constant distance that stab a maximal number of points in the plane. The second approach is based on finding a maximal common approximate subsequence, and improves existing algorithms by one order of magnitude exploiting the sequential nature of the matching problem. We compare our results to a computational geometry algorithm using a topological line-sweep.
  • Kaski, Petteri; Penttinen, Aleksi; Suomela, Jukka (Old City Publishing, 2008)
    We study the algorithmic problem of coordinating transmissions in a wireless network where radio interference constrains concurrent transmissions on wireless links. We focus on pairwise conflicts between the links; these can be described as a conflict graph. Associated with the conflict graph are two fundamental network coordination tasks: (a) finding a nonconflicting set of links with the maximum total weight, and (b) finding a link schedule with the minimum total length. Our work shows that two assumptions on the geometric structure of conflict graphs suffice to achieve polynomial-time constant-factor approximations: (i) bounded density of devices, and (ii) bounded range of interference. We also show that these assumptions are not sufficient to obtain a polynomial-time approximation scheme (PTAS) for either coordination task. There exists a PTAS if we make an additional assumption: (iii) bounded range of radio transmissions.