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.

Numbers and Languages

The thesis presents results obtained during the authors PhD-studies. First systems of language equations of a simple form consisting of just two equations are proved to be computationally universal. These are systems over unary alphabet, that are seen as systems of equations over natural numbers. The systems contain only an equation X+A=B and an equation X+X+C=X+X+D, where A, B, C and D are eventually periodic constants. It is proved that for every recursive set S there exists natural numbers p and d, and eventually periodic sets A, B, C and D such that a number n is in S if and only if np+d is in the unique solution of the abovementioned system of two equations, so all recursive sets can be represented in an encoded form. It is also proved that all recursive sets cannot be represented as they are, so the encoding is really needed. Furthermore, it is proved that the family of languages generated by Boolean grammars is closed under injective gsm-mappings and inverse gsm-mappings. The arguments apply also for the families of unambiguous Boolean languages, conjunctive languages and unambiguous languages. Finally, characterizations for morphisims preserving subfamilies of context-free languages are presented. It is shown that the families of deterministic and LL context-free languages are closed under codes if and only if they are of bounded deciphering delay. These families are also closed under non-codes, if they map every letter into a submonoid generated by a single word. The family of unambiguous context-free languages is closed under all codes and under the same non-codes as the families of deterministic and LL context-free languages.

Acute blood volume expansion delays the gastrointestinal transit of a charcoal meal in awake rats

The present study evaluates the effect of blood volume expansion on the gastrointestinal transit of a charchoal meal (2.5 ml of an aqueous suspension consisting of 5% charcoal and 5% gum arabic) in awake male Wistar rats (200-270 g). On the day before the experiments, the rats were anesthetized with ether, submitted to left jugular vein cannulation and fasted with water ad libitum until 2 h before the gastrointestinal transit measurement. Blood volume expansion by iv infusion of 1 ml/min Ringer bicarbonate in volumes of 3, 4 or 5% body weight delayed gastrointestinal transit at 10 min after test meal administration by 21.3-26.7% (P<0.05), but no effect was observed after 1 or 2% body weight expansion. The effect of blood volume expansion (up to 5% body weight) on gastrointestinal transit lasted for at least 60 min (P<0.05). Mean arterial pressure increased transiently and central venous pressure increased and hematocrit decreased (P<0.05). Subdiaphragmatic vagotomy and yohimbine (3 mg/kg) prevented the delay caused by expansion on gastrointestinal transit, while atropine (0.5 mg/kg), L-NAME (2 mg/kg), hexamethonium (10 mg/kg), prazosin (1 mg/kg) or propranolol (2 mg/kg) were ineffective. These data show that blood volume expansion delays the gastrointestinal transit of a charcoal meal and that vagal and yohimbine-sensitive pathways appear to be involved in this phenomenon. The delay in gastrointestinal transit observed here, taken together with the modifications of gastrointestinal permeability to salt and water reported by others, may be part of the mechanisms involved in liquid excess management.

Differences in prostate cancer detection between Canadian and Saudi populations

