Estimating and evaluating the statistics of gapped local-alignment scores

We present a novel maximum-likelihood-based algorithm for estimating the distribution of alignment scores from the scores of unrelated sequences in a database search. Using a new method for measuring the accuracy of p-values, we show that our maximum-likelihood-based algorithm is more accurate than existing regression-based and lookup table methods. We explore a more sophisticated way of modeling and estimating the score distributions (using a two-component mixture model and expectation maximization), but conclude that this does not improve significantly over simply ignoring scores with small E-values during estimation. Finally, we measure the classification accuracy of p-values estimated in different ways and observe that inaccurate p-values can, somewhat paradoxically, lead to higher classification accuracy. We explain this paradox and argue that statistical accuracy, not classification accuracy, should be the primary criterion in comparisons of similarity search methods that return p-values that adjust for target sequence length.

Chroma binary similarity and local alignment applied to cover song identification

We present a new technique for audio signal comparison based on tonal subsequence alignment and its application to detect cover versions (i.e., different performances of the same underlying musical piece). Cover song identification is a task whose popularity has increased in the Music Information Retrieval (MIR) community along in the past, as it provides a direct and objective way to evaluate music similarity algorithms.This article first presents a series of experiments carried outwith two state-of-the-art methods for cover song identification.We have studied several components of these (such as chroma resolution and similarity, transposition, beat tracking or Dynamic Time Warping constraints), in order to discover which characteristics would be desirable for a competitive cover song identifier. After analyzing many cross-validated results, the importance of these characteristics is discussed, and the best-performing ones are finally applied to the newly proposed method. Multipleevaluations of this one confirm a large increase in identificationaccuracy when comparing it with alternative state-of-the-artapproaches.

Local alignment refinement using structural assessment.

Homology modeling is the most commonly used technique to build a three-dimensional model for a protein sequence. It heavily relies on the quality of the sequence alignment between the protein to model and related proteins with a known three dimensional structure. Alignment quality can be assessed according to the physico-chemical properties of the three dimensional models it produces.In this work, we introduce fifteen predictors designed to evaluate the properties of the models obtained for various alignments. They consist of an energy value obtained from different force fields (CHARMM, ProsaII or ANOLEA) computed on residue selected around misaligned regions. These predictors were evaluated on ten challenging test cases. For each target, all possible ungapped alignments are generated and their corresponding models are computed and evaluated.The best predictor, retrieving the structural alignment for 9 out of 10 test cases, is based on the ANOLEA atomistic mean force potential and takes into account residues around misaligned secondary structure elements. The performance of the other predictors is significantly lower. This work shows that substantial improvement in local alignments can be obtained by careful assessment of the local structure of the resulting models.

The estimation of statistical parameters for local alignment score distributions

The distribution of optimal local alignment scores of random sequences plays a vital role in evaluating the statistical significance of sequence alignments. These scores can be well described by an extreme-value distribution. The distribution’s parameters depend upon the scoring system employed and the random letter frequencies; in general they cannot be derived analytically, but must be estimated by curve fitting. For obtaining accurate parameter estimates, a form of the recently described ‘island’ method has several advantages. We describe this method in detail, and use it to investigate the functional dependence of these parameters on finite-length edge effects.

Efficient subsequence alignment of time series

