Kahden merkkijonon pisimmän yhteisen alijonon ongelma ja sen ratkaiseminen

Tämä tutkielma kuuluu merkkijonoalgoritmiikan piiriin. Merkkijono S on merkkijonojen X[1..m] ja Y[1..n] yhteinen alijono, mikäli se voidaan muodostaa poistamalla X:stä 0..m ja Y:stä 0..n kappaletta merkkejä mielivaltaisista paikoista. Jos yksikään X:n ja Y:n yhteinen alijono ei ole S:ää pidempi, sanotaan, että S on X:n ja Y:n pisin yhteinen alijono (lyh. PYA). Tässä työssä keskitytään kahden merkkijonon PYAn ratkaisemiseen, mutta ongelma on yleistettävissä myös useammalle jonolle. PYA-ongelmalle on sovelluskohteita – paitsi tietojenkäsittelytieteen niin myös bioinformatiikan osa-alueilla. Tunnetuimpia niistä ovat tekstin ja kuvien tiivistäminen, tiedostojen versionhallinta, hahmontunnistus sekä DNA- ja proteiiniketjujen rakennetta vertaileva tutkimus. Ongelman ratkaisemisen tekee hankalaksi ratkaisualgoritmien riippuvuus syötejonojen useista eri parametreista. Näitä ovat syötejonojen pituuden lisäksi mm. syöttöaakkoston koko, syötteiden merkkijakauma, PYAn suhteellinen osuus lyhyemmän syötejonon pituudesta ja täsmäävien merkkiparien lukumäärä. Täten on vaikeaa kehittää algoritmia, joka toimisi tehokkaasti kaikille ongelman esiintymille. Tutkielman on määrä toimia yhtäältä käsikirjana, jossa esitellään ongelman peruskäsitteiden kuvauksen jälkeen jo aikaisemmin kehitettyjä tarkkoja PYAalgoritmeja. Niiden tarkastelu on ryhmitelty algoritmin toimintamallin mukaan joko rivi, korkeuskäyrä tai diagonaali kerrallaan sekä monisuuntaisesti prosessoiviin. Tarkkojen menetelmien lisäksi esitellään PYAn pituuden ylä- tai alarajan laskevia heuristisia menetelmiä, joiden laskemia tuloksia voidaan hyödyntää joko sellaisinaan tai ohjaamaan tarkan algoritmin suoritusta. Tämä osuus perustuu tutkimusryhmämme julkaisemiin artikkeleihin. Niissä käsitellään ensimmäistä kertaa heuristiikoilla tehostettuja tarkkoja menetelmiä. Toisaalta työ sisältää laajahkon empiirisen tutkimusosuuden, jonka tavoitteena on ollut tehostaa olemassa olevien tarkkojen algoritmien ajoaikaa ja muistinkäyttöä. Kyseiseen tavoitteeseen on pyritty ohjelmointiteknisesti esittelemällä algoritmien toimintamallia hyvin tukevia tietorakenteita ja rajoittamalla algoritmien suorittamaa tuloksetonta laskentaa parantamalla niiden kykyä havainnoida suorituksen aikana saavutettuja välituloksia ja hyödyntää niitä. Tutkielman johtopäätöksinä voidaan yleisesti todeta tarkkojen PYA-algoritmien heuristisen esiprosessoinnin lähes systemaattisesti pienentävän niiden suoritusaikaa ja erityisesti muistintarvetta. Lisäksi algoritmin käyttämällä tietorakenteella on ratkaiseva vaikutus laskennan tehokkuuteen: mitä paikallisempia haku- ja päivitysoperaatiot ovat, sitä tehokkaampaa algoritmin suorittama laskenta on.

Is professional recognition in plastic surgery related to activity in research

OBJECTIVE: To evaluate the relation of medical research, with the participation of prominent plastic surgeon in Congress.METHODS: We reviewed the scientific programs of the last 3 Brazilian Congress of Surgery, were selected 21 Brazilian plástic surgeons invited to serve as panelists or speakers in roundtable sessions in the last 3 congresses (Group 1). We randomly selected and paired by other members (associates) of the Brazilian Society of Plastic Surgery, with no participation in congress as speaker (Group 2). We conducted a search for articles published in journals indexed in Medline, Lilacs and SciELO for all doctors selected during the entire academic career and the last 5 years from March 2007 until March 2012. We assessed the research activity through the simple counting of the number of publications in indexed journals for each professional. The number of publications groups was compared.RESULTS: articles produced throughout career: Group 1- 639 articles (average of 30.42 items each). Group 2- 79 articles (mean 3.95 articles each). Difference between medias: p <0.001.CONCLUSION: The results demonstrate that the Brazilian Society of Plastic Surgery seeking professionals with a greater number of publications and journals of higher impact. This approach encourages new members to pursue a higher qualification, and give security to congressmen, they can rely on the existence of a technical criterion in the choice of speakers.

