Using Markov chains and temporal alignment to identify clinical patterns in Dementia.

In the healthcare sector, resorting to big data and advanced analytics is a great advantage when dealing with complex groups of patients in terms of comorbidities, representing a significant step towards personalized targeting. In this work, we focus on understanding key features and clinical pathways of patients with multimorbidity suffering from Dementia. This disease can result from many heterogeneous factors, potentially becoming more prevalent as the population ages. We present a set of methods that allow us to identify medical appointment patterns within a cohort of 1924 patients followed from January 2007 to August 2021 in Hospital da Luz (Lisbon), and to stratify patients into subgroups that exhibit similar patterns of interaction. With Markov Chains, we are able to identify the most prevailing medical appointments attended by Dementia patients, as well as recurring transitions between these. To perform patient stratification, we applied AliClu, a temporal sequence alignment algorithm for clustering longitudinal clinical data, which allowed us to successfully identify patient subgroups with similar medical appointment activity. A feature analysis per cluster obtained allows the identification of distinct patterns and characteristics. This pipeline provides a tool to identify prevailing clinical pathways of medical appointments within the dataset, as well as the most common transitions between medical specialities within Dementia patients. This methodology, alongside demographic and clinical data, has the potential to provide early signalling of the most likely clinical pathways and serve as a support tool for health providers in deciding the best course of treatment, considering a patient as a whole.

Zgli: A Pipeline for Clustering by Compression with Application to Patient Stratification in Spondyloarthritis.

The normalized compression distance (NCD) is a similarity measure between a pair of finite objects based on compression. Clustering methods usually use distances (e.g., Euclidean distance, Manhattan distance) to measure the similarity between objects. The NCD is yet another distance with particular characteristics that can be used to build the starting distance matrix for methods such as hierarchical clustering or K-medoids. In this work, we propose Zgli, a novel Python module that enables the user to compute the NCD between files inside a given folder. Inspired by the CompLearn Linux command line tool, this module iterates on it by providing new text file compressors, a new compression-by-column option for tabular data, such as CSV files, and an encoder for small files made up of categorical data. Our results demonstrate that compression by column can yield better results than previous methods in the literature when clustering tabular data. Additionally, the categorical encoder shows that it can augment categorical data, allowing the use of the NCD for new data types. One of the advantages is that using this new feature does not require knowledge or context of the data. Furthermore, the fact that the new proposed module is written in Python, one of the most popular programming languages for machine learning, potentiates its use by developers to tackle problems with a new approach based on compression. This pipeline was tested in clinical data and proved a promising computational strategy by providing patient stratification via clusters aiding in precision medicine.

Dynamic Bayesian networks for stratification of disease progression in amyotrophic lateral sclerosis.

BACKGROUND AND PURPOSE: Progression rate is quite variable in amyotrophic lateral sclerosis (ALS); thus, tools for profiling disease progression are essential for timely interventions. The objective was to apply dynamic Bayesian networks (DBNs) to establish the influence of clinical and demographic variables on disease progression rate. METHODS: In all, 664 ALS patients from our database were included stratified into slow (SP), average (AP) and fast (FP) progressors, according to the Amyotrophic Lateral Sclerosis Functional Rating Scale Revised (ALSFRS-R) rate of decay. The sdtDBN framework was used, a machine learning model which learnt optimal DBNs with both static (gender, age at onset, onset region, body mass index, disease duration at entry, familial history, revised El Escorial criteria and C9orf72) and dynamic (ALSFRS-R scores and sub-scores, forced vital capacity, maximum inspiratory pressure, maximum expiratory pressure and phrenic amplitude) variables. RESULTS: Disease duration and body mass index at diagnosis are the foremost influences amongst static variables. Disease duration is the variable that better discriminates the three groups. Maximum expiratory pressure is the respiratory test with prevalent influence on all groups. ALSFRS score has a higher influence on FP, but lower on AP and SP. The bulbar sub-score has considerable influence on FP but limited on SP. Limb function has a more decisive influence on AP and SP. The respiratory sub-score has little influence in all groups. ALSFRS-R questions 1 (speech) and 9 (climbing stairs) are the most influential in FP and SP, respectively. CONCLUSIONS: The sdtDBN analysis identified five variables, easily obtained during clinical evaluation, which are the most influential for each progression group. This insightful information may help to improve prognosis and care.

