Rozprawy doktorskie na temat „Alignment algorithm”

An essential tool in biology is the alignment of multiple sequences. Biologists use multiple sequence alignments for tasks such as predicting protein structure and function, reconstructing phylogenetic trees, and finding motifs. Constructing high-quality multiple alignments is computationally hard, both in theory and in practice, and is typically done using heuristic methods. The majority of state-of-the-art multiple alignment programs employ a form and polish strategy, where in the construction phase, an initial multiple alignment is formed by progressively merging smaller alignments, starting with single sequences. Then in a local-search phase, the resulting alignment is polished by repeatedly splitting it into smaller alignments and re-merging. This merging of alignments, the basic computational problem in the construction and local-search phases of the best multiple alignment heuristics, is called the Aligning Alignments Problem. Under the sum-of-pairs objective for scoring multiple alignments, this problem may seem to be a simple extension of two-sequence alignment. It is proven here, however, that with affine gap costs (which are recognized as necessary to get biologically-informative alignments) the problem is NP-complete when gaps are counted exactly. Interestingly, this form of multiple alignment is polynomial-time solvable when we relax the exact count, showing that exact gap counts themselves are inherently hard in multiple sequence alignment. Unlike general multiple alignment however, we show that Aligning Alignments with affine gap costs and exact counts is tractable in practice, by demonstrating an effective algorithm and a fast implementation. Our software AlignAlign is both time- and space-efficient on biological data. Computational experiments on biological data show instances derived from standard benchmark suites can be optimally aligned with surprising efficiency, and experiments on simulated data show the time and space both scale well.

Focal plane corrected Cassegrain type optical systems have been widely used in various fields. The axial alignment of complex optical systems is not easy and a practical alignment method is needed for such systems. Tilts, decenters and axial motion of elements or group of elements in the system are the typical alignment parameters. Interferometric measurement is an effective way to see the errors caused by the misalignment of each element in an optical system. In this thesis, alignment of a Cassegrain type telescope will be examined by using interferometric measurements and modulation transfer function simulations.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 89-90).
String alignment and comparison in Computer Science is a well-explored space with classic problems such as Longest Common Subsequence that have practical application in bioinformatic genomic sequencing and data comparison in revision control systems. In the field of musicology, score alignment and comparison is a problem with many similarities to string comparison and alignment but also vast differences. In particular we can use ideas in string alignment and comparison to compare a music score in the MIDI format with a music score generated from Optical Musical Recognition (OMR), both of which have incomplete or wrong information, and correct errors that were introduced in the OMR process to create an improved third score. This thesis creates a set of algorithms that align and compare MIDI and OMR music scores to produce a corrected version of the OMR score that borrows ideas from classic computer science string comparison and alignment algorithm but also incorporates optimizations and heuristics from music theory.
by Emily H. Zhang.
M. Eng.

The exact algorithm formulated by Kececioglu and Starrett (2004) provides a solution to the NP-complete problem of aligning alignments in most biological cases. This work investigates potential speedups that may be gained through the parallelization of the dynamic programming phase of this particular algorithm. Results indicate it is possible to improve the run time performance of the algorithm over non-trivial alignments that compose to a matrix of greater than 10^5 cells.

The genome sequence alignment problems are very important ones from the computational biology perspective. These problems deal with large amount of data which is memory intensive as well as computation intensive. In the literature, two separate algorithms have been studied and improved – one is a Pairwise sequence alignment algorithm which aligns pairs of genome sequences with memory reduction and parallelism for the computation and the other one is the multiple sequence alignment algorithm that aligns multiple genome sequences and this algorithm is also parallelized efficiently so that the workload of the alignment program is well distributed. The parallel applications can be launched on different environments where shared memory is very well suited for these kinds of applications. But shared memory environment has the limitation of memory usage as well as scalability also these machines are very costly. A better approach is to use the cluster of computers and the cluster environment can be further enhanced to a grid environment so that the scalability can be improved introducing multiple clusters. Here the grid environment is studied as well as the shared memory and cluster environment for the two applications. It can be stated that for carefully designed algorithms the grid environment is comparable for its performance to other distributed environments and it sometimes outperforms the others in terms of the limitations of resources the other distributed environments have.

For as long as biologists have been computing alignments of sequences, the question of what values to use for scoring substitutions and gaps has persisted. In practice, substitution scores are usually chosen by convention, and gap penalties are often found by trial and error. In contrast, a rigorous way to determine parameter values that are appropriate for aligning biological sequences is by solving the problem of Inverse Parametric Sequence Alignment. Given examples of biologically correct reference alignments, this is the problem of finding parameter values that make the examples score as close as possible to optimal alignments of their sequences. The reference alignments that are currently available contain regions where the alignment is not specified, which leads to a version of the problem with partial examples.In this dissertation, we develop a new polynomial-time algorithm for Inverse Parametric Sequence Alignment that is simple to implement, fast in practice, and can learn hundreds of parameters simultaneously from hundreds of examples. Computational results with partial examples show that best possible values for all 212 parameters of the standard alignment scoring model for protein sequences can be computed from 200 examples in 4 hours of computation on a standard desktop machine. We also consider a new scoring model with a small number of additional parameters that incorporates predicted secondary structure for the protein sequences. By learning parameter values for this new secondary-structure-based model, we can improve on the alignment accuracy of the standard model by as much as 15% for sequences with less than 25% identity.

