New algorithms for automated phylogenetic reconstruction using artificial intelligence and data mining techniques

Academic and industrial research in the late 90s have brought about an exponential explosion of DNA sequence data. Automated expert systems are being created to help biologists to extract patterns, trends and links from this ever-deepening ocean of information. Two such systems aimed on retrieving and subsequently utilizing phylogenetically relevant information have been developed in this dissertation, the major objective of which was to automate the often difficult and confusing phylogenetic reconstruction process. ^ Popular phylogenetic reconstruction methods, such as distance-based methods, attempt to find an optimal tree topology (that reflects the relationships among related sequences and their evolutionary history) by searching through the topology space. Various compromises between the fast (but incomplete) and exhaustive (but computationally prohibitive) search heuristics have been suggested. An intelligent compromise algorithm that relies on a flexible “beam” search principle from the Artificial Intelligence domain and uses the pre-computed local topology reliability information to adjust the beam search space continuously is described in the second chapter of this dissertation. ^ However, sometimes even a (virtually) complete distance-based method is inferior to the significantly more elaborate (and computationally expensive) maximum likelihood (ML) method. In fact, depending on the nature of the sequence data in question either method might prove to be superior. Therefore, it is difficult (even for an expert) to tell a priori which phylogenetic reconstruction method—distance-based, ML or maybe maximum parsimony (MP)—should be chosen for any particular data set. ^ A number of factors, often hidden, influence the performance of a method. For example, it is generally understood that for a phylogenetically “difficult” data set more sophisticated methods (e.g., ML) tend to be more effective and thus should be chosen. However, it is the interplay of many factors that one needs to consider in order to avoid choosing an inferior method (potentially a costly mistake, both in terms of computational expenses and in terms of reconstruction accuracy.) ^ Chapter III of this dissertation details a phylogenetic reconstruction expert system that selects a superior proper method automatically. It uses a classifier (a Decision Tree-inducing algorithm) to map a new data set to the proper phylogenetic reconstruction method. ^

Design and Optimization of Four-dimensional Cone-beam Computed Tomography in Image-guided Radiation Therapy

The influence of respiratory motion on patient anatomy poses a challenge to accurate radiation therapy, especially in lung cancer treatment. Modern radiation therapy planning uses models of tumor respiratory motion to account for target motion in targeting. The tumor motion model can be verified on a per-treatment session basis with four-dimensional cone-beam computed tomography (4D-CBCT), which acquires an image set of the dynamic target throughout the respiratory cycle during the therapy session. 4D-CBCT is undersampled if the scan time is too short. However, short scan time is desirable in clinical practice to reduce patient setup time. This dissertation presents the design and optimization of 4D-CBCT to reduce the impact of undersampling artifacts with short scan times. This work measures the impact of undersampling artifacts on the accuracy of target motion measurement under different sampling conditions and for various object sizes and motions. The results provide a minimum scan time such that the target tracking error is less than a specified tolerance. This work also presents new image reconstruction algorithms for reducing undersampling artifacts in undersampled datasets by taking advantage of the assumption that the relevant motion of interest is contained within a volume-of-interest (VOI). It is shown that the VOI-based reconstruction provides more accurate image intensity than standard reconstruction. The VOI-based reconstruction produced 43% fewer least-squares error inside the VOI and 84% fewer error throughout the image in a study designed to simulate target motion. The VOI-based reconstruction approach can reduce acquisition time and improve image quality in 4D-CBCT.

A matrix pencil approach to the existence of compactly supported reconstruction functions in average sampling

The aim of this work is to solve a question raised for average sampling in shift-invariant spaces by using the well-known matrix pencil theory. In many common situations in sampling theory, the available data are samples of some convolution operator acting on the function itself: this leads to the problem of average sampling, also known as generalized sampling. In this paper we deal with the existence of a sampling formula involving these samples and having reconstruction functions with compact support. Thus, low computational complexity is involved and truncation errors are avoided. In practice, it is accomplished by means of a FIR filter bank. An answer is given in the light of the generalized sampling theory by using the oversampling technique: more samples than strictly necessary are used. The original problem reduces to finding a polynomial left inverse of a polynomial matrix intimately related to the sampling problem which, for a suitable choice of the sampling period, becomes a matrix pencil. This matrix pencil approach allows us to obtain a practical method for computing the compactly supported reconstruction functions for the important case where the oversampling rate is minimum. Moreover, the optimality of the obtained solution is established.

Beyond filtered backprojection: a reconstruction software package for ion beam microtomography data

