Edge matching puzzles as hard SAT/CSP benchmarks

Recently, edge matching puzzles, an NP-complete problem, have rececived, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.

The Classification of Vitreous Seeds in Retinoblastoma and Response to Intravitreal Melphalan.

PURPOSE: To evaluate the clinical characteristics of the 3 classifications of vitreous seeds in retinoblastoma-dust (class 1), spheres (class 2), and clouds (class 3)-and their responses to intravitreal melphalan. DESIGN: Retrospective, bi-institutional cohort study. PARTICIPANTS: A total of 87 patient eyes received 475 intravitreal injections of melphalan (median dose, 30 μg) given weekly, a median of 5 times (range, 1-12 times). METHODS: At presentation, the vitreous seeds were classified into 3 groups: dust, spheres, and clouds. Indirect ophthalmoscopy, fundus photography, ultrasonography, and ultrasonic biomicroscopy were used to evaluate clinical response to weekly intravitreal melphalan injections and time to regression of vitreous seeds. Kaplan-Meier estimates of time to regression and ocular survival, patient survival, and event-free survival (EFS) were calculated and then compared using the Mantel-Cox test of curve. MAIN OUTCOME MEASURES: Time to regression of vitreous seeds, patient survival, ocular survival, and EFS. RESULTS: The difference in time to regression was significantly different for the 3 seed classes (P < 0.0001): the median time to regression was 0.6, 1.7, and 7.7 months for dust, spheres, and clouds, respectively. Eyes with dust received significantly fewer injections and a lower median and cumulative dose of melphalan, whereas eyes with clouds received significantly more injections and a higher median and cumulative dose of melphalan. Overall, the 2-year Kaplan-Meier estimates for ocular survival, patient survival, and EFS (related to target seeds) were 90.4% (95% confidence interval [CI], 79.7-95.6), 100%, and 98.5% (95% CI, 90-99.7), respectively. CONCLUSIONS: The regression and response of vitreous seeds to intravitreal melphalan are different for each seed classification. The vitreous seed classification can be predictive of time to regression, number, median dose, and cumulative dose of intravitreal melphalan injections required.

Genotypic classification of patients with Wolfram syndrome: insights into the natural history of the disease and correlation with phenotype

Purpose: Wolfram syndrome is a degenerative, recessive rare disease with an onset in childhood. It is caused by mutations in WFS1 or CISD2 genes. More than 200 different variations in WFS1 have been described in patients with Wolfram syndrome, which complicates the establishment of clear genotype-phenotype correlation. The purpose of this study was to elucidate the role of WFS1 mutations and update the natural history of the disease. Methods: This study analyzed clinical and genetic data of 412 patients with Wolfram syndrome published in the last 15 years. Results: (i) 15% of published patients do not fulfill the current ­inclusion criterion; (ii) genotypic prevalence differences may exist among countries; (iii) diabetes mellitus and optic atrophy might not be the first two clinical features in some patients; (iv) mutations are nonuniformly distributed in WFS1; (v) age at onset of diabetes mellitus, hearing defects, and diabetes insipidus may depend on the patient"s genotypic class; and (vi) disease progression rate might depend on genotypic class. Conclusion: New genotype-phenotype correlations were established, disease progression rate for the general population and for the genotypic classes has been calculated, and new diagnostic criteria have been proposed. The conclusions raised could be important for patient management and counseling as well as for the development of treatments for Wolfram syndrome.

The Control of the Edge Shrinkage in Board

Tämän diplomityön tavoitteena oli löytää prosessiparametrejä nestepakkauskartongin reuna-alueiden kuivatuskutistuman hallintaan ja saada tuotteen reuna-alueiden sileystaso paremmaksi. Tarkoituksena oli parantaa reuna-alueiden painettavuusominaisuuksia sekä saada koneen poikkisuunnassa laadultaan parempi tuote. Työn kirjallisuusosassa on tarkasteltu työn kannalta nestepakkauskartongin kriittisimpiä ominaisuuksia, sileyttä ja jäykkyyttä. Lisäksi kirjallisuusosassa on tarkasteltu kuitujen ominaisuuksia, sylinterikuivatusta ja kuivatuskutistumaa. Kokeellisessa osassa on etsitty esitutkimuksella prosessiparametrejä, jotka ovat aiheuttaneet poikkisuunnan sileyserojen kasvun kartonkikoneen investoinnin jälkeen. Suoria korrelaatioita prosessiparametrien ja kuivatuskutistuman välille ei löydetty. Kokeellisen osan tehdasmittakaavaisissa koeajoissa tutkittiin kahdeksan eri parametrin vaikutusta kuivatuskutistumaan, jotka perustuivat kirjallisuuteen. Tutkituista parametreistä huulisuihkun iskukulman muutoksella sekä konesuuntaisella kuivatusprofiililla ei ollut vaikutusta kuivatuskutistumaan. Runkokerroksen mäntysellun korvaaminen koivusellulla vähensi kuivatuskutistumaa ja lisäsi sileyttä, mutta tuotteen palstautumislujuus ei tällöin ollut riittävä. Retentiokemikaalien reseptimuutoksilla pinta- ja taustakerroksen välillä, kuivatusosan nollatason laskulla ja perälaatikkosakeuksien pienentämisellä oli vähän vaikutusta kuivatuskutistumaan. Vaikutus reuna-alueiden sileyteen oli kuitenkin vähemmän kuin 10 %. Diplomityön perusteella kuivatusosan nopeuseroilla ja kuivatusviirojen kireyksillä oli suurin vaikutusta kuivatuskutistumaan ja reuna-alueiden sileystasoon. Lisäämällä nopeuseroja ja kiristämällä kuivatusviiroja reuna-alueiden sileyttä pystyttiin parantamaan yli 20 %.