Local Features in Image and Video Processing - Object Class Matching and Video Shot Detection

The usage of digital content, such as video clips and images, has increased dramatically during the last decade. Local image features have been applied increasingly in various image and video retrieval applications. This thesis evaluates local features and applies them to image and video processing tasks. The results of the study show that 1) the performance of different local feature detector and descriptor methods vary significantly in object class matching, 2) local features can be applied in image alignment with superior results against the state-of-the-art, 3) the local feature based shot boundary detection method produces promising results, and 4) the local feature based hierarchical video summarization method shows promising new new research direction. In conclusion, this thesis presents the local features as a powerful tool in many applications and the imminent future work should concentrate on improving the quality of the local features.

LVDC power distribution system: computational modelling

In the doctoral dissertation, low-voltage direct current (LVDC) distribution system stability, supply security and power quality are evaluated by computational modelling and measurements on an LVDC research platform. Computational models for the LVDC network analysis are developed. Time-domain simulation models are implemented in the time-domain simulation environment PSCAD/EMTDC. The PSCAD/EMTDC models of the LVDC network are applied to the transient behaviour and power quality studies. The LVDC network power loss model is developed in a MATLAB environment and is capable of fast estimation of the network and component power losses. The model integrates analytical equations that describe the power loss mechanism of the network components with power flow calculations. For an LVDC network research platform, a monitoring and control software solution is developed. The solution is used to deliver measurement data for verification of the developed models and analysis of the modelling results. In the work, the power loss mechanism of the LVDC network components and its main dependencies are described. Energy loss distribution of the LVDC network components is presented. Power quality measurements and current spectra are provided and harmonic pollution on the DC network is analysed. The transient behaviour of the network is verified through time-domain simulations. DC capacitor guidelines for an LVDC power distribution network are introduced. The power loss analysis results show that one of the main optimisation targets for an LVDC power distribution network should be reduction of the no-load losses and efficiency improvement of converters at partial loads. Low-frequency spectra of the network voltages and currents are shown, and harmonic propagation is analysed. Power quality in the LVDC network point of common coupling (PCC) is discussed. Power quality standard requirements are shown to be met by the LVDC network. The network behaviour during transients is analysed by time-domain simulations. The network is shown to be transient stable during large-scale disturbances. Measurement results on the LVDC research platform proving this are presented in the work.

The renal and hepatic distribution of Bence Jones proteins depends on glycosylation: a scintigraphic study in rats

The aim of the present study was to evaluate renal and liver distribution of two monoclonal immunoglobulin light chains. The chains were purified individually from the urine of patients with multiple myeloma and characterized as lambda light chains with a molecular mass of 28 kDa. They were named BJg (high amount of galactose residues exposed) and BJs (sialic acid residues exposed) on the basis of carbohydrate content. A scintigraphic study was performed on male Wistar rats weighing 250 g for 60 min after iv administration of 1 mg of each protein (7.4 MBq), as the intact proteins and also after carbohydrate oxidation. Images were obtained with a Siemens gamma camera with a high-resolution collimator and processed with a MicroDelta system. Hepatic and renal distribution were established and are reported as percent of injected dose. Liver uptake of BJg was significantly higher than liver uptake of BJs (94.3 vs 81.4%) (P<0.05). This contributed to its greater removal from the intravascular compartment, and consequently lower kidney accumulation of BJg in comparison to BJs (5.7 vs 18.6%) (P<0.05). After carbohydrate oxidation, there was a decrease in hepatic accumulation of both proteins and consequently a higher renal overload. The tissue distribution of periodate-treated BJg was similar to that of native BJs: 82.7 vs 81.4% in the liver and 17.3 vs 18.6% in the kidneys. These observations indicate the important role of sugar residues of Bence Jones proteins for their recognition by specific membrane receptors, which leads to differential tissue accumulation and possible toxicity