A new version of the TomoRebuild data reduction software package is presented, for the reconstruction of scanning transmission ion microscopy tomography (STIMT) and particle induced X-ray emission tomography (PIXET) images. First, we present a state of the art of the reconstruction codes available for ion beam microtomography. The algorithm proposed here brings several advantages. It is a portable, multi-platform code, designed in C++ with well-separated classes for easier use and evolution. Data reduction is separated in different steps and the intermediate results may be checked if necessary. Although no additional graphic library or numerical tool is required to run the program as a command line, a user friendly interface was designed in Java, as an ImageJ plugin. All experimental and reconstruction parameters may be entered either through this plugin or directly in text format files. A simple standard format is proposed for the input of experimental data. Optional graphic applications using the ROOT interface may be used separately to display and fit energy spectra. Regarding the reconstruction process, the filtered backprojection (FBP) algorithm, already present in the previous version of the code, was optimized so that it is about 10 times as fast. In addition, Maximum Likelihood Expectation Maximization (MLEM) and its accelerated version Ordered Subsets Expectation Maximization (OSEM) algorithms were implemented. A detailed user guide in English is available. A reconstruction example of experimental data from a biological sample is given. It shows the capability of the code to reduce noise in the sinograms and to deal with incomplete data, which puts a new perspective on tomography using low number of projections or limited angle.

Parallel implementation of image segmentation algorithms on a network of transputers

Image segmentation is one of the most computationally intensive operations in image processing and computer vision. This is because a large volume of data is involved and many different features have to be extracted from the image data. This thesis is concerned with the investigation of practical issues related to the implementation of several classes of image segmentation algorithms on parallel architectures. The Transputer is used as the basic building block of hardware architectures and Occam is used as the programming language. The segmentation methods chosen for implementation are convolution, for edge-based segmentation; the Split and Merge algorithm for segmenting non-textured regions; and the Granlund method for segmentation of textured images. Three different convolution methods have been implemented. The direct method of convolution, carried out in the spatial domain, uses the array architecture. The other two methods, based on convolution in the frequency domain, require the use of the two-dimensional Fourier transform. Parallel implementations of two different Fast Fourier Transform algorithms have been developed, incorporating original solutions. For the Row-Column method the array architecture has been adopted, and for the Vector-Radix method, the pyramid architecture. The texture segmentation algorithm, for which a system-level design is given, demonstrates a further application of the Vector-Radix Fourier transform. A novel concurrent version of the quad-tree based Split and Merge algorithm has been implemented on the pyramid architecture. The performance of the developed parallel implementations is analysed. Many of the obtained speed-up and efficiency measures show values close to their respective theoretical maxima. Where appropriate comparisons are drawn between different implementations. The thesis concludes with comments on general issues related to the use of the Transputer system as a development tool for image processing applications; and on the issues related to the engineering of concurrent image processing applications.

Advancing atomic nanolithography: cold atomic Cs beam exposure of alkanethiol self-assembled monolayers

We report the results of a study into the quality of functionalized surfaces for nanolithographic imaging. Self-assembled monolayer (SAM) coverage, subsequent post-etch pattern definition and minimum feature size all depend on the quality of the Au substrate used in atomic nanolithographic experiments. We find sputtered Au substrates yield much smoother surfaces and a higher density of {111} oriented grains than evaporated Au surfaces. A detailed study of the self-assembly mechanism using molecular resolution AFM and STM has shown that the monolayer is composed of domains with sizes typically of 5-25 nm, and multiple molecular domains can exist within one Au grain. Exposure of the SAM to an optically-cooled atomic Cs beam traversing a two-dimensional array of submicron material masks ans also standing wave optical masks allowed determination of the minimum average Cs dose (2 Cs atoms per SAM molecule) and the realization of < 50 nm structures. The SAM monolayer contains many non-uniformities such as pin-holes, domain boundaries and monoatomic depressions which are present in the Au surface prior to SAM adsorption. These imperfections limit the use of alkanethiols as a resist in atomic nanolithography experiments. These studies have allowed us to realize an Atom Pencil suitable for deposition of precision quantities of material at the microand nanoscale to an active surface.

Beam-energy Dependence Of The Directed Flow Of Protons, Antiprotons, And Pions In Au+au Collisions.

Rapidity-odd directed flow (v1) measurements for charged pions, protons, and antiprotons near midrapidity (y=0) are reported in sNN=7.7, 11.5, 19.6, 27, 39, 62.4, and 200 GeV Au+Au collisions as recorded by the STAR detector at the Relativistic Heavy Ion Collider. At intermediate impact parameters, the proton and net-proton slope parameter dv1/dy|y=0 shows a minimum between 11.5 and 19.6 GeV. In addition, the net-proton dv1/dy|y=0 changes sign twice between 7.7 and 39 GeV. The proton and net-proton results qualitatively resemble predictions of a hydrodynamic model with a first-order phase transition from hadronic matter to deconfined matter, and differ from hadronic transport calculations.