Zeitreihen sind allgegenwärtig. Die Erfassung und Verarbeitung kontinuierlich gemessener Daten ist in allen Bereichen der Naturwissenschaften, Medizin und Finanzwelt vertreten. Das enorme Anwachsen aufgezeichneter Datenmengen, sei es durch automatisierte Monitoring-Systeme oder integrierte Sensoren, bedarf außerordentlich schneller Algorithmen in Theorie und Praxis. Infolgedessen beschäftigt sich diese Arbeit mit der effizienten Berechnung von Teilsequenzalignments. Komplexe Algorithmen wie z.B. Anomaliedetektion, Motivfabfrage oder die unüberwachte Extraktion von prototypischen Bausteinen in Zeitreihen machen exzessiven Gebrauch von diesen Alignments. Darin begründet sich der Bedarf nach schnellen Implementierungen. Diese Arbeit untergliedert sich in drei Ansätze, die sich dieser Herausforderung widmen. Das umfasst vier Alignierungsalgorithmen und ihre Parallelisierung auf CUDA-fähiger Hardware, einen Algorithmus zur Segmentierung von Datenströmen und eine einheitliche Behandlung von Liegruppen-wertigen Zeitreihen.rnrnDer erste Beitrag ist eine vollständige CUDA-Portierung der UCR-Suite, die weltführende Implementierung von Teilsequenzalignierung. Das umfasst ein neues Berechnungsschema zur Ermittlung lokaler Alignierungsgüten unter Verwendung z-normierten euklidischen Abstands, welches auf jeder parallelen Hardware mit Unterstützung für schnelle Fouriertransformation einsetzbar ist. Des Weiteren geben wir eine SIMT-verträgliche Umsetzung der Lower-Bound-Kaskade der UCR-Suite zur effizienten Berechnung lokaler Alignierungsgüten unter Dynamic Time Warping an. Beide CUDA-Implementierungen ermöglichen eine um ein bis zwei Größenordnungen schnellere Berechnung als etablierte Methoden.rnrnAls zweites untersuchen wir zwei Linearzeit-Approximierungen für das elastische Alignment von Teilsequenzen. Auf der einen Seite behandeln wir ein SIMT-verträgliches Relaxierungschema für Greedy DTW und seine effiziente CUDA-Parallelisierung. Auf der anderen Seite führen wir ein neues lokales Abstandsmaß ein, den Gliding Elastic Match (GEM), welches mit der gleichen asymptotischen Zeitkomplexität wie Greedy DTW berechnet werden kann, jedoch eine vollständige Relaxierung der Penalty-Matrix bietet. Weitere Verbesserungen umfassen Invarianz gegen Trends auf der Messachse und uniforme Skalierung auf der Zeitachse. Des Weiteren wird eine Erweiterung von GEM zur Multi-Shape-Segmentierung diskutiert und auf Bewegungsdaten evaluiert. Beide CUDA-Parallelisierung verzeichnen Laufzeitverbesserungen um bis zu zwei Größenordnungen.rnrnDie Behandlung von Zeitreihen beschränkt sich in der Literatur in der Regel auf reellwertige Messdaten. Der dritte Beitrag umfasst eine einheitliche Methode zur Behandlung von Liegruppen-wertigen Zeitreihen. Darauf aufbauend werden Distanzmaße auf der Rotationsgruppe SO(3) und auf der euklidischen Gruppe SE(3) behandelt. Des Weiteren werden speichereffiziente Darstellungen und gruppenkompatible Erweiterungen elastischer Maße diskutiert.

Genome Survey Sequence Analysis and Identification of Homologs of Major Surface Protease (gp63) Genes in Trypanosoma rangeli

In this study, 222 genome survey sequences were generated for Trypanosoma rangeli strain P07 isolated from an opossum (Didelphis albiventris) in Minas Gerais State, Brazil. T. rangeli sequences were compared by BLASTX (Basic Local Alignment Search Tool X) analysis with the assembled contigs of Leishmania braziliensis, Leishmania infantum, Leishmania major, Trypanosoma brucei, and Trypanosoma cruzi. Results revealed that 82% (182/222) of the sequences were associated with predicted proteins described, whereas 18% (40/222) of the sequences did not show significant identity with sequences deposited in databases, suggesting that they may represent T. rangeli-specific sequences. Among the 182 predicted sequences, 179 (80.6%) had the highest similarity with T. cruzi, 2 (0.9%) with T. brucei, and 1 (0.5%) with L. braziliensis. Computer analysis permitted the identification of members of various gene families described for trypanosomatids in the genome of T. rangeli, such as trans-sialidases, mucin-associated surface proteins, and major surface proteases (MSP or gp63). This is the first report identifying sequences of the MSP family in T. rangeli. Multiple sequence alignments showed that the predicted MSP of T. rangeli presented the typical characteristics of metalloproteases, such as the presence of the HEXXH motif, which corresponds to a region previously associated with the catalytic site of the enzyme, and various cysteine and proline residues, which are conserved among MSPs of different trypanosomatid species. Reverse transcriptase-polymerase chain reaction analysis revealed the presence of MSP transcripts in epimastigote forms of T. rangeli.

Protective immunity induced in mice by F8.1 and F8.2 antigens purified from Schistosoma mansoni eggs