Transfer of Metal(loid)s from Soil to Leaves and Trunk Xylem Sap of Medicinal Plants and Possible Health Risk Assessment.

The objective of the present study was to investigate metal(loid)s in soils, in the trunk xylem sap and in the leaves of the Dipteryx alata plant located near the highway with high vehicle traffic in agricultural regions and near landfills, and to assess the transfer of metal(loid)s from soil to plant and possible health risk assessment. Trunk xylem sap, leaves and soil samples were collected at three sites near the highway. The analysis of trace elements was carried out using inductively coupled plasma optical emission spectroscopy (ICP OES). In the three soil sampling sites far from the highway edge, 15 elements were quantified. The concentrations of elements in the soil presented in greater proportions in the distance of 5 m in relation to 20 and 35 m. The metal(loid)s content in the study soil was higher than in other countries. The concentrations of Al, Cu, Fe, Mg, Mn, P, Se and Zn in the xylem sap were much higher than the leaves. The values of transfer factor of P, Mg and Mn from soil to the xylem sap and transfer factor of P from soil to leaf were greater than 1, indicating that the specie have a significant phytoremediation and phytoextraction potential. This plant has a tendency to accumulate As, Cd and Cr in its leaf tissues. The chronic hazard index (HI) values recorded in this study were above 1 for adults and adolescents. It is concluded that the soil, the trunk xylem sap and leaves of this plant are contaminated by heavy metals. Ingestion of the trunk xylem sap of this plant can cause toxicity in humans if ingested in large quantities and in the long term; therefore, its consumption should be avoided.

Predicting Biologic Therapy Outcome of Patients With Spondyloarthritis: Joint Models for Longitudinal and Survival Analysis.

BACKGROUND: Rheumatic diseases are one of the most common chronic diseases worldwide. Among them, spondyloarthritis (SpA) is a group of highly debilitating diseases, with an early onset age, which significantly impacts patients' quality of life, health care systems, and society in general. Recent treatment options consist of using biologic therapies, and establishing the most beneficial option according to the patients' characteristics is a challenge that needs to be overcome. Meanwhile, the emerging availability of electronic medical records has made necessary the development of methods that can extract insightful information while handling all the challenges of dealing with complex, real-world data. OBJECTIVE: The aim of this study was to achieve a better understanding of SpA patients' therapy responses and identify the predictors that affect them, thereby enabling the prognosis of therapy success or failure. METHODS: A data mining approach based on joint models for the survival analysis of the biologic therapy failure is proposed, which considers the information of both baseline and time-varying variables extracted from the electronic medical records of SpA patients from the database, Reuma.pt. RESULTS: Our results show that being a male, starting biologic therapy at an older age, having a larger time interval between disease start and initiation of the first biologic drug, and being human leukocyte antigen (HLA)-B27 positive are indicators of a good prognosis for the biological drug survival; meanwhile, having disease onset or biologic therapy initiation occur in more recent years, a larger number of education years, and higher values of C-reactive protein or Bath Ankylosing Spondylitis Functional Index (BASFI) at baseline are all predictors of a greater risk of failure of the first biologic therapy. CONCLUSIONS: Among this Portuguese subpopulation of SpA patients, those who were male, HLA-B27 positive, and with a later biologic therapy starting date or a larger time interval between disease start and initiation of the first biologic therapy showed longer therapy adherence. Joint models proved to be a valuable tool for the analysis of electronic medical records in the field of rheumatic diseases and may allow for the identification of potential predictors of biologic therapy failure.