Beam-energy Dependence Of Charge Separation Along The Magnetic Field In Au+au Collisions At Rhic.

Local parity-odd domains are theorized to form inside a quark-gluon plasma which has been produced in high-energy heavy-ion collisions. The local parity-odd domains manifest themselves as charge separation along the magnetic field axis via the chiral magnetic effect. The experimental observation of charge separation has previously been reported for heavy-ion collisions at the top RHIC energies. In this Letter, we present the results of the beam-energy dependence of the charge correlations in Au+Au collisions at midrapidity for center-of-mass energies of 7.7, 11.5, 19.6, 27, 39, and 62.4 GeV from the STAR experiment. After background subtraction, the signal gradually reduces with decreased beam energy and tends to vanish by 7.7 GeV. This implies the dominance of hadronic interactions over partonic ones at lower collision energies.

Beam Energy Dependence Of Moments Of The Net-charge Multiplicity Distributions In Au+au Collisions At Rhic.

We report the first measurements of the moments--mean (M), variance (σ(2)), skewness (S), and kurtosis (κ)--of the net-charge multiplicity distributions at midrapidity in Au+Au collisions at seven energies, ranging from sqrt[sNN]=7.7 to 200 GeV, as a part of the Beam Energy Scan program at RHIC. The moments are related to the thermodynamic susceptibilities of net charge, and are sensitive to the location of the QCD critical point. We compare the products of the moments, σ(2)/M, Sσ, and κσ(2), with the expectations from Poisson and negative binomial distributions (NBDs). The Sσ values deviate from the Poisson baseline and are close to the NBD baseline, while the κσ(2) values tend to lie between the two. Within the present uncertainties, our data do not show nonmonotonic behavior as a function of collision energy. These measurements provide a valuable tool to extract the freeze-out parameters in heavy-ion collisions by comparing with theoretical models.

Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.

Abstract In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

Vertical Bone Measurements From Cone Beam Computed Tomography Images Using Different Software Packages.

This article aimed at comparing the accuracy of linear measurement tools of different commercial software packages. Eight fully edentulous dry mandibles were selected for this study. Incisor, canine, premolar, first molar and second molar regions were selected. Cone beam computed tomography (CBCT) images were obtained with i-CAT Next Generation. Linear bone measurements were performed by one observer on the cross-sectional images using three different software packages: XoranCat®, OnDemand3D® and KDIS3D®, all able to assess DICOM images. In addition, 25% of the sample was reevaluated for the purpose of reproducibility. The mandibles were sectioned to obtain the gold standard for each region. Intraclass coefficients (ICC) were calculated to examine the agreement between the two periods of evaluation; the one-way analysis of variance performed with the post-hoc Dunnett test was used to compare each of the software-derived measurements with the gold standard. The ICC values were excellent for all software packages. The least difference between the software-derived measurements and the gold standard was obtained with the OnDemand3D and KDIS3D (-0.11 and -0.14 mm, respectively), and the greatest, with the XoranCAT (+0.25 mm). However, there was no statistical significant difference between the measurements obtained with the different software packages and the gold standard (p> 0.05). In conclusion, linear bone measurements were not influenced by the software package used to reconstruct the image from CBCT DICOM data.

Reprodutibilidade das mensurações da espessura das tábuas ósseas na tomografia computadorizada Cone-Beam utilizando diferentes protocolos de aquisição de imagem

INTRODUÇÃO: quanto menor a dimensão do voxel, maior a nitidez da imagem de tomografia computadorizada Cone-Beam (TCCB), porém, maior a dose de radiação emitida. OBJETIVOS: avaliar e comparar a reprodutibilidade da mensuração da espessura das tábuas ósseas vestibular e lingual em imagens de TCCB, utilizando diferentes protocolos de aquisição de imagem com variação da dimensão do voxel. MÉTODOS: exames de TCCB foram tomados de 12 mandíbulas humanas secas, com dimensão do voxel de 0,2; 0,3 e 0,4mm, no aparelho i-CAT Cone-Beam 3-D Dental Imaging System. No software i-CAT Viewer, foi mensurada a espessura das tábuas ósseas vestibular e lingual, em um corte axial passando 12mm acima do forame mentoniano do lado direito. A reprodutibilidade intraexaminador foi avaliada por meio da aplicação do teste t pareado. Para a comparação interexaminadores, foi utilizado o teste t independente. Os resultados foram considerados com o nível de significância de 5%. RESULTADOS: observou-se uma excelente reprodutibilidade interexaminadores para os três protocolos avaliados. A reprodutibilidade intraexaminadores foi muito boa, com exceção de algumas regiões dos dentes anteriores, que mostraram diferenças estatisticamente significativas, independentemente da dimensão do voxel. CONCLUSÃO: a mensuração da espessura das tábuas ósseas vestibular e lingual em imagens de TCCB mostrou boa precisão para exames obtidos com voxel de 0,2; 0,3 ou 0,4mm. A reprodutibilidade das mensurações na região anterior da mandíbula foi mais crítica do que na região posterior.