Schistosoma mansoni soluble egg antigens (SEA) were fractionated by isoelectric focusing, resulting in 20 components, characterized by pH, absorbance and protein concentration. The higher absorbance fractions were submitted to electrophoresis, and fraction 8 (F8) presented a specific pattern of bands on its isoelectric point. Protein 3 was observed only on F8, and so, it was utilized to rabbit immunization, in order to evaluate its capacity of inducing protective immunity. IgG antibodies from rabbit anti-F8 serum were coupled to Sepharose, and used to obtain the specific antigen by affinity chromatography. This antigen, submitted to electrophoresis, presented two proteic bands (F8.1 and F8.2), which were transferred to nitrocellulose membrane (PVDF) and sequenciated. The homology of F8.2 to known proteins was determined using the Basic Local Alignment Search Tool program (BLASTp). Significant homologies were obtained for the rabbit cytosolic Ca2+ uptake inhibitor, and for the bird a1-proteinase inhibitor. Immunization of mice with F8.1 and F8.2, in the presence of Corynebacterium parvum and Al(OH)3 as adjuvant, induced a significant protection degree against challenge infection, as observed by the decrease on worm burden recovered from portal system.

Caracterização de rizóbios indicados para produção de inoculantes por meio de sequenciamento parcial do 16S rRNA

O objetivo deste trabalho foi confrontar as sequências parciais do gene 16S rRNA de estirpes padrão de rizóbios com as de estirpes recomendadas para a produção de inoculantes no Brasil, com vistas à verificação da confiabilidade do sequenciamento parcial desse gene para a identificação rápida de estirpes. Foram realizados sequenciamentos através de reação em cadeia da polimerase (PCR) com iniciadores relativos à região codificadora do gene 16S rRNA entre as bactérias estudadas. Os resultados foram analisados pela consulta de similaridade de nucleotídeos aos do "Basic Local Alignment Search Tool" (Blastn) e por meio da interpretação de árvores filogenéticas geradas usando ferramentas de bioinformática. A classificação taxonômica das estirpes Semia recomendadas para inoculação de leguminosas com base em propriedades morfológicas e especificidade hospedeira não foi confirmada em todas as estirpes. A maioria das estirpes estudadas, consultadas no Blastn, é consistente com a classificação proposta pela construção de árvores filogenéticas das sequências destas estirpes, com base na similaridade pelo sequenciamento parcial do gene considerado.

Contamination of genomic databases by HIV-1 and its possible consequences. A study in Bioinformatics.

Peer-reviewed

A proposal to estimate the motion of an underwater vehicle through visual mosaicking

This thesis proposes a solution to the problem of estimating the motion of an Unmanned Underwater Vehicle (UUV). Our approach is based on the integration of the incremental measurements which are provided by a vision system. When the vehicle is close to the underwater terrain, it constructs a visual map (so called "mosaic") of the area where the mission takes place while, at the same time, it localizes itself on this map, following the Concurrent Mapping and Localization strategy. The proposed methodology to achieve this goal is based on a feature-based mosaicking algorithm. A down-looking camera is attached to the underwater vehicle. As the vehicle moves, a sequence of images of the sea-floor is acquired by the camera. For every image of the sequence, a set of characteristic features is detected by means of a corner detector. Then, their correspondences are found in the next image of the sequence. Solving the correspondence problem in an accurate and reliable way is a difficult task in computer vision. We consider different alternatives to solve this problem by introducing a detailed analysis of the textural characteristics of the image. This is done in two phases: first comparing different texture operators individually, and next selecting those that best characterize the point/matching pair and using them together to obtain a more robust characterization. Various alternatives are also studied to merge the information provided by the individual texture operators. Finally, the best approach in terms of robustness and efficiency is proposed. After the correspondences have been solved, for every pair of consecutive images we obtain a list of image features in the first image and their matchings in the next frame. Our aim is now to recover the apparent motion of the camera from these features. Although an accurate texture analysis is devoted to the matching pro-cedure, some false matches (known as outliers) could still appear among the right correspon-dences. For this reason, a robust estimation technique is used to estimate the planar transformation (homography) which explains the dominant motion of the image. Next, this homography is used to warp the processed image to the common mosaic frame, constructing a composite image formed by every frame of the sequence. With the aim of estimating the position of the vehicle as the mosaic is being constructed, the 3D motion of the vehicle can be computed from the measurements obtained by a sonar altimeter and the incremental motion computed from the homography. Unfortunately, as the mosaic increases in size, image local alignment errors increase the inaccuracies associated to the position of the vehicle. Occasionally, the trajectory described by the vehicle may cross over itself. In this situation new information is available, and the system can readjust the position estimates. Our proposal consists not only in localizing the vehicle, but also in readjusting the trajectory described by the vehicle when crossover information is obtained. This is achieved by implementing an Augmented State Kalman Filter (ASKF). Kalman filtering appears as an adequate framework to deal with position estimates and their associated covariances. Finally, some experimental results are shown. A laboratory setup has been used to analyze and evaluate the accuracy of the mosaicking system. This setup enables a quantitative measurement of the accumulated errors of the mosaics created in the lab. Then, the results obtained from real sea trials using the URIS underwater vehicle are shown.