Highway alignment development is recognised as a non-linear constrained optimisation problem. It is affected by many economical, social, and environmental factors subject to many design constraints. The highway alignment development process is therefore considered complex but very important. Highway alignment development is about finding an optimum alignment solution between two termini points in a 3D space, subject to several constraints. The development process using the current method is considered complex because of the number of the design elements involved, their interactions, and the formulations required to relate them to a realistic highway alignment. Moreover, it is considered that an alignment, generated using the existing method, results in a sub-optimal solution. This is due to the fact that the two alignments (horizontal and vertical alignments) are found in two independent stages and from only a handful number of alternative evaluations. This research reports on a new approach for improving the process of highway alignment development by utilising modern technologies. It proposes a novel design approach, as an alternative to the existing method, for highway alignment development in a three-dimensional space (considering the horizontal and vertical alignments simultaneously). It describes a method for highway alignment development through station points. Station points, as points along the centre line of alignment which are defined by their X, Y, and Z coordinates, are used to define the alignment configuration. The research also considers the implications of access provision (in term of junctions) and their locations on highway alignment. The environmental factors (noise and air pollution in terms of proximity distance) and accessibility (user and link construction costs in terms of access costs) are embedded in the formulations required to represent junctions in the model. The proposed approach was tested through the development of a genetic algorithms based optimisation model. To achieve this, several algorithms were developed to perform the search. The evaluation of the solutions was handled by a fitness function that includes construction (length), location (land acquisition, environmentally sensitive areas, and soil condition), and earthwork (fill and cut material) dependent costs. Other forms of costs that are quantifiable can also be incorporated within the fitness function. The critical constraints, believed important for realistic alignments (horizontal curvature, vertical curvature, and maximum gradient) are also dealt with within the model formulation. The experimental results show that the problem of highway alignment can be better represented using the concept of station points, by which better alignment solutions (global or near global solutions) were achieved. It was also shown that the alignment development process could be simplified through the use of station points, resulting in the efficient evaluation of more alternatives. Furthermore, the results conclude that a highway alignment cannot be optimum unless it is simultaneously optimised with junctions. Further investigations and development are also recommended for future studies.

Wireless sensor networks has been one of the major research topics in recent years because of its great potential for a wide range of applications. In some application scenarios, sensor nodes intend to report the sensing data to a far-field destination, which cannot be realized by traditional transmission techniques. Due to the energy limitations and the hardware constraints of sensor nodes, distributed transmit beamforming is considered as an attractive candidate for long-range communications in such scenarios as it can reduce energy requirement of each sensor node and extend the communication range. However, unlike conventional beamforming, which is performed by a centralized antenna array, distributed beamforming is performed by a virtual antenna array composed of randomly located sensor nodes, each of which has an independent oscillator. Sensor nodes have to coordinate with each other and adjust their transmitting signals to collaboratively act as a distributed beamformer. The most crucial problem of realizing distributed beamforming is to achieve carrier phase alignment at the destination. This thesis will investigate distributed beamforming from both theoretical and practical aspects. First, the bit error ratio performance of distributed beamforming with phase errors is analyzed, which is a key metric to measure the system performance in practice. We derive two distinct expressions to approximate the error probability over Rayleigh fading channels corresponding to small numbers of nodes and large numbers of nodes respectively. The accuracy of both expressions is demonstrated by simulation results. The impact of phase errors on the system performance is examined for various numbers of nodes and different levels of transmit power. Second, a novel iterative algorithm is proposed to achieve carrier phase alignment at the destination in static channels, which only requires one-bit feedback from the destination. This algorithm is obtained by combining two novel schemes, both of which can greatly improve the convergence speed of phase alignment. The advantages in the convergence speed are obtained by exploiting the feedback information more efficiently compared to existing solutions. Third, the proposed phase alignment algorithm is modified to track time-varying channels. The modified algorithm has the ability to detect channel amplitude and phase changes that arise over time due to motion of the sensors or the destination. The algorithm can adjust key parameters adaptively according to the changes, which makes it more robust in practical implementation.

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

Made available in DSpace on 2016-04-29T14:23:42Z (GMT). No. of bitstreams: 1 Aline Rodrigheri Ioste.pdf: 3892568 bytes, checksum: d4b25a166ea46de0a3b7edfbfeab6923 (MD5) Previous issue date: 2016-03-04
The objective of this study is to deeply understand the techniques currently used in optimal alignment of DNA sequences, focused on the strengths and limitations of these methods. Analyzing the feasibility of creating a new logical approach able to ensure optimal results , taking into account existing problems in optimal alignment as: (i ) the numerous alignment possibilities of two sequences , ( ii ) the great need for space and memory the machines, ( ii ) processing time to compute the optimal data and (iv ) exponential growth. This study allowed the beginning of the creation of a new logical approach to the global optimum alignment, showing promising results in higher scores with less need for calculations where the mastery of these new techniques can lead to use search of excellent results in the global alignment optimal in large data bases
O objetivo deste estudo é entender profundamente as técnicas utilizadas atualmente no alinhamento ótimo de sequências de DNA e analisar a viabilidade da criação de uma nova abordagem lógica capaz de garantir o resultado ótimo, levando em consideração os problemas existentes no alinhamento ótimo como: (i) as inúmeras possibilidades de alinhamento de duas sequências, (ii) a grande necessidade de espaço e memória das máquinas, (ii) o tempo de processamento para computar os dados ótimos e (iv) seu crescimento exponencial. O presente estudo permitiu o início da criação de uma nova abordagem lógica para o alinhamento ótimo global, demonstrando resultados promissores de maiores pontuações com menos necessidades de cálculos, onde o domínio destas novas técnicas pode conduzir à utilização da busca de resultados ótimos no alinhamento global de sequências biológicas em grandes bases de dados

