ABSTRACT The longest common subsequence (LCS) problem is a classical problem both in com- binational optimization and computational biology. During the past few decades, a considerable number of studies have been focused on LCS and its related prob- lems. In this thesis, we shall present a complete survey on LCS and its related problems, and review some e¡Ócient algorithms for solving these problems. We shall also give the de¡Ânition to each problem, present some theorems, and illustrate time complexity and space complexity of the algorithms for solving these problems.

This thesis considers a variant of the classical problem for finding the longest common subsequence (LCS) called longest common subsequence problem with a gapped constraint (LCSGC). Given two sequences A, B, and a constrained sequence C, which is accomplished with a corresponding gapped constraint for each symbol, whose lengths are m, n, and r, respectively, the LCSGC problem is to find an LCS of A and B, such that C is also a subsequence of this LCS and the gapped constraints corresponding to C are satisfied. In this thesis, two algorithms with time complexities O(m2n2r) and O(mnr ¡Ñ min(m, n)) are proposed based on the dynamic programming technique for solving the LCSGC problem.

The laser-induced holographic grating technique was employed to study the dynamic of the intensity grating formation in the azo-dye doped liquid crystals. The liquid crystal material in this study has several mesomorphic phases: Smectic C, Smectic A, Nematic and Isotropic. The first order of diffraction in the mesomorphic phases have been investigated by changing the polarizations of the probe beam.

Problems of some regularities in strings, such as repetition, period, seed, square, etc., have been studied extensively recently. Many algorithms have been proposed to solve these problems in O(1) time complexity on an n imes n reconfigurable bus model, where $n$ is the length of the given string. In this paper, we concentrate to solve problems of another form of regularity, the string superprimitivity test problem and the LCS (longest common subsequence) problem in strings on the reconfigurable bus model. And we propose a O(log n) time parallel algorithm to solve the string superprimitivity test problem. We also review some algorithms for the LCS problem. Further research is also given in this paper.

With the improvement of biological techniques, the amount of biosequences data, such as DNA, RNA and protein sequences, are growing explosively. It is almost impossible to handle such huge amount of data purely by manpower. Thus the requirement of the great computing power is essential. There are some ways to treat biosequence data, finding identical biosequences, searching similar biosequences, or mining the signature of biosequences. All of these are based on the same problems, the biosequence alignment problems. In this dissertation, we shall study the biosequence alignment problems to raise the biological meaning of the optimal or near-optimal alignments since the biologists and computer scientists sometimes argue the biological meaning of the mathematically optimal alignment obtained based on some scoring functions. We first study the methods to improve the optimal alignment of two given biosequences. Since usually the optimal alignment is not unique, there should exist the best one among the optimal alignments, and we try to extract this by defining some other criteria to judge the goodness of the alignments when the traditional methods cannot decide which is the better one. Two algorithms are proposed for solving the newly defined biosequence alignment problems, the smoothest optimal alignment and the most conserved optimal alignment problems. Some other criteria are also discussed since most of them can be solved in a similar way. Then we notice that the most biologically meaningful alignment may not be the optimal one since there is no perfect scoring matrix. We address our candidates in those near-optimal alignments, and present a tracing marking function to get all near-optimal alignments and use the criterion "the most conserved" to filter it, which is named as the near-optimal block alignment (NBA) problem. Finally, as everybody knows that existing scoring matrices are not perfect at all, we try to figure out how we choose the winner when multiple scoring matrices are applied. We define some reasonable schemes to decide the winner alignment. In this dissertation, we solve and discuss the algorithms for near-optimal alignment problems on biosequences. In the future, we would like to do some experiments to support or reject these concepts.