Hydrogelation and self-assembly of Fmoc-tripeptides: unexpected influence of sequence on self-assembled fibril structure, and hydrogel modulus and anisotropy

The self-assembly and hydrogelation properties of two Fmoc-tripeptides [Fmoc = N-(fluorenyl-9-methoxycarbonyl)] are investigated, in borate buffer and other basic solutions. A remarkable difference in self-assembly properties is observed comparing Fmoc-VLK(Boc) with Fmoc-K(Boc)LV, both containing K protected by N(epsilon)-tert-butyloxycarbonate (Boc). In borate buffer, the former peptide forms highly anisotropic fibrils which show local alignment, and the hydrogels show flow-aligning properties. In contrast, Fmoc-K(Boc)LV forms highly branched fibrils that produce isotropic hydrogels with a much higher modulus (G' > 10(4) Pa), and lower concentration for hydrogel formation. The distinct self-assembled structures are ascribed to conformational differences, as revealed by secondary structure probes (CD, FTIR, Raman spectroscopy) and X-ray diffraction. Fmoc-VLK(Boc) forms well-defined beta-sheets with a cross-beta X-ray diffraction pattern, whereas Fmoc-KLV(Boc) forms unoriented assemblies with multiple stacked sheets. Interchange of the K and V residues when inverting the tripeptide sequence thus leads to substantial differences in self-assembled structures, suggesting a promising approach to control hydrogel properties.

Caracterização de rizóbios indicados para produção de inoculantes por meio de sequenciamento parcial do 16S rRNA

O objetivo deste trabalho foi confrontar as sequências parciais do gene 16S rRNA de estirpes padrão de rizóbios com as de estirpes recomendadas para a produção de inoculantes no Brasil, com vistas à verificação da confiabilidade do sequenciamento parcial desse gene para a identificação rápida de estirpes. Foram realizados sequenciamentos através de reação em cadeia da polimerase (PCR) com iniciadores relativos à região codificadora do gene 16S rRNA entre as bactérias estudadas. Os resultados foram analisados pela consulta de similaridade de nucleotídeos aos do Basic Local Alignment Search Tool (Blastn) e por meio da interpretação de árvores filogenéticas geradas usando ferramentas de bioinformática. A classificação taxonômica das estirpes Semia recomendadas para inoculação de leguminosas com base em propriedades morfológicas e especificidade hospedeira não foi confirmada em todas as estirpes. A maioria das estirpes estudadas, consultadas no Blastn, é consistente com a classificação proposta pela construção de árvores filogenéticas das sequências destas estirpes, com base na similaridade pelo sequenciamento parcial do gene considerado.

Phylogeny of Celastraceae Subfamily Salacioideae and Tribe Lophopetaleae Inferred from Morphological Characters and Nuclear and Plastid Genes

The phylogeny of Celastraceae subfamily Salacioideae (ca. 255 species in the Old and New World tropics) and tribe Lophopetaleae (ca. 29 species in southern Asia and the Austral-Pacific) was inferred using morphological characters together with plastid (matK, trnL-F) and nuclear (ITS and 26S rDNA) genes. Brassiantha, a monotypic genus endemic to New Guinea, is inferred to be more closely related to the clade of Dicarpellum (New Caledonia) and Hypsophila (Queensland, Australia) than it is to Hippocrateoideae or Salacioideae. This unambiguously supported resolution indicates that a nectary disk positioned outside the stamens has been convergently derived in these two lineages. The clade of Kokoona and Lophopetalum is resolved as more closely related to Breria and Elaeodendron than it is to Hippocrateoideae or Salacioideae. Sarawakodendron, a monotypic genus endemic to Borneo, is resolved as sister to Salacioideae. Salacioideae are inferred to have an Old World origin that was followed by a single successful radiation within Central and South America. We infer that capsular fruits are primitive within the clade of Hippocrateoideae + Sarawakodendron + Salacioideae, with berries a synapomorphy for Salacioideae. Based on the resolution of Sarawakodendron as sister to Salacioideae, we hypothesize that the filaments of Sarawakodendron arils are homologous to the spiral filaments in the mucilagenous pulp of Salacioideae.

Assessment of a quantitative 5' nuclease real-time polymerase chain reaction using the nicotinamide adenine dinucleotide dehydrogenase gamma subunit (nuoG) for Bartonella species in domiciled and stray cats in Brazil

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Molecular identification of food sources in triatomines in the Brazilian northeast: roles of goats and rodents in Chagas disease epidemiology

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)