To be able to understand characteristics and purpose of biological sequences correctly, it is crucial to have a possibility to sort and compare them. Because of this need and to extend existing knowledge pool, numerous methods were proposed. Especially in field of multiple sequences alignment. Methods for multiple sequences alignment may provide various valuable information about sequences which failed to show enough similarity in pairwise alignment. According to this, several algorithms were implemented in various computer applications which provide a way to analyse huge sets of data. One of those, the progressive alignment algorithm, is implemented as a part of this thesis

Genetic research projects currently can require enormous computing power to processes the vast quantities of data available. Further, DNA sequencing projects are generating data at an exponential rate greater than that of the development microprocessor technology; thus, new, faster methods and techniques of processing this data are needed. One common type of processing involves searching a sequence database for the most similar sequences. Here we present a distributed database search system that utilizes adaptive computing technologies. The search is performed using the Smith-Waterman algorithm, a common sequence comparison algorithm. To reduce the total search time, an initial search is performed using a version of the algorithm, implemented in adaptive computing hardware, which is designed to efficiently perform the initial search. A final search is performed using a complete version of the algorithm. This two-stage search, employing adaptive and distributed hardware, achieves a performance increase of several orders of magnitude over similar processor based systems.
Master of Science

Interference is a fundamental problem in wireless networks. An effective solution to this problem usually calls for a cross-layer approach. Although there exist a large volume of works on interference management techniques in the literature, most of them are limited to signal processing at the physical (PHY) layer or information-theoretic exploitation. Studies of advanced interference techniques from a cross-layer optimization perspective remain limited, especially involving multi-hop wireless networks. This dissertation aims at filling this gap by offering a comprehensive investigation of three interference techniques: interference cancellation (IC), interference alignment (IA), and interference neutralization (IN). This dissertation consists of three parts: the first part studies IC in distributed multi-hop multiple-input multiple-output (MIMO) networks; the second part studies IA in multi-hop networks, cellular networks, and underwater acoustic (UWA) networks; and the third part focuses on IN in multi-hop single-antenna networks. While each part makes a step towards advancing an interference technique, they collectively constitute a body of work on interference management in the networking research community. Results in this dissertation not only advance network-level understanding of the three interference management techniques, but also offer insights and guidance on how these techniques may be incorporated in upper-layer protocol design. In the first part, we study IC in multi-hop MIMO networks where resource allocation is achieved through neighboring node coordination and local information exchange. Based on a well-established degree-of-freedom (DoF) MIMO model, we develop a distributed DoF scheduling algorithm with the objective of maximizing network-level throughput while guaranteeing solution feasibility at the PHY layer. The proposed algorithm accomplishes a number of beneficial features, including polynomial-time complexity, amenability to local implementation, a guarantee of feasibility at the PHY layer, and competitive throughput performance. Our results offer a definitive ``yes'' answer to the question --- Can the node-ordering DoF model be deployed in a distributed multi-hop MIMO network? In particular, we show that the essence of the DoF model --- a global node ordering, can be implicitly achieved via local operations, albeit it is invisible to individual node. In the second part, we investigate IA in various complex wireless networks from a networking perspective. Specifically, we study IA in three different domains: spatial domain, spectral domain, and temporal domain. In the spatial domain, we study IA for multi-hop MIMO networks. We derive a set of simple constraints to characterize the IA capability at the PHY layer. We prove that as long as the set of simple constraints are satisfied, there exists a feasible IA scheme (i.e., precoding and decoding vectors) at the PHY layer so that the data streams on each link can be transported free of interference. Therefore, instead of dealing with the complex design of precoding and decoding vectors, our IA constraints only require simple algebraic addition/subtraction operations. Such simplicity allows us to study network-level IA problems without being distracted by the tedious details in signal design at the PHY layer. Based on these IA constraints, we develop an optimization framework for unicast and multicast communications. In the spectral domain, we study IA in OFDM-based cellular networks. Different from spatial IA, spectral IA is achieved by mapping data streams onto a set of frequency bands/subcarriers (rather than a set of antenna elements). For the uplink, we derive a set of simple IA constraints to characterize a feasible DoF region for a cellular network. We show how to construct precoding and decoding vectors at the PHY layer so that each data stream can be transported free of interference. Based on the set of IA constraints, we study a user throughput maximization problem and show the throughput improvement over two other schemes via numerical results. For the downlink, we find that we can exploit the uplink IA constraints to the downlink case simply by reversing the roles of user and base station. Further, the downlink user throughput maximization problem has the exactly same formulation as the uplink problem and thus can be solved in the exactly same way. In the temporal domain, we study IA for UWA networks. A fundamental issue in UWA networks is large propagation delays due to slow signal speed in water medium. But temporal IA has the potential to turn the adverse effect of large propagation delays into something beneficial. We propose a temporal IA scheme based on propagation delays, nicknamed PD-IA, for multi-hop UWA networks. We first derive a set of PD-IA constraints to guarantee PD-IA feasibility at the PHY layer. Then we develop a distributed PD-IA scheduling algorithm, called Shark-IA, to maximally overlap interference in a multi-hop UWA network. We show that PD-IA can turn the adverse propagation delays to throughput improvement in multi-hop UWA networks. In the third part, we study IN for multi-hop single-antenna networks with full cooperation among the nodes. The fundamental problem here is node selection for IN in a multi-hop network environment. We first establish an IN reference model to characterize the IN capability at the PHY layer. Based on this reference model, we develop a set of constraints that can be used to quickly determine whether a subset of links can be active simultaneously. By identifying each eligible neutralization node as a neut, we study IN in a multi-hop network with a set of sessions and derive the necessary constraints to characterize neut selection, IN, and scheduling. These constraints allow us to study IN problems from a networking perspective but without the need of getting into signal design issues at the PHY layer. By applying our IN model and constraints to study a throughput maximization problem, we show that the use of IN can generally increase network throughput. In particular, throughput gain is most significant when there is a sufficient number of neuts that can be used for IN. In summary, this dissertation offers a comprehensive investigation of three interference management techniques (IC, IA, and IN) from a networking perspective. Theoretical and algorithmic contributions of this dissertation encompass characterization of interference exploitation capabilities at the PHY layer, derivation of tractable interference models, development of feasibility proof for each interference model, formulation of throughput maximization problems, design of distributed IC and PD-IA scheduling algorithms, and development of near-optimal solutions with a performance guarantee. The results in this dissertation offer network-level understanding of the three interference management techniques and lay the groundwork for future research on interference management in wireless networks.
Ph. D.