Coupling sparse Cox models with clustering of longitudinal transcriptomics data for trauma prognosis.

BACKGROUND: Longitudinal gene expression analysis and survival modeling have been proved to add valuable biological and clinical knowledge. This study proposes a novel framework to discover gene signatures and patterns in a high-dimensional time series transcriptomics data and to assess their association with hospital length of stay. METHODS: We investigated a longitudinal and high-dimensional gene expression dataset from 168 blunt-force trauma patients followed during the first 28 days after injury. To model the length of stay, an initial dimensionality reduction step was performed by applying Cox regression with elastic net regularization using gene expression data from the first hospitalization days. Also, a novel methodology to impute missing values to the genes selected previously was proposed. We then applied multivariate time series (MTS) clustering to analyse gene expression over time and to stratify patients with similar trajectories. The validation of the patients' partitions obtained by MTS clustering was performed using Kaplan-Meier curves and log-rank tests. RESULTS: We were able to unravel 22 genes strongly associated with hospital's discharge. Their expression values in the first days after trauma showed to be good predictors of the length of stay. The proposed mixed imputation method allowed to achieve a complete dataset of short time series with a minimum loss of information for the 28 days of follow-up. MTS clustering enabled to group patients with similar genes trajectories and, notably, with similar discharge days from the hospital. Patients within each cluster have comparable genes' trajectories and may have an analogous response to injury. CONCLUSION: The proposed framework was able to tackle the joint analysis of time-to-event information with longitudinal multivariate high-dimensional data. The application to length of stay and transcriptomics data revealed a strong relationship between gene expression trajectory and patients' recovery, which may improve trauma patient's management by healthcare systems. The proposed methodology can be easily adapted to other medical data, towards more effective clinical decision support systems for health applications.

Learning dynamic Bayesian networks from time-dependent and time-independent data: Unraveling disease progression in Amyotrophic Lateral Sclerosis.

Amyotrophic lateral sclerosis (ALS) is a neurodegenerative disease causing patients to quickly lose motor neurons. The disease is characterized by a fast functional impairment and ventilatory decline, leading most patients to die from respiratory failure. To estimate when patients should get ventilatory support, it is helpful to adequately profile the disease progression. For this purpose, we use dynamic Bayesian networks (DBNs), a machine learning model, that graphically represents the conditional dependencies among variables. However, the standard DBN framework only includes dynamic (time-dependent) variables, while most ALS datasets have dynamic and static (time-independent) observations. Therefore, we propose the sdtDBN framework, which learns optimal DBNs with static and dynamic variables. Besides learning DBNs from data, with polynomial-time complexity in the number of variables, the proposed framework enables the user to insert prior knowledge and to make inference in the learned DBNs. We use sdtDBNs to study the progression of 1214 patients from a Portuguese ALS dataset. First, we predict the values of every functional indicator in the patients' consultations, achieving results competitive with state-of-the-art studies. Then, we determine the influence of each variable in patients' decline before and after getting ventilatory support. This insightful information can lead clinicians to pay particular attention to specific variables when evaluating the patients, thus improving prognosis. The case study with ALS shows that sdtDBNs are a promising predictive and descriptive tool, which can also be applied to assess the progression of other diseases, given time-dependent and time-independent clinical observations.

Phytol, a Chlorophyll Component, Produces Antihyperalgesic, Anti-inflammatory, and Antiarthritic Effects: Possible NFκB Pathway Involvement and Reduced Levels of the Proinflammatory Cytokines TNF-α and IL-6.