Few studies have addressed racial differences in prostate cancer (PCa) detection between Western and Arabian countries, although PCa has a significantly lower prevalence in Arabic populations compared to Western populations. Therefore, an explanation of this difference is lacking. Serum prostate-specific antigen (PSA) is a valuable marker used to select patients who should undergo prostate biopsies, although the manner in which it is used may require adjustments based on the ethnic population in question. We investigated racial differences in the PCa detection rate between Canadian and Saudi populations. A retrospective analysis was performed of data collected prospectively over 5 consecutive years in urology clinics at the McGill University Health Center (MUHC) and King Saud University Hospital (KSUH). Men who had high (>4'ng/mL) or rising PSA levels and a negative digital rectal examination were eligible. A total of 1403 Canadian and 414 Saudi patients were evaluated for the study; 717 and 158 men, median age 64 and 68 years, were included in the MUHC and KSUH cohorts, respectively, P<0.0001). Median serum PSA, prostate volume, and PSA density values were 6.1'ng/mL, 47.3 g, and 0.12'ng·mL−1·g−1, respectively, for MUHC patients and 5.2'ng/mL, 64.5'g, and 0.08'ng·mL−1·g−1, respectively, for KSUH patients (P<0.0001, t-test followed by one-way ANOVA). In addition, the KSUH group had a significantly lower PCa detection rate among patients younger than 60 years of age and with PSA values <10'ng/mL.

Defining Contexts in Context-Free Grammars

This thesis introduces an extension of Chomsky’s context-free grammars equipped with operators for referring to left and right contexts of strings.The new model is called grammar with contexts. The semantics of these grammars are given in two equivalent ways — by language equations and by logical deduction, where a grammar is understood as a logic for the recursive definition of syntax. The motivation for grammars with contexts comes from an extensive example that completely defines the syntax and static semantics of a simple typed programming language. Grammars with contexts maintain most important practical properties of context-free grammars, including a variant of the Chomsky normal form. For grammars with one-sided contexts (that is, either left or right), there is a cubic-time tabular parsing algorithm, applicable to an arbitrary grammar. The time complexity of this algorithm can be improved to quadratic,provided that the grammar is unambiguous, that is, it only allows one parsefor every string it defines. A tabular parsing algorithm for grammars withtwo-sided contexts has fourth power time complexity. For these grammarsthere is a recognition algorithm that uses a linear amount of space. For certain subclasses of grammars with contexts there are low-degree polynomial parsing algorithms. One of them is an extension of the classical recursive descent for context-free grammars; the version for grammars with contexts still works in linear time like its prototype. Another algorithm, with time complexity varying from linear to cubic depending on the particular grammar, adapts deterministic LR parsing to the new model. If all context operators in a grammar define regular languages, then such a grammar can be transformed to an equivalent grammar without context operators at all. This allows one to represent the syntax of languages in a more succinct way by utilizing context specifications. Linear grammars with contexts turned out to be non-trivial already over a one-letter alphabet. This fact leads to some undecidability results for this family of grammars

Microencapsulation of babassu coconut milk

The objective of this study was to obtain babassu coconut milk powder microencapsulated by spray drying process using gum Arabic as wall material. Coconut milk was extracted by babassu peeling, grinding (with two parts of water), and vacuum filtration. The milk was pasteurized at 85 ºC for 15 minutes and homogenized to break up the fat globules, rendering the milk a uniform consistency. A central composite rotatable design with a range of independent variables was used: inlet air temperature in the dryer (170-220 ºC) and gum Arabic concentration (10-20%, w/w) on the responses: moisture content (0.52-2.39%), hygroscopicity (6.98-9.86 g adsorbed water/100g solids), water activity (0.14-0.58), lipid oxidation (0.012-0.064 meq peroxide/kg oil), and process yield (20.33-30.19%). All variables influenced significantly the responses evaluated. Microencapsulation was optimized for maximum process yield and minimal lipid oxidation. The coconut milk powder obtained at optimum conditions was characterized in terms of morphology, particle size distribution, bulk and absolute density, porosity, and wettability.

Influence of spray drying operating conditions on microencapsulated rosemary essential oil properties

Spray drying is an important method used by the food industry in the production of microencapsulated flavors to improve handling and dispersion properties. The objective of this study was to evaluate the influence of the process conditions on the properties of rosemary essential oil microencapsulated by spray drying using gum Arabic as encapsulant. The effects of the wall material concentration (10-30%), inlet air temperature (135-195 ºC), and feed flow rate (0.5-1.0 L.h-1) on the moisture content, hygroscopicity, wettability, solubility, bulk and tapped densities, particle density, flowability, and cohesiveness were evaluated using a 2³ central composite rotational experimental design. Moisture content, hygroscopicity and wettability were significantly affected by the three factors analyzed. Bulk density was positively influenced by the wall material concentration and negatively by the inlet air temperature. Particle density was influenced by the wall material concentration and the inlet air temperature variables, both in a negative manner. As for the solubility, tapped density, flowability, and cohesiveness, the models did not fit the data well. The results indicated that moderate wall material concentration (24%), low inlet air temperature (135 ºC), and moderate feed flow rate (0.7 L.h-1) are the best spray drying conditions.

Kit̄̄̄̄̄̄̄̄āb al-ṭabīkh

Arabic cookery book, dated tentatively to 12th or 13th century by the editors (Öhrnberg & Mroueh) on the basis of the script. Aro suggests (grounds not made explicit) that the manuscript came to the library from the collections of G. A. Wallin, but Öhrnberg & Mroueh simply describe it as being of unknown provenance.

Papias, Vocabularium.

Abbaye Saint-Maur-des-Fossés ; cf. B. de Montfaucon, Bibliotheca bibliothecarum, II, 1739, p.1141-1143 : "73. 1095. Dictionarium amplissimum". Ex-libris : F. 1 : "Sti Germani a Pratis". Paris.

« Extraicts et mémoires concernans l'Ordre du Sainct-Esprit ».

Contient : « Extraict des statuts de l'Ordre du Sainct-Esprit, rédigé suivant l'ordre de l'alphabet » ; « Extraicts et copies des Registres de l'Ordre du Sainct-Esprit » ; « Noms de tous les officiers de l'Ordre qui ont exercé les charges, depuis la création dudict Ordre jusques à présent, 1662 » ; « Enregistrement de tout ce qui a concerné la promotion des commandeurs de l'Ordre du Sainct-Esprit, faicte le premier janvier 1662... » ; « Table alphabétique des extraicts et copies des Registres de l'Ordre du Sainct-Esprit » [cf. f. 21] ; « Lettre du maréchal de Fabert... au Roy, refusant la qualité de chevallier de l'Ordre de Sa Majesté », décembre 1661 ; « Discours sur les contraventions aux statuts de l'Ordre du Saint Esprit, faites par les officiers dudit Ordre. Ensemble sur la protestation du sieur marquis de Sourdis, chevalier de l'Ordre du S. Esprit, pour tous les chevaliers, signifiée ausdits officiers le deuxiesme janvier mil six cens cinquante sept », in-4°, impr ; « Responce à l'escrit publié contre les grâces et les priviléges accordez par nos rois Très-chrestiens aux officiers de leurs Ordres », in-4°, impr

« Les oeuvres de CHRISTOPHLE, parisien, très exsellant philosophe, corrigées de toute superfluité, traduite[s] d'italien en françoys, au mois de janvier 1584, par EA. D. M. ».

Contient : « Medul[l]a artis » ; « La Pierre végétable de Christophle, parisien, comme elle se contient dans son Alphabet » ; « Icy commence la Sommette du très excellant Christophle, parisien, de la composition de la grande pierre des philosophes », traité divisé en deux parties principales, dont la première comprend 17 chapitres, cotés de 7 à 23, et suivi (fol. 67 v°) de l' « Alphabet de la présente Sommette » ; Traité intitulé « Violete », en deux parties, suivi (fol. 99 v°) de l'« Alphabet de nostre susdite Violete » ; « Lucidaire, ou Somme majeur de l'art transmutatoire des corps des métaulx », en deux parties principales, suivi (fol. 216) de l'« Alp[h]abet dudict Lucidaire » ; Traité intitulé « La Pratique de nostre oeuvre », traité à la suite duquel se lisent les dates 1466 et 1476 ; « L'extraction et exubération de la très excellente quinte essence de l'estoille de la mer antienne » ; On a ajouté, d'une autre main, un « Abbrégé des euvres practicales [de] Christofle, parisien » ; Notes diverses d'un des possesseurs du volume, parmi lesquelles on remarque : « Monsieur Bongard [Jacques Bongars ?] est honest home et de mes bons amys ; Dieu le vueille conserver et tous les ciens par sa grâce et miséricorde infinie »

Recueil sur l'Alchimie, en vers et en prose ; traités ou poèmes de RAYMOND LULLE, de Jean DE LA FONTAINE, de Nicolas FLAMEL, de JEAN DE MEUNG, de Christofle DE GAMON.

Contient : « Dictionnaire des mots et termes plus usitez et cachez en l'art spagirique, desquels les philosophes chimiques ont accoutumé de se servir, suivant les lettres de l'alphabet : Acetum philosophorum- » ; inachevé ; « Recueil de plusieurs secretz et pièces curieuses, exactement recherché ; le tout aprouvé pour estre bon et avoir esté esprouvé ; faict par moy, G. D. R., à Paris, ce 30e juillet 1666 » ; Recettes diverses ; « Le débat et question sur la grande oeuvre, entre Aaron et Marie la prophétesse » ; « Le Vade mecum, ou abrégé de l'art chimique, touchant la transmutation des mestaux et vraye pierre des philosophes, extraict des oeuvres du très docte et très vénérable RAYMOND LULLE, traduict fidellement du latin en françois, en faveur des amateurs de la philosophie hermétique... Le livre de l'art compendieuse de Raymond Lulle, qu'il a nommé Vade mecum : La teinture du feu est la plus excellente... » ; l'ouvrage ici traduit est celui qui est imprimé dans la Bibliotheca chemica curiosa de J.-J. Manget, t. I, pp. 849-852, sous le titre : Raymundi Lullii liber Artis compendiosae, quem Vade mecum nuncupavit ; n° CXI de la notice de l'Histoire littéraire de la France, t. XXIX, p. 280 ; « Claviculles de RAYMOND LULLE ; Raymondi Lullii clavicula. Chers enfans, qui voulez estre de nostre doctrine... ; et pour ce que sans ce petit livre et clavicule... » ; traduction et extraits, avec de notables différences, de l'ouvrage imprimé dans la Bibliotheca chemica curiosa de J.-J. Manget, t. I, pp. 872-875, sous le titre : Clavicula Raymundi Lullii..., quae et Apertorium dicitur ; Hist. littér., ibid., p. 284, n° CXVII ; Traités d'alchimie, en vers, probablement copie du recueil publié à Paris, en 1561, sous le titre : De la transformation métallique, trois anciens traités en rithme françoise, et comprenant : La Fontaine des amoureux de science, par Jean DE LA FONTAINE, de Valenciennes (fol. 106), — le Sommaire philosophique, de Nicolas FLAMEL (fol. 117), — et les Remontrances de Nature à l'alchimiste errant, par JEAN DE MEUNG (fol. 120 v°) ; « Du traité de Terra terrarum » ; « Christofle DE GAMON à un singulier » ; poème de C. de Gamon sur l'alchimie, connu sous le titre de « Trésor des Trésors », avec partie du commentaire

Français 1353

Contient : 1° Horoscope de Baudouin de Courtenai ; 2° Introductoire d'astronomie ; 3° « Li Livres ABU ALI des nativitez des enfenz, de lor fortune » ; 4° « Le Epistle MESSEHALA es choses de l'eclipse del soloil et de la lune es conjunctions des planetes... translatez de JEHAN D'ESPALE en lime de arabic en latin » ; 5° « Li Livres des flors de ALBUMAXAR à faire jugemenz » ; 6° Le Livre des « corruptions de l'air » ; 7° Horoscope de Baudoin de Courtenai

Bounds on edit metric codes with combinatorial DNA constraints

The design of a large and reliable DNA codeword library is a key problem in DNA based computing. DNA codes, namely sets of fixed length edit metric codewords over the alphabet {A, C, G, T}, satisfy certain combinatorial constraints with respect to biological and chemical restrictions of DNA strands. The primary constraints that we consider are the reverse--complement constraint and the fixed GC--content constraint, as well as the basic edit distance constraint between codewords. We focus on exploring the theory underlying DNA codes and discuss several approaches to searching for optimal DNA codes. We use Conway's lexicode algorithm and an exhaustive search algorithm to produce provably optimal DNA codes for codes with small parameter values. And a genetic algorithm is proposed to search for some sub--optimal DNA codes with relatively large parameter values, where we can consider their sizes as reasonable lower bounds of DNA codes. Furthermore, we provide tables of bounds on sizes of DNA codes with length from 1 to 9 and minimum distance from 1 to 9.