NADPH-diaphorase activity in area 17 of the squirrel monkey visual cortex: neuropil pattern, cell morphology and laminar distribution

We studied the distribution of NADPH-diaphorase activity in the visual cortex of normal adult New World monkeys (Saimiri sciureus) using the malic enzyme "indirect" method. NADPH-diaphorase neuropil activity had a heterogeneous distribution. In coronal sections, it had a clear laminar pattern that was coincident with Nissl-stained layers. In tangential sections, we observed blobs in supragranular layers of V1 and stripes throughout the entire V2. We quantified and compared the tangential distribution of NADPH-diaphorase and cytochrome oxidase blobs in adjacent sections of the supragranular layers of V1. Although their spatial distributions were rather similar, the two enzymes did not always overlap. The histochemical reaction also revealed two different types of stained cells: a slightly stained subpopulation and a subgroup of deeply stained neurons resembling a Golgi impregnation. These neurons were sparsely spined non-pyramidal cells. Their dendritic arbors were very well stained but their axons were not always evident. In the gray matter, heavily stained neurons showed different dendritic arbor morphologies. However, most of the strongly reactive cells lay in the subjacent white matter, where they presented a more homogenous morphology. Our results demonstrate that the pattern of NADPH-diaphorase activity is similar to that previously described in Old World monkeys

MHC-restricted antigen presentation and recognition: constraints on gene, recombinant and peptide vaccines in humans

The target of any immunization is to activate and expand lymphocyte clones with the desired recognition specificity and the necessary effector functions. In gene, recombinant and peptide vaccines, the immunogen is a single protein or a small assembly of epitopes from antigenic proteins. Since most immune responses against protein and peptide antigens are T-cell dependent, the molecular target of such vaccines is to generate at least 50-100 complexes between MHC molecule and the antigenic peptide per antigen-presenting cell, sensitizing a T cell population of appropriate clonal size and effector characteristics. Thus, the immunobiology of antigen recognition by T cells must be taken into account when designing new generation peptide- or gene-based vaccines. Since T cell recognition is MHC-restricted, and given the wide polymorphism of the different MHC molecules, distinct epitopes may be recognized by different individuals in the population. Therefore, the issue of whether immunization will be effective in inducing a protective immune response, covering the entire target population, becomes an important question. Many pathogens have evolved molecular mechanisms to escape recognition by the immune system by variation of antigenic protein sequences. In this short review, we will discuss the several concepts related to selection of amino acid sequences to be included in DNA and peptide vaccines.

Evidence for the expression of native Mycobacterium tuberculosis phospholipase C: recognition by immune sera and detection of promoter activity

The genome of Mycobacterium tuberculosis H37Rv contains three contiguous genes (plc-a, plc-b and plc-c) which are similar to the Pseudomonas aeruginosa phospholipase C (PLC) genes. Expression of mycobacterial PLC-a and PLC-b in E. coli and M. smegmatis has been reported, whereas expression of the native proteins in M. tuberculosis H37Rv has not been demonstrated. The objective of the present study was to demonstrate that native PLC-a is expressed in M. tuberculosis H37Rv. Sera from mice immunized with recombinant PLC-a expressed in E. coli were used in immunoblots to evaluate PLC-a expression. The immune serum recognized a 49-kDa protein in immunoblots against M. tuberculosis extracts. No bands were visible in M. tuberculosis culture supernatants or extracts from M. avium, M. bovis and M. smegmatis. A 550-bp DNA fragment upstream of plc-a was cloned in the pJEM12 vector and the existence of a functional promoter was evaluated by detection of ß-galactosidase activity. ß-Galactosidase activity was detected in M. smegmatis transformed with recombinant pJEM12 grown in vitro and inside macrophages. The putative promoter was active both in vitro and in vivo, suggesting that expression is constitutive. In conclusion, expression of non-secreted native PLC-a was demonstrated in M. tuberculosis.

A carbohydrate-based mechanism of species recognition in sea urchin fertilization