Phytol is a diterpene constituent of chlorophyll and has been shown to have several pharmacological properties, particularly in relation to the management of painful inflammatory diseases. Arthritis is one of the most common of these inflammatory diseases, mainly affecting the synovial membrane, cartilage, and bone in joints. Proinflammatory cytokines, such as TNF-α and IL-6, and the NFκB signaling pathway play a pivotal role in arthritis. However, as the mechanisms of action of phytol and its ability to reduce the levels of these cytokines are poorly understood, we decided to investigate its pharmacological effects using a mouse model of complete Freund's adjuvant (CFA)-induced arthritis. Our results showed that phytol was able to inhibit joint swelling and hyperalgesia throughout the whole treatment period. Moreover, phytol reduced myeloperoxidase (MPO) activity and proinflammatory cytokine release in synovial fluid and decreased IL-6 production as well as the COX-2 immunocontent in the spinal cord. It also downregulated the p38MAPK and NFκB signaling pathways. Therefore, our findings demonstrated that phytol can be an innovative antiarthritic agent due to its capacity to attenuate inflammatory reactions in joints and the spinal cord, mainly through the modulation of mediators that are key to the establishment of arthritic pain.

Modelling cancer outcomes of bone metastatic patients: combining survival data with N-Telopeptide of type I collagen (NTX) dynamics through joint models.

BACKGROUND: Joint models (JM) have emerged as a promising statistical framework to concurrently analyse survival data and multiple longitudinal responses. This is particularly relevant in clinical studies where the goal is to estimate the association between time-to-event data and the biomarkers evolution. In the context of oncological data, JM can indeed provide interesting prognostic markers for the event under study and thus support clinical decisions and treatment choices. However, several problems arise when dealing with this type of data, such as the high-dimensionality of the covariates space, the lack of knowledge about the function structure of the time series and the presence of missing data, facts that may hamper the accurate estimation of the JM. METHODS: We propose to apply JM for the analysis of bone metastatic patients and infer the association of their survival with several covariates, in particular the N-Telopeptide of Type I Collagen (NTX) dynamics. This biomarker has been identified as a relevant prognostic factor in patients with metastatic cancer, but only using static information in some specific time points. RESULTS: We extended this analysis using the full NTX time series for a larger cohort of patients with bone metastasis, and compared the results obtained by the JM and the extended Cox regression model. Imputation based on fuzzy clustering was used to deal with missing values and several functions for NTX evolution were compared, such as rational, exponential and cubic splines. CONCLUSIONS: The JM obtained confirm the association between NTX values and patients' response, attesting the importance of this time series, and additionally provide a deep understanding of the key survival covariates.

Terpenes as possible drugs for the mitigation of arthritic symptoms - A systematic review.

BACKGROUND: Arthritis is a syndrome associated with exacerbated inflammation, joint destruction and chronic pain and disability. Chronic treatment of arthritis is associated with several side effects and high abandonment. Therefore, there has been an ongoing search for alternative treatments to overcome these problems. PURPOSE: Natural products, which are already widely used for their biological, cosmetic and pharmacotechnic properties, are a possible source for new drugs. Terpenes, a large class of organic compounds produced mainly by plants and trees, are a promising natural product and have already been shown to be effective in treating chronic pain, particularly of an inflammatory origin. STUDY DESIGN AND METHODS: This review identifies the main terpenes with anti-arthritic activity reported in the last 10 years. A survey was conducted between December 2017 and June 2018 in the PUBMED, SCOPUS and Science Direct databases using combinations of the descriptors terpenes, arthritis and inflammation. RESULTS: The results showed that terpenes have promising biological effects in relation to the treatment of arthritis, with the 24 terpenes identified in our survey being effective in the modulation of inflammatory mediators important to the physiopathology of arthritis, such as IL-6, IL-17, TNF-α, NFκB, and COX-2, among others. It is important to note that most of the studies used animal models, which limits, at least in part, the direct translation to humans of the experimental evidence produced by the studies. CONCLUSION: Together, our finds suggest that terpenes can modulate the immuno-regulatory and destructive tissue events that underlie the clinical presentation and the progression of arthritis and are worthy of further clinical investigation.

Information-Theoretical Criteria for Characterizing the Earliness of Time-Series Data.

