Auswahl der wissenschaftlichen Literatur zum Thema „Algorithme d'alignement“

Ce mémoire propose un système permettant de suivre, à l'aide d'un ordinateur domestique et d'un microphone, une partition de musique jouée par un musicien. Le système utilise en entrée une partition de musique et le signal audio numérique monophonique de la partition de musique jouée par le musicien. Contrairement aux systèmes habituels, le système proposé donne la liberté au musicien de jouer différents segments de la partition de musique dans l'ordre qu'il le désire, et ce, sans préalablement informer le système de ses intentions. Pour ce faire, le système propose une variante de l'algorithme de la déformation dynamique du temps ( Dynamic Time Warping ) utilisant des notions musicales pour effectuer le suivi. Il est à noter que la complexité du système est suffisamment faible pour qu'un ordinateur domestique récent puisse suivre le musicien pendant que celui-ci joue la partition de musique, et ce, avec un délai constant de quelques notes de musique.

Dans ce travail de thèse, nous traitons le problème de planification de numérisation et nous abordons également la problématique d'alignement de nuages de points 3D. Ces problèmes peuvent être étudiés et globalisés pour répondre aux besoins de nombreux domaines d'études. Dans ce manuscrit, nous répondons à la problématique suivante : comment contrôler automatiquement une pièce mécanique en cours d'usinage ? La première contribution à cette étude est l'élaboration d'un algorithme de planification automatique de numérisation de la pièce en fonction des contrôles à effectuer sur celle-ci. L'approche que nous proposons permet de s'adapter à n'importe quel outil de numérisation optique. La méthode proposée est générale et permet en plus de s'adapter à n'importe quel environnement industriel dans lequel est positionnée la pièce à contrôler. La seconde contribution se focalise sur le cas spécifique des données issues de capteurs optiques, à savoir les nuages de points 3D. À partir du plan de numérisation, nous élaborons une stratégie d'alignement des nuages de points entre eux. Nous abordons la problématique des cas où l'alignement des nuages de points n'est pas possible et tentons de résoudre ce problème. Enfin, on montre plusieurs applications industrielles de ces algorithmes, et nous discutons que la précision des méthodes proposées sur ces cas. On propose plusieurs ouvertures sur la suite de ces travaux, notamment sur les cas spécifiques de pièces non-alignables ou de grande envergure. Des idées d'amélioration et de robustification des algorithmes sont faites pour la suite de la recherche
In this thesis work, we deal with the problem of scan planning and we also address the problem of 3D point clouds alignment. These problems can be studied and globalized to meet the needs of many fields of study. In this manuscript, we answer the following question: how to automatically control a mechanical part during machining? Or more precisely: how to obtain a good representation of the part so as to check its good conformity during the machining process? The first contribution to this study is the development of an automatic algorithm for planning the digitization of the part according to the controls to be carried out on it. The approach allows to adapt to any optical digitizing device. In our study, we show the results of this method on several fringe projection optical sensors and on several industrial parts. The proposed method is general and allows to adapt to any industrial environment in which the part to be controlled is positioned. The second contribution focuses on the specific case of data from optical sensors, i.e. 3D point clouds. From the scanning plan, we develop a strategy for aligning point clouds between them. We address the problem of cases where the alignment of point clouds is not possible and try to solve this problem. Finally, we show several industrial applications of these algorithms, and we study the precision of the methods on these cases. We propose several openings on the continuation of this work, in particular on the specific cases of non-alignable parts or on large parts. Ideas for improvement and robustification of the algorithms are discussed