In the present review, we describe a systematic study of the sulfated polysaccharides from marine invertebrates, which led to the discovery of a carbohydrate-based mechanism of sperm-egg recognition during sea urchin fertilization. We have described unique polymers present in these organisms, especially sulfated fucose-rich compounds found in the egg jelly coat of sea urchins. The polysaccharides have simple, linear structures consisting of repeating units of oligosaccharides. They differ among the various species of sea urchins in specific patterns of sulfation and/or position of the glycosidic linkage within their repeating units. These polysaccharides show species specificity in inducing the acrosome reaction in sea urchin sperm, providing a clear-cut example of a signal transduction event regulated by sulfated polysaccharides. This distinct carbohydrate-mediated mechanism of sperm-egg recognition coexists with the bindin-protein system. Possibly, the genes involved in the biosynthesis of these sulfated fucans did not evolve in concordance with evolutionary distance but underwent a dramatic change near the tip of the Strongylocentrotid tree. Overall, we established a direct causal link between the molecular structure of a sulfated polysaccharide and a cellular physiological event - the induction of the sperm acrosome reaction in sea urchins. Small structural changes modulate an entire system of sperm-egg recognition and species-specific fertilization in sea urchins. We demonstrated that sulfated polysaccharides - in addition to their known function in cell proliferation, development, coagulation, and viral infection - mediate fertilization, and respond to evolutionary mechanisms that lead to species diversity.

Long-term social recognition memory in adult male rats: factor analysis of the social and non-social behaviors

A modified version of the intruder-resident paradigm was used to investigate if social recognition memory lasts at least 24 h. One hundred and forty-six adult male Wistar rats were used. Independent groups of rats were exposed to an intruder for 0.083, 0.5, 2, 24, or 168 h and tested 24 h after the first encounter with the familiar or a different conspecific. Factor analysis was employed to identify associations between behaviors and treatments. Resident rats exhibited a 24-h social recognition memory, as indicated by a 3- to 5-fold decrease in social behaviors in the second encounter with the same conspecific compared to those observed for a different conspecific, when the duration of the first encounter was 2 h or longer. It was possible to distinguish between two different categories of social behaviors and their expression depended on the duration of the first encounter. Sniffing the anogenital area (49.9% of the social behaviors), sniffing the body (17.9%), sniffing the head (3%), and following the conspecific (3.1%), exhibited mostly by resident rats, characterized social investigation and revealed long-term social recognition memory. However, dominance (23.8%) and mild aggression (2.3%), exhibited by both resident and intruders, characterized social agonistic behaviors and were not affected by memory. Differently, sniffing the environment (76.8% of the non-social behaviors) and rearing (14.3%), both exhibited mostly by adult intruder rats, characterized non-social behaviors. Together, these results show that social recognition memory in rats may last at least 24 h after a 2-h or longer exposure to the conspecific.

Chemical pattern of brazilian apples: a chemometric approach based on the Fuji and Gala varieties

The chemical composition of apple juices may be used to discriminate between the varieties for consumption and those for raw material. Fuji and Gala have a chemical pattern that can be used for this classification. Multivariate methods correlate independent continuous chemical descriptors with the categorical apple variety. Three main descriptors of apple juice were selected: malic acid, total reducing sugar and total phenolic compounds. A chemometric approach, employing PCA and SIMCA, was used to classify apple juice samples. PCA was performed with 24 juices from Fuji and Gala, and SIMCA, with 15 juices. The exploratory and predictive models recognized 88% and 64%, respectively, as belonging to a mixed domain. The apple juice from commercial fruits shows a pattern related to cv. Fuji and Gala with boundaries from 0.18 to 0.389 g.100 mL-1 (malic acid), from 8.65 to 15.18 g.100 mL-1 (total reducing sugar) and from 100 to 400 mg.L-1 (total phenolic compounds), but such boundaries were slightly shorter in the remaining set of commercial apple juices, specifically from 0.16 to 0.36 g.100 mL-1, from 9.25 to 15.5 g.100 mL-1 and from 180 to 606 mg.L-1 for acidity, reducing sugar and phenolic compounds, respectively, representing the acid, sweet and bitter tastes.

Formal modelling for digital media distribution