Biomedical signals constitute time-series that sustain machine learning techniques to achieve classification. These signals are complex with measurements of several features over, eventually, an extended period. Characterizing whether the data can anticipate prediction is an essential task in time-series mining. The ability to obtain information in advance by having early knowledge about a specific event may be of great utility in many areas. Early classification arises as an extension of the time-series classification problem, given the need to obtain a reliable prediction as soon as possible. In this work, we propose an information-theoretic method, named Multivariate Correlations for Early Classification (MCEC), to characterize the early classification opportunity of a time-series. Experimental validation is performed on synthetic and benchmark data, confirming the ability of the MCEC algorithm to perform a trade-off between accuracy and earliness in a wide-spectrum of time-series data, such as those collected from sensors, images, spectrographs, and electrocardiograms.

AliClu - Temporal sequence alignment for clustering longitudinal clinical data.

BACKGROUND: Patient stratification is a critical task in clinical decision making since it can allow physicians to choose treatments in a personalized way. Given the increasing availability of electronic medical records (EMRs) with longitudinal data, one crucial problem is how to efficiently cluster the patients based on the temporal information from medical appointments. In this work, we propose applying the Temporal Needleman-Wunsch (TNW) algorithm to align discrete sequences with the transition time information between symbols. These symbols may correspond to a patient's current therapy, their overall health status, or any other discrete state. The transition time information represents the duration of each of those states. The obtained TNW pairwise scores are then used to perform hierarchical clustering. To find the best number of clusters and assess their stability, a resampling technique is applied. RESULTS: We propose the AliClu, a novel tool for clustering temporal clinical data based on the TNW algorithm coupled with clustering validity assessments through bootstrapping. The AliClu was applied for the analysis of the rheumatoid arthritis EMRs obtained from the Portuguese database of rheumatologic patient visits (Reuma.pt). In particular, the AliClu was used for the analysis of therapy switches, which were coded as letters corresponding to biologic drugs and included their durations before each change occurred. The obtained optimized clusters allow one to stratify the patients based on their temporal therapy profiles and to support the identification of common features for those groups. CONCLUSIONS: The AliClu is a promising computational strategy to analyse longitudinal patient data by providing validated clusters and by unravelling the patterns that exist in clinical outcomes. Patient stratification is performed in an automatic or semi-automatic way, allowing one to tune the alignment, clustering, and validation parameters. The AliClu is freely available at https://github.com/sysbiomed/AliClu.

Model selection for clustering of pharmacokinetic responses.

BACKGROUND AND OBJECTIVE: Pharmacokinetics comprises the study of drug absorption, distribution, metabolism and excretion over time. Clinical pharmacokinetics, focusing on therapeutic management, offers important insights towards personalised medicine through the study of efficacy and toxicity of drug therapies. This study is hampered by subject's high variability in drug blood concentration, when starting a therapy with the same drug dosage. Clustering of pharmacokinetics responses has been addressed recently as a way to stratify subjects and provide different drug doses for each stratum. This clustering method, however, is not able to automatically determine the correct number of clusters, using an user-defined parameter for collapsing clusters that are closer than a given heuristic threshold. We aim to use information-theoretical approaches to address parameter-free model selection. METHODS: We propose two model selection criteria for clustering pharmacokinetics responses, founded on the Minimum Description Length and on the Normalised Maximum Likelihood. RESULTS: Experimental results show the ability of model selection schemes to unveil the correct number of clusters underlying the mixture of pharmacokinetics responses. CONCLUSIONS: In this work we were able to devise two model selection criteria to determine the number of clusters in a mixture of pharmacokinetics curves, advancing over previous works. A cost-efficient parallel implementation in Java of the proposed method is publicly available for the community.

Evidence for the involvement of TNF-α, IL-1ß and IL-10 in the antinociceptive and anti-inflammatory effects of indole-3-guanylhydrazone hydrochloride, an aromatic aminoguanidine, in rodents.