Aligner des macromolécules telles que des protéines, des ADN et des ARN afin de révéler ou exploiter, leur homologie fonctionnelle est un défi classique en bioinformatique, qui offre de nombreuses applications, notamment dans la modélisation de structures et l'annotation des génomes. Un certain nombre d'algorithmes et d'outils ont été proposés pour le problème d'alignement structure-séquence d'ARN. Cependant, en ce qui concerne les ARN complexes, comportant des pseudo-noeuds, des interactions multiples et des paires de bases non canoniques, de tels outils sont rarement utilisés dans la pratique, en partie à cause de leurs grandes exigences de calcul, et de leur incapacité à supporter des types généraux de structures. Récemment, Rinaudo et al. ont donné un algorithme paramétré général pour la comparaison structure-séquence d'ARN, qui est capable de prendre en entrée n'importe quel type de structures comportant des pseudo-noeuds. L'algorithme paramétré est un algorithme de programmation dynamique basée sur la décomposition arborescente. Nous avons développé plusieurs variantes et extensions de cet algorithme. Afin de l'accélérer sans perte sensible de précision, nous avons introduit une approche de programmation dynamique par bandes. De plus, trois algorithmes ont été développés pour obtenir des alignements sous-optimaux. De plus, nous introduisons dans ce contexte la notion de MEA (Maximum-expected Structure-Alignment) pour calculer un alignement avec la précision maximale attendue sur un ensemble d'alignements. Tous ces algorithmes ont été implémentés dans un logiciel nommé LiCoRNA (aLignment of Complex RNAs). Les performances de LiCoRNA ont été évaluées d'abord sur l'alignement des graines des familles de de la base de données RFAM qui comportent des pseudo-noeuds. Comparé aux autres algorithmes de l'état de l'art, LiCoRNA obtient généralement des résultats équivalents ou meilleurs que ses concurrents. Grâce à la grande précision démontrée par LiCoRNA, nous montrons que cet outil peut être utilisé pour améliorer les alignements de certaines familles de RFAM qui comportent des pseudo-noeuds
Aligning macromolecules such as proteins, DNAs and RNAs in order to reveal, or conversely exploit, their functional homology is a classic challenge in bioinformatics, with far-reaching applications in structure modelling and genome annotation. In the specific context of complex RNAs, featuring pseudoknots, multiple interactions and non-canonical base pairs, multiple algorithmic solutions and tools have been proposed for the structure sequence alignment problem. However, such tools are seldom used in practice, due in part to their extreme computational demands, and because of their inability to support general types of structures. Recently, Rinaudo et al. gave a fully general parameterised algorithm for structure-sequence comparison, which is able to take as input any type of pseudoknotted structures. The parameterised algorithm is a tree decomposition based dynamic programming. To accelerate the dynamic programming algorithm without losing two much accuracy, we introduced a banded dynamic programming. Then three algorithms are introduced to get the suboptimal structure-sequence alignments. Furthermore, we introduce the notation Maximum Expected structure-sequence Alignment (MEA) to compute an alignment with maximum expected accuracy over a set of alignments. The Boltzmann match probability are computed based on the inside-outside algorithm. The algorithms are implemented in a software named LiCoRNA (aLignment of Complex RNAs). We first evaluate the performance of LiCoRNA on the seed alignment in the pseudoknotted RFAM families. Compared to the state-of-the-art algorithms, LiCoRNA shows generally equivalent or better results than its competitors. With the high accuracy showed by LiCoRNA, we further curate RFAM full pseudoknotted alignment. The reason why we realign full alignments is that covariance model does not support pseudoknot which may lead to misalign when building the full alignment

L'alignement multiple est une opération permettant de mettre en évidence la similarité entre plusieurs séquences. Il est notamment utilisé pour la reconstruction de phylogénies, la recherche de motifs et la prédiction de structures. Cette thèse s'intéresse au développement de nouveaux algorithmes pour ce problème particulièrement difficile, et introduit deux algorithmes progressifs ayant pour point commun de réaliser un alignement multiple par alignements successifs de groupes de séquences.
Le premier algorithme, Plasma utilise une méthode de descente, dont chaque itération consiste à réaliser des insertions de colonnes de brèches dans deux alignements multiples à aligner. Le second algorithme, Plasma II , est basé sur le principe de la programmation dynamique. Nous généralisons ici l'algorithme utilisé pour l'alignement de deux séquences, et étendons le cadre de la programmation dynamique `a l'alignement de deux alignements multiples. Cet algorithme ainsi que plusieurs variantes sont intensivement évalués sur les jeux d'essais de Balibase, montrant des résultats encourageants, voire compétitifs, par rapport à certains algorithmes de référence comme Clustal W, tant sur la qualité de l'alignement que sur le temps de calcul.