Human beings have always strived to preserve their memories and spread their ideas. In the beginning this was always done through human interpretations, such as telling stories and creating sculptures. Later, technological progress made it possible to create a recording of a phenomenon; first as an analogue recording onto a physical object, and later digitally, as a sequence of bits to be interpreted by a computer. By the end of the 20th century technological advances had made it feasible to distribute media content over a computer network instead of on physical objects, thus enabling the concept of digital media distribution. Many digital media distribution systems already exist, and their continued, and in many cases increasing, usage is an indicator for the high interest in their future enhancements and enriching. By looking at these digital media distribution systems, we have identified three main areas of possible improvement: network structure and coordination, transport of content over the network, and the encoding used for the content. In this thesis, our aim is to show that improvements in performance, efficiency and availability can be done in conjunction with improvements in software quality and reliability through the use of formal methods: mathematical approaches to reasoning about software so that we can prove its correctness, together with the desirable properties. We envision a complete media distribution system based on a distributed architecture, such as peer-to-peer networking, in which different parts of the system have been formally modelled and verified. Starting with the network itself, we show how it can be formally constructed and modularised in the Event-B formalism, such that we can separate the modelling of one node from the modelling of the network itself. We also show how the piece selection algorithm in the BitTorrent peer-to-peer transfer protocol can be adapted for on-demand media streaming, and how this can be modelled in Event-B. Furthermore, we show how modelling one peer in Event-B can give results similar to simulating an entire network of peers. Going further, we introduce a formal specification language for content transfer algorithms, and show that having such a language can make these algorithms easier to understand. We also show how generating Event-B code from this language can result in less complexity compared to creating the models from written specifications. We also consider the decoding part of a media distribution system by showing how video decoding can be done in parallel. This is based on formally defined dependencies between frames and blocks in a video sequence; we have shown that also this step can be performed in a way that is mathematically proven correct. Our modelling and proving in this thesis is, in its majority, tool-based. This provides a demonstration of the advance of formal methods as well as their increased reliability, and thus, advocates for their more wide-spread usage in the future.

Recognition of nucleic acids by metal ion complexes

Metal-ion-mediated base-pairing of nucleic acids has attracted considerable attention during the past decade, since it offers means to expand the genetic code by artificial base-pairs, to create predesigned molecular architecture by metal-ion-mediated inter- or intra-strand cross-links, or to convert double stranded DNA to a nano-scale wire. Such applications largely depend on the presence of a modified nucleobase in both strands engaged in the duplex formation. Hybridization of metal-ion-binding oligonucleotide analogs with natural nucleic acid sequences has received much less attention in spite of obvious applications. While the natural oligonucleotides hybridize with high selectivity, their affinity for complementary sequences is inadequate for a number of applications. In the case of DNA, for example, more than 10 consecutive Watson-Crick base pairs are required for a stable duplex at room temperature, making targeting of sequences shorter than this challenging. For example, many types of cancer exhibit distinctive profiles of oncogenic miRNA, the diagnostics of which is, however, difficult owing to the presence of only short single stranded loop structures. Metallo-oligonucleotides, with their superior affinity towards their natural complements, would offer a way to overcome the low stability of short duplexes. In this study a number of metal-ion-binding surrogate nucleosides were prepared and their interaction with nucleoside 5´-monophosphates (NMPs) has been investigated by 1H NMR spectroscopy. To find metal ion complexes that could discriminate between natural nucleobases upon double helix formation, glycol nucleic acid (GNA) sequences carrying a PdII ion with vacant coordination sites at a predetermined position were synthesized and their affinity to complementary as well as mismatched counterparts quantified by UV-melting measurements.

Design and implementation of machine vision system for the mobile assembly robot

The review of intelligent machines shows that the demand for new ways of helping people in perception of the real world is becoming higher and higher every year. This thesis provides information about design and implementation of machine vision for mobile assembly robot. The work has been done as a part of LUT project in Laboratory of Intelligent Machines. The aim of this work is to create a working vision system. The qualitative and quantitative research were done to complete this task. In the first part, the author presents the theoretical background of such things as digital camera work principles, wireless transmission basics, creation of live stream, methods used for pattern recognition. Formulas, dependencies and previous research related to the topic are shown. In the second part, the equipment used for the project is described. There is information about the brands, models, capabilities and also requirements needed for implementation. Although, the author gives a description of LabVIEW software, its add-ons and OpenCV which are used in the project. Furthermore, one can find results in further section of considered thesis. They mainly represented by screenshots from cameras, working station and photos of the system. The key result of this thesis is vision system created for the needs of mobile assembly robot. Therefore, it is possible to see graphically what was done on examples. Future research in this field includes optimization of the pattern recognition algorithm. This will give less response time for recognizing objects. Presented by author system can be used also for further activities which include artificial intelligence usage.