Research Doctorate - Doctor of Philosophy (PhD) / Machine learning methods usually represent knowledge and hypotheses using attribute-value languages, principally because of their simplicity and demonstrated utility over a broad variety of problems. However, attribute-value languages have limited expressive power and for some problems the target function can only be expressed as an exhaustive conjunction of specific cases. Such problems are handled better with inductive logic programming (ILP) or relational reinforcement learning (RRL), which employ more expressive languages, typically languages over first-order logic. Methods developed within these fields generally extend upon attribute-value algorithms; however, many attribute-value algorithms that are potentially viable for RRL, the younger of the two fields, remain to be extended. This thesis investigates an approach to RRL derived from the learning classifier system XCS. In brief, the new system, FOXCS, generates, evaluates, and evolves a population of ``condition-action'' rules that are definite clauses over first-order logic. The rules are typically comprehensible enough to be understood by humans and can be inspected to determine the acquired principles. Key properties of FOXCS, which are inherited from XCS, are that it is general (applies to arbitrary Markov decision processes), model-free (rewards and state transitions are ``black box'' functions), and ``tabula rasa'' (the initial policy can be unspecified). Furthermore, in contrast to decision tree learning, its rule-based approach is ideal for incrementally learning expressions over first-order logic, a valuable characteristic for an RRL system. Perhaps the most novel aspect of FOXCS is its inductive component, which synthesizes evolutionary computation and first-order logic refinement for incremental learning. New evolutionary operators were developed because previous combinations of evolutionary computation and first-order logic were non-incremental. The effectiveness of the inductive component was empirically demonstrated by benchmarking on ILP tasks, which found that FOXCS produced hypotheses of comparable accuracy to several well-known ILP algorithms. Further benchmarking on RRL tasks found that the optimality of the policies learnt were at least comparable to those of existing RRL systems. Finally, a significant advantage of its use of variables in rules was demonstrated: unlike RRL systems that did not use variables, FOXCS, with appropriate extensions, learnt scalable policies that were genuinely independent of the dimensionality of the task environment.

Avec le développement de la technologie, les mesures des champs de vitesse instationnaire sont disponibles maintenant. Il s'en suit une augmentation de l'intérêt de l'analyse lagrangienne des données. Un outil central pour analyser les écoulements est l'exposant de Lyapunov à temps fini (FTLE). Il permet d’identifier les structures cohérentes lagrangiennes LCS qui apparaissent comme des crêtes du champ de FTLE. Les LCS sont des quasi barrières de transport et séparent le domaine fluide en régions aux propriétés dynamiques différentes. Cependant, la méthodologie de calcul actuelle des FTLE exige l'évaluation numérique d'un grand nombre de trajectoires de particules fluides sur un maillage cartésien ou adaptatif qui est superposé aux champs de vitesses simulées ou mesurées.Dans ce travail de thèse, nous proposons une nouvelle méthode de calcul du champ de l'exposant de Lyapunov à temps fini FTLE. Pour cela, nous utilisons la méthode des moments d'ordre 2 qui permet d'évaluer au cours du temps la dispersion des particules distribuées uniformément dans un domaine circulaire ou elliptique. Nous appelons ce nouveau champ scalaire, champ de M-FTLE. Nous validons cette approche, théoriquement en tout point du domaine fluide en comparant M-FTLE et FTLE et aussi en faisant la comparaison sur des exemples classiques (champ de vitesse linéaire, circulaire ou hyperbolique) et sur un exemple numérique (champ de vitesse du double gyre). Cette méthode est alors appliquée sur des données expérimentales du champ de vitesse du mascaret, obtenues au sein l'institut 'Pprime' par vélocimétrie par image de particules PIV. / With the development of technology, instantaneous flow fields coming from experiments or numerical simulation are available now. It has been followed by a rise of interest for the Lagrangian analysis of such data. One central tool to analyze the flow fields is the Finite Time Lyapunov Exponent (FTLE). It allows to the identify of the Lagrangian Coherent Structures (LCS) which appear as ridges in the FTLE fields. The LCS are quasi transport bareers and separatte the fluid domain into regions which have different dynamic properties. However, the computation methodology currently used in order to obtain the FTLE requires numerical evalution of a large number of fluid particle trajectories on cartesian or adaptive meshes that are superimposed on the original data grid.In this thesis, we propose a new method for calculating the Finite Time Lyapunov Exponent FTLE fields. For this, we use the method of second-order moments which allows to evaluate over time the dispersion of particles uniformly distributed in a circular or elliptical domain. We call this new scalar field, the M-FTLE field. We validate this approach theoretically, at every point of the fluid domain by comparing FTLE and M-FTLE and also by the comparison of the classic examples (linear velocity field, circular and hyperbolic) and a numerical example (velocity field of double gyre). This method is then applied on experimental measurements of tidal bore velocity fields, obtained within the institute 'Pprime' by using a measurement technique called particle image velocimetry (PIV).