Las exigentes tolerancias de alineación en los componentes de los futuros colisionadores lineales de partículas requieren el desarrollo de nuevas técnicas de alineación más precisas que las existentes. Este es el caso del Colisionador Lineal Compacto (Compact Linear Collider, CLIC), cuyos objetivos altamente restrictivos de alineamiento alcanzan los 10 um. Para poder lograr el máximo rendimiento del acelerador, es necesario que el posicionamiento de las estructuras que aceleran las partículas y de los campos que las guían cumplan las tolerancias de alineación para dirigir el haz a lo largo de la trayectoria diseñada. Dicho procedimiento consiste en relacionar la posición de los ejes de referencia de cada componente con respecto a objetos externos, o fiduciales, lo cual resulta muy tedioso y económicamente costoso. Los errores sistemáticos y aleatorios se van acumulando en cada paso del proceso y, en consecuencia, la precisión final de alineamiento es todo un desafío. En este contexto, nace el proyecto PACMAN (Particle Accelerator Components Metrology and Alignment to the Nanometre scale), subvencionado por la Unión Europea en el programa FP7 de financiación para la investigación e innovación. El objetivo principal de PACMAN es investigar, desarrollar e implementar una solución integrada alternativa que incorpore todos los pasos de alineación en una misma ubicación, con el objetivo de mejorar la precisión de alineación de los componentes de los aceleradores, en concreto: las estructuras aceleradoras, los cuadrupolos y los monitores de posición de haz. La viabilidad de las soluciones desarrolladas y la precisión de alineamiento alcanzada deben de demostrarse en un banco de pruebas utilizando componentes de CLIC. La estrategia de PACMAN para alcanzar el objetivo técnico se divide en tres pasos. El primero consiste en la fiducialización de los componentes y sus soportes. El segundo paso es el ensamblaje de los componentes en dos tipos de soporte, uno compuesto por un monitor de posición de haz y un cuadrupolo, y otro con cuatro estructuras aceleradoras, tomando como referencia su centro electromagnético. Finalmente, ambos soportes se transportan al túnel para su alineación final utilizando técnicas de hilos tensados. En esta tesis doctoral, se describe el desarrollo de una nueva técnica no destructiva para localizar los ejes electromagnéticos de estructuras aceleradoras y su validación experimental. Para ello, se ha utilizado una estructura aceleradora de CLIC conocida como TD24. Debido a la complejidad mecánica de la TD24, su difícil acceso y su diámetro medio de iris de 5.5 mm, se desarrolla una nueva técnica denominada en esta tesis como 'el método perturbativo' y se realiza una propuesta experimental de validación. El estudio de viabilidad de este método, cumpliendo con los requisitos impuestos de precisión en la medida de 10 um, ha sido realizado con una campaña extensa de simulaciones de campos electromagnéticos en tres dimensiones utilizando la herramienta de software conocida como HFSS. Los resultados de simulación han permitido el desarrollo de un algoritmo muy completo de medidas y han proporcionado las especificaciones técnicas para el diseño conceptual de un banco de pruebas para la medida de los ejes electromagnéticos de la TD24. El preciso ensamblaje del banco de pruebas y sus correspondientes calibraciones, la incorporación de nuevos tratamientos de las medidas en el algoritmo final y la caracterización de fuentes de error en la medida, favorecieron la localización del centro electromagnético en la TD24 con una precisión menor a 1 um con un error estimado menor que 8.5 um, cumplimiendo con los objetivos de precisión establecidos.
In the next generation of linear particle accelerators, challenging alignment tolerances are required in the positioning of the components focusing, accelerating and detecting the beam over the accelerator length in order to achieve the maximum machine performance. In the case of the Compact Linear Collider (CLIC), accelerating structures, beam position monitors and quadrupole magnets need to be aligned in their support with respect to their reference axes with an accuracy of 10 um. To reach such objective, the PACMAN (Particle Accelerator Components Metrology and Alignment to the Nanometer Scale) project strives for the improvement of the current alignment accuracy by developing new methods and tools, whose feasibility should be validated using the major CLIC components. This Ph.D. thesis concerns the investigation, development and implementation of a new non-destructive intracavity technique, referenced here as 'the perturbative method', to determine the electromagnetic axes of accelerating structures by means of a stretched wire, acting as a reference of alignment. Of particular importance is the experimental validation of the method through the 5.5 mm iris-mean aperture CLIC prototype known as TD24, with complex mechanical features and difficult accessibility, in a dedicated test bench. In the first chapter of this thesis, the alignment techniques in particle accelerators and the novel proposals to be implemented in the future linear colliders are introduced, and a detailed description of the PACMAN project is provided. The feasibility study of the method, carried out with extensive electromagnetic fields simulations, is described in chapter 2, giving as a result, the knowledge of the theoretical accuracy expected in the measurement of the electromagnetic axes and facilitating the development of a measurement algorithm. The conceptual design, manufacturing and calibration of the automated experimental set-up, integrating the solution developed to measure the electromagnetic axes of the TD24, are covered in chapter 3. The future lines of research and developments of the perturbative method are also explored. In chapter 4, the most significant results obtained from an extensive experimental work are presented, analysed and compared with simulations. The proof-of-principle is completed, the measurement algorithm is optimised and the electromagnetic centre is measured in the TD24 with a precision less than 1 um and an estimated error less than 8.5 um. Finally, in chapter 5, the developments undertaken along this research work are summarised, the innovative achievements accomplished within the PACMAN project are listed and its impact is analysed.
En la generació pròxima d'acceleradors de partícules lineals, desafiant toleràncies d'alineament és requerit en el posicionament dels components que enfoquen, accelerant i detectant la biga sobre la longitud d'accelerador per tal d'aconseguir l'actuació de màquina màxima. En el cas del Colisionador Compacte Lineal (CLIC), accelerant estructures, monitors de posició de fes i imants necessiten ser alineats en el seu suport amb respectar a les seves destrals de referència amb una precisió de 10 um. Per assolir tal objectiu, el PACMAN (Metrologia de Components de l'Accelerador de partícules i Alineament al Nanometer Escala) projecte s'esforça per la millora de l'actual precisió d'alineament per mètodes nous en desenvolupament i eines, la viabilitat dels quals hauria de ser validada utilitzant els components de CLIC importants. Aquesta tesi concerneix la investigació, desenvolupament i implementació d'un nou no-destructiu tècnica interna, va referenciar ací mentre 'el mètode de pertorbació' per determinar les destrals electromagnètiques d'accelerar estructures mitjançant un cable estès, actuant com a referència d'alineament. De la importància particular és la validació experimental del mètode a través del 5.5 mm iris-roí obertura prototipus de CLIC sabut com TD24, amb característiques mecàniques complexes i accessibilitat difícil, en un banc de prova dedicat. En el primer capítol d'aquesta tesi, les tècniques d'alineament en acceleradors de partícules i les propostes novelles per ser implementades en el futur colisionador lineal és introduït, i una descripció detallada del projecte PACMAN és proporcionat. L'estudi de viabilitat el mètode de pertorbació, va dur a terme amb simulacres de camps electromagnètics extensos, és descrit dins capitol 2, donant com a resultat, el coneixement de la precisió teòrica esperada en la mida de les destrals electromagnètiques i facilitant el desenvolupament d'un algoritme de mida. El disseny conceptual, fabricació i calibratge del conjunt experimental automatitzat-amunt, integrant la solució desenvolupada per mesurar les destrals electromagnètiques del TD24, és cobert dins capitol 3. Les línies futures de recerca i desenvolupaments del mètode és també va explorar. Dins capitol 4, la majoria de resultats significatius van obtenir d'una faena experimental extensa és presentada, analitzat i comparat amb simulacres. La prova-de-el principi és completat, l'algoritme de mida és optimitzat i el centre electromagnètic és mesurat en el TD24 amb una precisió menys d'1 um i un error calculat menys de 8.5 um. Finalment, dins capitol 5, els desenvolupaments empresos al llarg d'aquesta faena de recerca és resumit, les consecucions innovadores van acomplir dins del projecte PACMAN és llistat i el seu impacte és analitzat.
Galindo Muñoz, N. (2018). Development of direct measurement techniques for the in-situ internal alignment of accelerating structures [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/100488
TESIS

The aim of this thesis is to create an algorithm that allows the alignment of the genome of two organisms by means of suffix structures and to implement it into the programming language environment R. The thesis deals with the description of the construction of the suffix structures and the methods of whole genome alignment. The result of the thesis is a functional algorithm for whole genome alignment by means of suffix structures implemented in the software environment R and its comparison with similar programs for the whole genome alignment.

Aligning multiple biological sequences such as protein sequences or DNA/RNA sequences is a fundamental task in bioinformatics and sequence analysis. These alignments may contain invaluable information that scientists need to predict the sequences' structures, determine the evolutionary relationships between them, or discover drug-like compounds that can bind to the sequences. Unfortunately, multiple sequence alignment (MSA) is NP-Complete. In addition, the lack of a reliable scoring method makes it very hard to align the sequences reliably and to evaluate the alignment outcomes. In this dissertation, we have designed a new scoring method for use in multiple sequence alignment. Our scoring method encapsulates stereo-chemical properties of sequence residues and their substitution probabilities into a tree-structure scoring scheme. This new technique provides a reliable scoring scheme with low computational complexity. In addition to the new scoring scheme, we have designed an overlapping sequence clustering algorithm to use in our new three multiple sequence alignment algorithms. One of our alignment algorithms uses a dynamic weighted guidance tree to perform multiple sequence alignment in progressive fashion. The use of dynamic weighted tree allows errors in the early alignment stages to be corrected in the subsequence stages. Other two algorithms utilize sequence knowledge-bases and sequence consistency to produce biological meaningful sequence alignments. To improve the speed of the multiple sequence alignment, we have developed a parallel algorithm that can be deployed on reconfigurable computer models. Analytically, our parallel algorithm is the fastest progressive multiple sequence alignment algorithm.

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

Thesis advisor: Gabor T. Marth
Background: Due to the rapid development and application of next generation sequencing (NGS) techniques, large amounts of NGS data have become available for genome-related biological research, such as population genetics, evolutionary research, and genome wide association studies. A crucial step of these genome-related studies is the detection of genomic variation between different species and individuals. Current approaches for the detection of genomic variation can be classified into alignment-based variation detection and assembly-based variation detection. Due to the limitation of current NGS read length, alignment-based variation detection remains the mainstream approach. The Smith-Waterman algorithm, which produces the optimal pairwise alignment between two sequences, is frequently used as a key component of fast heuristic read mapping and variation detection tools for next-generation sequencing data. Though various fast Smith-Waterman implementations are developed, they are either designed as monolithic protein database searching tools, which do not return detailed alignment, or they are embedded into other tools. These issues make reusing these efficient Smith-Waterman implementations impractical. After the alignment step in the traditional variation detection pipeline, the afterward variation detection using pileup data and the Bayesian model is also facing great challenges especially from low-complexity genomic regions. Sequencing errors and misalignment problems still influence variation detection (especially INDEL detection) a lot. The accuracy of genomic variation detection still needs to be improved, especially when we work on low- complexity genomic regions and low-quality sequencing data. Results: To facilitate easy integration of the fast Single-Instruction-Multiple-Data Smith-Waterman algorithm into third-party software, we wrote a C/C++ library, which extends Farrar's Striped Smith-Waterman (SSW) to return alignment information in addition to the optimal Smith-Waterman score. In this library we developed a new method to generate the full optimal alignment results and a suboptimal score in linear space at little cost of efficiency. This improvement makes the fast Single-Instruction-Multiple-Data Smith-Waterman become really useful in genomic applications. SSW is available both as a C/C++ software library, as well as a stand-alone alignment tool at: https://github.com/mengyao/Complete- Striped-Smith-Waterman-Library. The SSW library has been used in the primary read mapping tool MOSAIK, the split-read mapping program SCISSORS, the MEI detector TAN- GRAM, and the read-overlap graph generation program RZMBLR. The speeds of the mentioned software are improved significantly by replacing their ordinary Smith-Waterman or banded Smith-Waterman module with the SSW Library. To improve the accuracy of genomic variation detection, especially in low-complexity genomic regions and on low-quality sequencing data, we developed PHV, a genomic variation detection tool based on the profile hidden Markov model. PHV also demonstrates a novel PHMM application in the genomic research field. The banded PHMM algorithms used in PHV make it a very fast whole-genome variation detection tool based on the HMM method. The comparison of PHV to GATK, Samtools and Freebayes for detecting variation from both simulated data and real data shows PHV has good potential for dealing with sequencing errors and misalignments. PHV also successfully detects a 49 bp long deletion that is totally misaligned by the mapping tool, and neglected by GATK and Samtools. Conclusion: The efforts made in this thesis are very meaningful for methodology development in studies of genomic variation detection. The two novel algorithms stated here will also inspire future work in NGS data analysis
Thesis (PhD) — Boston College, 2014
Submitted to: Boston College. Graduate School of Arts and Sciences
Discipline: Biology

2011 - 2012
Semantic interoperability represents the capability of two or more systems to meaningfully and accurately interpret the exchanged data so as to produce useful results. It is an essential feature of all distributed and open knowledge based systems designed for both e-government and private businesses, since it enables machine interpretation, inferencing and computable logic. Unfortunately, the task of achieving semantic interoperability is very difficult because it requires that the meanings of any data must be specified in an appropriate detail in order to resolve any potential ambiguity. Currently, the best technology recognized for achieving such level of precision in specification of meaning is represented by ontologies. According to the most frequently referenced definition [1], an ontology is an explicit specification of a conceptualization, i.e., the formal specification of the objects, concepts, and other entities that are presumed to exist in some area of interest and the relationships that hold them [2]. However, different tasks or different points of view lead ontology designers to produce different conceptualizations of the same domain of interest. This means that the subjectivity of the ontology modeling results in the creation of heterogeneous ontologies characterized by terminological and conceptual discrepancies. Examples of these discrepancies are the use of different words to name the same concept, the use of the same word to name different concepts, the creation of hierarchies for a specific domain region with different levels of detail and so on. The arising so-called semantic heterogeneity problem represents, in turn, an obstacle for achieving semantic interoperability... [edited by author]
XI n.s.

Methods for aproximate string matching of various sequences used in bioinformatics are crucial part of development in this branch. Tasks are of very large time complexity and therefore we want create a hardware platform for acceleration of these computations. Goal of this work is to design a generalized architecture based on FPGA technology, which can work with various types of sequences. Designed acceleration card will use especially dynamic algorithms like Needleman-Wunsch and Smith-Waterman.

This thesis deals with sequence alignment algorithms. The sequence alignment is a mutual arrange of two or more sequences in order to study their similarity and dissimilarity. Four decades after the seminal work by Needleman and Wunsch in 1970, these methods still need more explorations. We start out with a review of a sequence alignment, and its generalization to multiple alignments, although the focus of this thesis is on the evaluation of the new alignment algorithms. The research presented here in has stepped into the different algorithms that are in terms of the dynamic programming. In the study of sequence alignment algorithms, two powerful techniques have been invented. According to the simulations, the new algorithms are shown to be extremely efficient for the comparing DNA sequences. All the sequence alignment algorithmsare compared in terms of the distance. We use the programming language R for the implementation and simulation of the algorithms discussed in this thesis.

Transfer Alignment is the process of simultaneously initializing and calibrating a weapon inertial navigation system (INS) using data from host aircraft&rsquo
s navigation system. In general, this process is accomplished by calculating the difference of navigation solutions between aircraft and weapon INSs to form observations which are then used in a Kalman filter to generate desired estimates. Numerous techniques about the problem of transfer alignment exist in the literature. In this thesis, those techniques that can be applied in the presence of elastic motion of aircraft wing were analyzed. Several transfer alignment algorithms each of which process different measurement types were designed and implemented. In order to evaluate the performance of implemented algorithms under realistic conditions, a transfer alignment simulation environment was developed. Using this simulation environment, the advantages and disadvantages of each algorithm were analyzed and the dependence of transfer alignment performance on Kalman filter system model, aircraft maneuvers and alignment duration were investigated.

Real-time face recognition has recently become available for the government and industry due to developments in face recognition algorithms, human head detection algorithms, and faster/low cost computers. Despite these advances, however, there are still some critical issues that affect the performance of real-time face recognition software. This paper addresses the problem of off-centered and out-of-pose faces in pictures, particularly in regard to the eigenface method for face recognition. We first demonstrate how the representation of faces by the eigenface method, and ultimately the performance of the software depend on the location of the eyes in the pictures. The eigenface method for face recognition is described: specifically, the creation of a face basis using the singular value decomposition, the reduction of dimension, and the unique representation of faces in the basis. Two different approaches for aligning the eyes in images are presented. The first considers the rotation of images using the orthogonal Procrustes Problem. The second approach looks at locating features in images using energy-minimizing active contours. We then conclude with a simple and fast algorithm for locating faces in images. Future research is also discussed.
Master of Science

Bioinformatics and computational biology (BCB) is a rapidly developing multidisciplinary field which encompasses a wide range of domains, including genomic sequence alignments. It is a fundamental tool in molecular biology in searching for homology between sequences. Sequence alignments are currently gaining close attention due to their great impact on the quality aspects of life such as facilitating early disease diagnosis, identifying the characteristics of a newly discovered sequence, and drug engineering. With the vast growth of genomic data, searching for a sequence homology over huge databases (often measured in gigabytes) is unable to produce results within a realistic time, hence the need for acceleration. Since the exponential increase of biological databases as a result of the human genome project (HGP), supercomputers and other parallel architectures such as the special purpose Very Large Scale Integration (VLSI) chip, Graphic Processing Unit (GPUs) and Field Programmable Gate Arrays (FPGAs) have become popular acceleration platforms. Nevertheless, there are always trade-off between area, speed, power, cost, development time and reusability when selecting an acceleration platform. FPGAs generally offer more flexibility, higher performance and lower overheads. However, they suffer from a relatively low level programming model as compared with off-the-shelf microprocessors such as standard microprocessors and GPUs. Due to the aforementioned limitations, the need has arisen for optimized FPGA core implementations which are crucial for this technology to become viable in high performance computing (HPC). This research proposes the use of state-of-the-art reprogrammable system-on-chip technology on FPGAs to accelerate three widely-used sequence alignment algorithms; the Smith-Waterman with affine gap penalty algorithm, the profile hidden Markov model (HMM) algorithm and the Basic Local Alignment Search Tool (BLAST) algorithm. The three novel aspects of this research are firstly that the algorithms are designed and implemented in hardware, with each core achieving the highest performance compared to the state-of-the-art. Secondly, an efficient scheduling strategy based on the double buffering technique is adopted into the hardware architectures. Here, when the alignment matrix computation task is overlapped with the PE configuration in a folded systolic array, the overall throughput of the core is significantly increased. This is due to the bound PE configuration time and the parallel PE configuration approach irrespective of the number of PEs in a systolic array. In addition, the use of only two configuration elements in the PE optimizes hardware resources and enables the scalability of PE systolic arrays without relying on restricted onboard memory resources. Finally, a new performance metric is devised, which facilitates the effective comparison of design performance between different FPGA devices and families. The normalized performance indicator (speed-up per area per process technology) takes out advantages of the area and lithography technology of any FPGA resulting in fairer comparisons. The cores have been designed using Verilog HDL and prototyped on the Alpha Data ADM-XRC-5LX card with the Virtex-5 XC5VLX110-3FF1153 FPGA. The implementation results show that the proposed architectures achieved giga cell updates per second (GCUPS) performances of 26.8, 29.5 and 24.2 respectively for the acceleration of the Smith-Waterman with affine gap penalty algorithm, the profile HMM algorithm and the BLAST algorithm. In terms of speed-up improvements, comparisons were made on performance of the designed cores against their corresponding software and the reported FPGA implementations. In the case of comparison with equivalent software execution, acceleration of the optimal alignment algorithm in hardware yielded an average speed-up of 269x as compared to the SSEARCH 35 software. For the profile HMM-based sequence alignment, the designed core achieved speed-up of 103x and 8.3x against the HMMER 2.0 and the latest version of HMMER (version 3.0) respectively. On the other hand, the implementation of the gapped BLAST with the two-hit method in hardware achieved a greater than tenfold speed-up compared to the latest NCBI BLAST software. In terms of comparison against other reported FPGA implementations, the proposed normalized performance indicator was used to evaluate the designed architectures fairly. The results showed that the first architecture achieved more than 50 percent improvement, while acceleration of the profile HMM sequence alignment in hardware gained a normalized speed-up of 1.34. In the case of the gapped BLAST with the two-hit method, the designed core achieved 11x speed-up after taking out advantages of the Virtex-5 FPGA. In addition, further analysis was conducted in terms of cost and power performances; it was noted that, the core achieved 0.46 MCUPS per dollar spent and 958.1 MCUPS per watt. This shows that FPGAs can be an attractive platform for high performance computation with advantages of smaller area footprint as well as represent economic ‘green’ solution compared to the other acceleration platforms. Higher throughput can be achieved by redeploying the cores on newer, bigger and faster FPGAs with minimal design effort.

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998.
Includes bibliographical references (leaves 70-74).
by Amy Christina Gieffers.
M.Eng.

碩士
國立交通大學
資訊科學系
91
In bioinformatics, it is desired to compare differences by aligning two proteins structure or nucleotide sequences. Biologists then become aware of the relationship from structures to functions for proteins. The protein structure alignment provides biologists observing any two proteins’ relationships. In this thesis, we used the ICP algorithm proposed by Besl and McKay at 1992 on protein structure analysis. ICP algorithm iteratively minimizes the distance between two different protein structures and computes a transformation matrix. Finally an optimal transformation matrix is obtained to align two proteins. In this thesis, we also present methods to speed up computing time. The experiment data of this thesis are obtained from PDB (Protein Data Bank). As a result of experiments, we can analysis protein structures accurately and provide friendly interface for protein visualization.

碩士
國立臺灣科技大學
資訊工程系
101
Multiple sequence alignment is a wide range of applications in DNA and protein sequence analysis. Correct alignment result can help us to find conserved regions in each sequence in addition to observe the sequences similarity. Even as a basis for prediction of protein structure. Dynamic programming method purpose obtain the optimal solution and get more better alignment results generally in a variety of algorithms today. However, the execute time and required memory space become bottleneck in dynamic programming procedure of multiple sequence alignment. For this reason, we propose a concept of segmentation. We find out some cut position of input sequences by greedy method, and according to each cut point in each sequence, dividing them and get fragment sets. These fragments are aligned and combined by MSA algorithm, and the A* algorithm applied in adjustment and integration of each fragment aligned result. The purpose is to use the estimated function in A* search process to abandon unreasonable alignment, so we can obtain whole multiple sequence alignment finally. A * algorithm is suitable to solve the shortest path search problem. To find the optimal solution, through the design of appropriate heuristic function. Our proposed algorithm implement sequence cut, revise and combine method. It can be applied to both, global and local alignment problems compared with other alignment algorithm, and reduced memory space during dynamic programming procedure.

碩士
大同大學
資訊工程學系(所)
93
As we know, conventional genetic algorithms considered the fixed crossover and mutation rates during the evolution processes. Higher crossover or mutation rates may cause abrupt changes during converging processes. On the contrary, smaller rates may not be enough for population to diversify the solution space. There is no guarantee that the traditional mutation and crossover operations will result in better offspring. As a result, the conventional method has the drawback of slow convergent problem. In order to solve those problems, we present a modified genetic algorithm to overcome the slow convergent problem existed in traditional genetic algorithms. We introduce the new methods to adapt the crossover and mutation rates which in turn help expedite the evolution. In order to prevent the chromosomes from being deteriorated by the crossover and mutation operations, we take the elite preservation policy into account. As a result, we can guarantee the offspring will perform as least as good as their parent. We also get an adaptable mutation rate by the comparison between the better and the worse chromosomes. The crossover rates are also calculated by the sum of the fitness values of elitists. The modified operations are able to find the suitable rates. In case the after-crossover chromosomes are exactly the same, we just allow one of them surviving into the next generation. Therefore, we can avoid the results stuck at local optimum. Our proposed algorithm not only accelerates the convergent speed, but also improves the pattern matching degree. On the benefits of the rapid convergence, our proposed algorithm is very suitable to solve the optimization problems in many application domains. Moreover, to verify the effectiveness of the proposed model, we use the algorithm to solve the problems of the polynomial fitting and the gene sequence alignment. The experimental results demonstrate that our proposed algorithm is more efficient than traditional algorithms.

碩士
大同大學
資訊工程研究所
92
As we know, conventional genetic algorithms considered the fixed crossover and mutation rates during the evolution processes. Higher crossover or mutation rates may cause abrupt changes during converging processes. On the contrary, smaller rates may not be enough for population to diversify the solution space. There is no guarantee that the traditional mutation and crossover operations will result in better offspring. As a result, the conventional method has the drawback of slow convergent problem. In order to solve those problems, we present a modified genetic algorithm to overcome the slow convergent problem existed in traditional genetic algorithms. We introduce the new methods to adapt the crossover and mutation rates which in turn help expedite the evolution. In order to prevent the chromosomes from being deteriorated by the crossover and mutation operations, we take the elite preservation policy into account. As a result, we can guarantee the offspring will perform as least as good as their parent. We also get an adaptable mutation rate by the comparison between the better and the worse chromosomes. The crossover rates are also calculated by the sum of the fitness values of elitists. The modified operations are able to find the suitable rates. In case the after-crossover chromosomes are exactly the same, we just allow one of them surviving into the next generation. Therefore, we can avoid the results stuck at local optimum. Our proposed algorithm not only accelerates the convergent speed, but also improves the pattern matching degree. On the benefits of the rapid convergence, our proposed algorithm is very suitable to solve the optimization problems in many application domains. Moreover, to verify the effectiveness of the proposed model, we use the algorithm to solve the problems of the polynomial fitting and the gene sequence alignment. The experimental results demonstrate that our proposed algorithm is more efficient than traditional algorithms.