Padronização de um método para mensuração das tábuas ósseas vestibular e lingual dos maxilares na Tomografia Computadorizada de Feixe Cônico (Cone Beam)

INTRODUÇÃO: a espessura das tábuas ósseas que recobrem os dentes por vestibular e lingual constitui um dos fatores limitantes da movimentação dentária. O avanço tecnológico em Imaginologia permitiu avaliar detalhadamente essas regiões anatômicas por meio da utilização da tomografia computadorizada de feixe cônico (TCFC). OBJETIVO: descrever e padronizar, pormenorizadamente, um método para mensuração das tábuas ósseas vestibular e lingual dos maxilares nas imagens de tomografia computadorizada de feixe cônico. METODOLOGIA: a padronização digital da posição da imagem da face deve constituir o primeiro passo antes da seleção dos cortes de TCFC. Dois cortes axiais de cada maxilar foram empregados para a mensuração da espessura do osso alveolar vestibular e lingual. Utilizou-se como referência a junção cemento-esmalte dos primeiros molares permanentes, tanto na arcada superior quanto na inferior. RESULTADOS: cortes axiais paralelos ao plano palatino foram indicados para avaliação quantitativa do osso alveolar na maxila. Na arcada inferior, os cortes axiais devem ser paralelos ao plano oclusal funcional. CONCLUSÃO: o método descrito apresenta reprodutibilidade para utilização em pesquisas, assim como para a avaliação clínica das repercussões periodontais da movimentação dentária, ao permitir a comparação de imagens pré e pós-tratamento.

Influence of intracanal post on apical periodontitis identified by cone-beam computed tomography

The determination of the success of endodontic treatment has been often discussed based on outcome obtained by periapical radiography. The aim of this study was to verify the influence of intracanal post on apical periodontitis detected by cone-beam computed tomography (CBCT). A consecutive sample of 1020 images (periapical radiographs and CBCT scans) taken from 619 patients (245 men; mean age, 50.1 years) between February 2008 and September 2009 were used in this study. Presence and intracanal post length (short, medium and long) were associated with apical periodontitis (AP). Chi-square test was used for statistical analyses. Significance level was set at p<0.01. The kappa value was used to assess examiner variability. From a total of 591 intracanal posts, AP was observed in 15.06%, 18.78% and 7.95% using periapical radiographs, into the different lengths, short, medium and long, respectively (p=0.466). Considering the same posts length it was verified AP in 24.20%, 26.40% and 11.84% observed by CBCT scans, respectively (p=0.154). From a total of 1,020 teeth used in this study, AP was detected in 397 (38.92%) by periapical radiography and in 614 (60.19%) by CBCT scans (p<0.001). The distribution of intracanal posts in different dental groups showed higher prevalence in maxillary anterior teeth (54.79%). Intracanal posts lengths did not influenced AP. AP was detected more frequently when CBCT method was used.

Method for determination of root curvature radius using cone-beam computed tomography images

This article describes and discusses a method to determine root curvature radius by using cone-beam computed tomography (CBCT). The severity of root canal curvature is essential to select instrument and instrumentation technique. The diagnosis and planning of root canal treatment have traditionally been made based on periapical radiography. However, the higher accuracy of CBCT images to identify anatomic and pathologic alterations compared to panoramic and periapical radiographs has been shown to reduce the incidence of false-negative results. In high-resolution images, the measurement of root curvature radius can be obtained by circumcenter. Based on 3 mathematical points determined with the working tools of Planimp® software, it is possible to calculate root curvature radius in both apical and coronal directions. The CBCT-aided method for determination of root curvature radius presented in this article is easy to perform, reproducible and allows a more reliable and predictable endodontic planning, which reflects directly on a more efficacious preparation of curved root canals.