La peau est un organe très exposé à l’environnement et fournit la première ligne de défense contre de nombreux pathogènes. Cette fonction est remplie dans l’épiderme murin par les cellules de Langerhans (LCs) et les cellules T dendritiques de l’épiderme (DETCs). Alors que le développement de ces cellules a bien été étudié, peu d’expériences ont été effectuées sur leur renouvellement en condition homéostatique chez des animaux adultes sans manipulations. Nous avons alors développé un système de traçage cellulaire par fluorescence multicolore pour étudier l’homéostasie des LCs et des DETCs. Cette approche de «fate mapping» m’a permis de mettre en évidence un modèle dans lequel le réseau adulte des LCs est formé d’unités prolifératives adjacentes composées de LCs en division et leurs cellules filles. Nous avons identifié que les cellules en division étaient majoritairement représentées par la fraction la plus immature des LCs, suggérant que ces LCs peuvent régénérer leur réseau grâce à une capacité de prolifération limitée. Lors d’une inflammation importante, les LCs sont renouvelées par des progéniteurs issus de la moelle osseuse et s’organisent également en unités de prolifération. Je me suis ensuite intéressé à l’homéostasie des DETCs. Ce réseau est formé de la même manière par des unités prolifératives de DETCs. Un modèle de greffe de peau nous a permis de montrer que les DETCs semblent renouveler les cellules disparues dans une zone restreinte. En conclusion, mes travaux de thèse ont permis de révéler les dynamiques cellulaires qui régissent l’homéostasie des cellules immunitaires de l’épiderme. / The skin is an organ very much exposed to the environment and supplies the primary line of defence against several pathogens. In the mouse model epidermis, this function is fulfilled by Langerhans’ cells (LCs) and dendritic T cells (DETCs). While LCs and DETCs development have thoroughly been studied, few experiences have been carried out concerning the renewal of these cells through homeostatic conditions in adult “nonmanipulated” animals. Then we have designed a new system of fate mapping, by way of multi-coloured fluorescence to study the LCs and DETCs homeostasis. This method of fate mapping allowed me to highlight a model in which the adult network of LCs is made up of adjacent proliferating units, made of dividing LCs and of their daughter cells. We have identified that the dividing cells were mainly represented by the most immature fraction of LCs, suggesting that these LCs can renew their network thanks to a limited ability to proliferate. During significant inflammation, LCs are renewed by progenitors coming from the bone marrow and organize themselves in proliferation units as well. I also took an interest in the homeostasis of DETCs. In the same way as for the LCs, this network seems to be made up of DETCs proliferating units. A model of skin graft led us to show that the DETCs seem to renew the missing cells in a restricted area. As a conclusion, my research work allowed me to reveal the cellular dynamism which governs the homeostasis of the epidermis’ immune cells.

Computing least common subsumers (lcs) and most specific concepts (msc) are inference tasks that can be used to support the „bottom up” construction of knowledge bases for KR systems based on description logic. For the description logic ALN, the msc need not always exist if one restricts the attention to acyclic concept descriptions. In this paper, we extend the notions lcs and msc to cyclic descriptions, and show how they can be computed. Our approach is based on the automata-theoretic characterizations of fixed-point semantics for cyclic terminologies developed in previous papers. / An abridged version of this technical report has been published at KI'98.

No description available.