Classification-Based compression of Multispectral Images

The purpose of this thesis is to present a new approach to the lossy compression of multispectral images. Proposed algorithm is based on combination of quantization and clustering. Clustering was investigated for compression of the spatial dimension and the vector quantization was applied for spectral dimension compression. Presenting algo¬rithms proposes to compress multispectral images in two stages. During the first stage we define the classes' etalons, another words to each uniform areas are located inside the image the number of class is given. And if there are the pixels are not yet assigned to some of the clusters then it doing during the second; pass and assign to the closest eta¬lons. Finally a compressed image is represented with a flat index image pointing to a codebook with etalons. The decompression stage is instant too. The proposed method described in this paper has been tested on different satellite multispectral images from different resources. The numerical results and illustrative examples of the method are represented too.

Wood Volume Measurement Using Color Images

Tämä työ käsittelee puutukkien tilavuuden mittaamista värikonenäön avulla. Värikuvat on saatu Simpeleellä olevan metsäteollisuusyrityksen hiomosta. Työssä esitetään perusteellisesti matemaattinen teoria, joka liittyy käytettyihin kuvankäsittelymenetelmiin, kuten luokitteluun, kohinan poistoon ja tukkien segmentointiin. Esitetyt menetelmät implementointiin käytännössä ja eri menetelmillä saatuja tuloksia vertailtiin keskenään. Kuvankäsittelyalgoritmit on implementoitu Matlab 6.0:n avulla. Pääasiassa käytettiin uusinta Image Processing Toolboxia, joka on versio 3.0. Tämä työn näkökulma on pääasiassa käytäntöön soveltava, koska metsäteollsuus on korkealla tasolla Suomessa ja siellä on paljon alan yrityksiä, joissa tässä työssä kehitettyä menetelmää voidaan hyödyntää.

A survey of transposable element classification systems--a call for a fundamental update to meet the challenge of their diversity and complexity.

The increase of publicly available sequencing data has allowed for rapid progress in our understanding of genome composition. As new information becomes available we should constantly be updating and reanalyzing existing and newly acquired data. In this report we focus on transposable elements (TEs) which make up a significant portion of nearly all sequenced genomes. Our ability to accurately identify and classify these sequences is critical to understanding their impact on host genomes. At the same time, as we demonstrate in this report, problems with existing classification schemes have led to significant misunderstandings of the evolution of both TE sequences and their host genomes. In a pioneering publication Finnegan (1989) proposed classifying all TE sequences into two classes based on transposition mechanisms and structural features: the retrotransposons (class I) and the DNA transposons (class II). We have retraced how ideas regarding TE classification and annotation in both prokaryotic and eukaryotic scientific communities have changed over time. This has led us to observe that: (1) a number of TEs have convergent structural features and/or transposition mechanisms that have led to misleading conclusions regarding their classification, (2) the evolution of TEs is similar to that of viruses by having several unrelated origins, (3) there might be at least 8 classes and 12 orders of TEs including 10 novel orders. In an effort to address these classification issues we propose: (1) the outline of a universal TE classification, (2) a set of methods and classification rules that could be used by all scientific communities involved in the study of TEs, and (3) a 5-year schedule for the establishment of an International Committee for Taxonomy of Transposable Elements (ICTTE).

Text Classification and Indexing in IP Networks

Internet on elektronisen postin perusrakenne ja ollut tärkeä tiedonlähde akateemisille käyttäjille jo pitkään. Siitä on tullut merkittävä tietolähde kaupallisille yrityksille niiden pyrkiessä pitämään yhteyttä asiakkaisiinsa ja seuraamaan kilpailijoitansa. WWW:n kasvu sekä määrällisesti että sen moninaisuus on luonut kasvavan kysynnän kehittyneille tiedonhallintapalveluille. Tällaisia palveluja ovet ryhmittely ja luokittelu, tiedon löytäminen ja suodattaminen sekä lähteiden käytön personointi ja seuranta. Vaikka WWW:stä saatavan tieteellisen ja kaupallisesti arvokkaan tiedon määrä on huomattavasti kasvanut viime vuosina sen etsiminen ja löytyminen on edelleen tavanomaisen Internet hakukoneen varassa. Tietojen hakuun kohdistuvien kasvavien ja muuttuvien tarpeiden tyydyttämisestä on tullut monimutkainen tehtävä Internet hakukoneille. Luokittelu ja indeksointi ovat merkittävä osa luotettavan ja täsmällisen tiedon etsimisessä ja löytämisessä. Tämä diplomityö esittelee luokittelussa ja indeksoinnissa käytettävät yleisimmät menetelmät ja niitä käyttäviä sovelluksia ja projekteja, joissa tiedon hakuun liittyvät ongelmat on pyritty ratkaisemaan.

ICA as a preprocessing technique for classification

In this paper we propose the use of the independent component analysis (ICA) [1] technique for improving the classification rate of decision trees and multilayer perceptrons [2], [3]. The use of an ICA for the preprocessing stage, makes the structure of both classifiers simpler, and therefore improves the generalization properties. The hypothesis behind the proposed preprocessing is that an ICA analysis will transform the feature space into a space where the components are independent, and aligned to the axes and therefore will be more adapted to the way that a decision tree is constructed. Also the inference of the weights of a multilayer perceptron will be much easier because the gradient search in the weight space will follow independent trajectories. The result is that classifiers are less complex and on some databases the error rate is lower. This idea is also applicable to regression