BACKGROUND: Indole-3-guanylhydrazone hydrochloride (LQM01) is a new derivative of aminoguanidine hydrochloride, an aromatic aminoguanidine. METHODS: Mice were treated with LQM01 (5, 10, 25 or 50 mg/kg, i.p.), vehicle (0.9% saline i.p.) or a standard drug. The mice were subjected to carrageenan-induced pleurisy, abdominal writhing induced by acetic acid, the formalin test and the hot-plate test. The model of non-inflammatory chronic muscle pain induced by saline acid was also used. Mice from the chronic protocol were assessed for withdrawal threshold, muscle strength and motor coordination. LQM01 or vehicle treated mice were evaluated for Fos protein. RESULTS: LQM01 inhibits TNF-α and IL-1ß production, as well as leukocyte recruitment during inflammation process. The level of IL-10 in LQM01-treated mice increased in pleural fluid. In addition, LQM01 decreased the nociceptive behavior in the acetic acid induced writhing test, the formalin test (both phases) and increased latency time on the hot-plate. LQM01 treatment also decreased mechanical hyperalgesia in mice with chronic muscle pain, with no changes in muscle strength and motor coordination. LQM01 reduced the number of Fos positive cells in the superficial dorsal horn. This compound exhibited antioxidant properties in in vitro assays. CONCLUSIONS: LQM01 has an outstanding anti-inflammatory and analgesic profile, probably mediated through a reduction in proinflammatory cytokines release, increase in IL-10 production and reduction in neuron activity in the dorsal horn of the spinal cord in mice. GENERAL SIGNIFICANCE: Beneficial effects of LQM01 suggest that it has some important clinical features and can play a role in the management of 'dysfunctional pain' and inflammatory diseases.

Polynomial-Time Algorithm for Learning Optimal BFS-Consistent Dynamic Bayesian Networks.

Dynamic Bayesian networks (DBN) are powerful probabilistic representations that model stochastic processes. They consist of a prior network, representing the distribution over the initial variables, and a set of transition networks, representing the transition distribution between variables over time. It was shown that learning complex transition networks, considering both intra- and inter-slice connections, is NP-hard. Therefore, the community has searched for the largest subclass of DBNs for which there is an efficient learning algorithm. We introduce a new polynomial-time algorithm for learning optimal DBNs consistent with a breadth-first search (BFS) order, named bcDBN. The proposed algorithm considers the set of networks such that each transition network has a bounded in-degree, allowing for p edges from past time slices (inter-slice connections) and k edges from the current time slice (intra-slice connections) consistent with the BFS order induced by the optimal tree-augmented network (tDBN). This approach increases exponentially, in the number of variables, the search space of the state-of-the-art tDBN algorithm. Concerning worst-case time complexity, given a Markov lag m, a set of n random variables ranging over r values, and a set of observations of N individuals over T time steps, the bcDBN algorithm is linear in N, T and m; polynomial in n and r; and exponential in p and k. We assess the bcDBN algorithm on simulated data against tDBN, revealing that it performs well throughout different experiments.

Pattern matching through Chaos Game Representation: bridging numerical and discrete data structures for biological sequence analysis.

BACKGROUND: Chaos Game Representation (CGR) is an iterated function that bijectively maps discrete sequences into a continuous domain. As a result, discrete sequences can be object of statistical and topological analyses otherwise reserved to numerical systems. Characteristically, CGR coordinates of substrings sharing an L-long suffix will be located within 2-L distance of each other. In the two decades since its original proposal, CGR has been generalized beyond its original focus on genomic sequences and has been successfully applied to a wide range of problems in bioinformatics. This report explores the possibility that it can be further extended to approach algorithms that rely on discrete, graph-based representations. RESULTS: The exploratory analysis described here consisted of selecting foundational string problems and refactoring them using CGR-based algorithms. We found that CGR can take the role of suffix trees and emulate sophisticated string algorithms, efficiently solving exact and approximate string matching problems such as finding all palindromes and tandem repeats, and matching with mismatches. The common feature of these problems is that they use longest common extension (LCE) queries as subtasks of their procedures, which we show to have a constant time solution with CGR. Additionally, we show that CGR can be used as a rolling hash function within the Rabin-Karp algorithm. CONCLUSIONS: The analysis of biological sequences relies on algorithmic foundations facing mounting challenges, both logistic (performance) and analytical (lack of unifying mathematical framework). CGR is found to provide the latter and to promise the former: graph-based data structures for sequence analysis operations are entailed by numerical-based data structures produced by CGR maps, providing a unifying analytical framework for a diversity of pattern matching problems.

GRISOTTO: A greedy approach to improve combinatorial algorithms for motif discovery with prior knowledge.

BACKGROUND: Position-specific priors (PSP) have been used with success to boost EM and Gibbs sampler-based motif discovery algorithms. PSP information has been computed from different sources, including orthologous conservation, DNA duplex stability, and nucleosome positioning. The use of prior information has not yet been used in the context of combinatorial algorithms. Moreover, priors have been used only independently, and the gain of combining priors from different sources has not yet been studied. RESULTS: We extend RISOTTO, a combinatorial algorithm for motif discovery, by post-processing its output with a greedy procedure that uses prior information. PSP's from different sources are combined into a scoring criterion that guides the greedy search procedure. The resulting method, called GRISOTTO, was evaluated over 156 yeast TF ChIP-chip sequence-sets commonly used to benchmark prior-based motif discovery algorithms. Results show that GRISOTTO is at least as accurate as other twelve state-of-the-art approaches for the same task, even without combining priors. Furthermore, by considering combined priors, GRISOTTO is considerably more accurate than the state-of-the-art approaches for the same task. We also show that PSP's improve GRISOTTO ability to retrieve motifs from mouse ChiP-seq data, indicating that the proposed algorithm can be applied to data from a different technology and for a higher eukaryote. CONCLUSIONS: The conclusions of this work are twofold. First, post-processing the output of combinatorial algorithms by incorporating prior information leads to a very efficient and effective motif discovery method. Second, combining priors from different sources is even more beneficial than considering them separately.

YEASTRACT-DISCOVERER: new tools to improve the analysis of transcriptional regulatory associations in Saccharomyces cerevisiae.

The Yeast search for transcriptional regulators and consensus tracking (YEASTRACT) information system (www.yeastract.com) was developed to support the analysis of transcription regulatory associations in Saccharomyces cerevisiae. Last updated in September 2007, this database contains over 30 990 regulatory associations between Transcription Factors (TFs) and target genes and includes 284 specific DNA binding sites for 108 characterized TFs. Computational tools are also provided to facilitate the exploitation of the gathered data when solving a number of biological questions, in particular the ones that involve the analysis of global gene expression results. In this new release, YEASTRACT includes DISCOVERER, a set of computational tools that can be used to identify complex motifs over-represented in the promoter regions of co-regulated genes. The motifs identified are then clustered in families, represented by a position weight matrix and are automatically compared with the known transcription factor binding sites described in YEASTRACT. Additionally, in this new release, it is possible to generate graphic depictions of transcriptional regulatory networks for documented or potential regulatory associations between TFs and target genes. The visual display of these networks of interactions is instrumental in functional studies. Tutorials are available on the system to exemplify the use of all the available tools.

An efficient algorithm for the identification of structured motifs in DNA promoter sequences.

We propose a new algorithm for identifying cis-regulatory modules in genomic sequences. The proposed algorithm, named RISO, uses a new data structure, called box-link, to store the information about conserved regions that occur in a well-ordered and regularly spaced manner in the data set sequences. This type of conserved regions, called structured motifs, is extremely relevant in the research of gene regulatory mechanisms since it can effectively represent promoter models. The complexity analysis shows a time and space gain over the best known exact algorithms that is exponential in the spacings between binding sites. A full implementation of the algorithm was developed and made available online. Experimental results show that the algorithm is much faster than existing ones, sometimes by more than four orders of magnitude. The application of the method to biological data sets shows its ability to extract relevant consensi.