Search

Fracture detection by artificial intelligence and especially Deep Convolutional Neural Networks (DCNN) is a topic of growing interest in current orthopaedic and radiological research. As learning a DCNN usually needs a large amount of training data, mostly frequent fractures as well as conventional X-ray are used. Therefore, less common fractures like acetabular fractures (AF) are underrepresented in the literature. The aim of this pilot study was to establish a DCNN for detection of AF using computer tomography (CT) scans.Patients with an acetabular fracture were identified from the monocentric consecutive pelvic injury registry at the BG Trauma Center XXX from 01/2003 - 12/2019. All patients with unilateral AF and CT scans available in DICOM-format were included for further processing. All datasets were automatically anonymised and digitally post-processed. Extraction of the relevant region of interests was performed and the technique of data augmentation (DA) was implemented to artificially increase the number of training samples. A DCNN based on Med3D was used for autonomous fracture detection, using global average pooling (GAP) to reduce overfitting.From a total of 2,340 patients with a pelvic fracture, 654 patients suffered from an AF. After screening and post-processing of the datasets, a total of 159 datasets were enrolled for training of the algorithm. A random assignment into training datasets (80%) and test datasets (20%) was performed. The technique of bone area extraction, DA and GAP increased the accuracy of fracture detection from 58.8% (native DCNN) up to an accuracy of 82.8% despite the low number of datasets.The accuracy of fracture detection of our trained DCNN is comparable to published values despite the low number of training datasets. The techniques of bone extraction, DA and GAP are useful for increasing the detection rates of rare fractures by a DCNN. Based on the used DCNN in combination with the described techniques from this pilot study, the possibility of an automatic fracture classification of AF is under investigation in a multicentre study.Die automatische Frakturerkennung mithilfe von künstlicher Intelligenz (KI) ist derzeit ein wichtiges Thema in der unfallchirurgischen und radiologischen Forschung. Vor allem bei der Nutzung von „Deep Convolutional Neural Networks“ (DCNN) ist allerdings üblicherweise eine große Anzahl an Trainingsdatensätzen erforderlich, um gute Erkennungsraten zu erzielen, weswegen diese Methoden bisher i. d. R. an sehr häufigen Frakturen und an Röntgenbildern angewendet werden. Demgegenüber stellen seltene Frakturen wie die Azetabulumfraktur (AF) eine Herausforderung für neuronale Netzwerke dar. Ziel dieser Pilotstudie war es daher, einen Algorithmus zu entwickeln, mit dessen Hilfe AF anhand von CT-Bildern zuverlässig automatisch erkannt werden können.Patienten mit einer einseitigen AF wurden aus dem monozentrischen Beckenregister der BG Unfallklinik Tübingen über einen Zeitraum von 01/2003 bis 12/2019 identifiziert. Patienten, bei denen CT-Datensätze im DICOM-Format vorlagen, wurden weiterverarbeitet. Die automatische Weiterverarbeitung beinhaltete die Anonymisierung sowie verschiedene Methoden der Knochenextraktion, der „Data Augmentation“ (DA) sowie des Global Average Poolings (GAP), um die Datensätze für das Training des auf Basis von Med3D erstellten DCNN vorzubereiten.Von insgesamt 2340 Patienten mit einer Beckenfraktur erlitten 654 eine AF. Nach Weiterverarbeitung der Datensätze konnten 159 Datensätze für das Training verwendet werden. 80% davon wurden als Trainingsdatensätze randomisiert, 20% wurden als Testdatensätze randomisiert. Durch die Techniken der DA und des GAP konnte die Erkennungsrate des DCNN trotz der geringen Zahl an Trainingsdatensätzen von 58,8 auf 82,8% gesteigert werden.Die Erkennungsrate unseres DCNN ist trotz der im Vergleich niedrigen Zahl an Trainingsdatensätzen vergleichbar mit Literaturangaben bei häufigeren Frakturen. Die Techniken der Knochenextraktion, verbunden mit der DA und der GAP, helfen bei selten auftretenden Frakturen, die Erkennungsraten eines DCNN zu erhöhen. Mit den Techniken und dem DCNN aus dieser Pilotstudie soll in einer Multicenterstudie an einer größeren Anzahl an Datensätzen die Möglichkeit einer automatischen Klassifizierung von AF untersucht werden.

Elderly individuals are at high risk for severe COVID-19. Due to modest vaccine responses compared to younger individuals and the time elapsed since prioritized vaccinations, the emerging immune-evasive Omicron variant of SARS-CoV-2 is a particular concern for the elderly. Here we longitudinally determined SARS-CoV-2-neutralizing serum activity against different variants in a cohort of 37 individuals with a median age of 82 years. Participants were followed for 10 months after an initial two-dose BNT162b2 vaccination and up to 4.5 months after a BNT162b2 booster. Detectable Omicron-neutralizing activity was nearly absent after two vaccinations but elicited in 89% of individuals by the booster immunization. Neutralizing titers against the Wu01, Delta, and Omicron variants showed similar post-boost declines and 81% of individuals maintained detectable activity against Omicron. Our study demonstrates the mRNA booster effectiveness in inducing Omicron neutralizing activity and provides critical information on vaccine response durability in the highly vulnerable elderly population.

Background: Lower respiratory tract infections are among the main causes of death. Although there are many respiratory viruses, diagnostic efforts are focused mainly on influenza. The Respiratory Viruses Network (RespVir) collects infection data, primarily from German university hospitals, for a high diversity of infections by respiratory pathogens. In this study, we computationally analysed a subset of the RespVir database, covering 217,150 samples tested for 17 different viral pathogens in the time span from 2010 to 2019. Methods: We calculated the prevalence of 17 respiratory viruses, analysed their seasonality patterns using information-theoretic measures and agglomerative clustering, and analysed their propensity for dual infection using a new metric dubbed average coinfection exclusion score (ACES). Results: After initial data pre-processing, we retained 206,814 samples, corresponding to 1,408,657 performed tests. We found that Influenza viruses were reported for less than half of all infections and that they exhibited the highest degree of seasonality Coinfections of viruses are frequent, the most prevalent coinfection was rhinovirus/bocavirus and most of the virus pairs had a positive ACES indicating a tendency to exclude each other regarding infection. Conclusions: The analysis of respiratory viruses dynamics in monoinfection and coinfection contributes to the prevention, diagnostic, treatment, and development of new therapeutics. Data obtained from multiplex testing is fundamental for this analysis and should be prioritized over single pathogen testing.

The identification and isolation of highly infectious SARS-CoV-2-infected individuals is an important public health strategy. Rapid antigen detection tests (RADT) are promising tools for large-scale screenings due to timely results and feasibility for on-site testing. Nonetheless, the diagnostic performance of RADT in detecting infectious individuals is not yet fully determined. In this study, RT-qPCR and virus culture of RT-qPCR-positive samples were used to evaluate and compare the performance of the Standard Q COVID-19 Ag test in detecting SARS-CoV-2-infected and possibly infectious individuals. To this end, two combined oro- and nasopharyngeal swabs were collected at a routine SARS-CoV-2 diagnostic center. A total of 2,028 samples were tested, and 118 virus cultures were inoculated. SARS-CoV-2 infection was detected in 210 samples by RT-qPCR, representing a positive rate of 10.36%. The Standard Q COVID-19 Ag test yielded a positive result in 92 (4.54%) samples resulting in an overall sensitivity and specificity of 42.86 and 99.89%, respectively. For adjusted CT values of

Understanding antibody-based SARS-CoV-2 immunity is critical for overcoming the COVID-19 pandemic and informing vaccination strategies. We evaluated SARS-CoV-2 antibody dynamics over 10 months in 963 individuals who predominantly experienced mild COVID-19. Investigating 2,146 samples, we initially detected SARS-CoV-2 antibodies in 94.4% of individuals, with 82% and 79% exhibiting serum and IgG neutralization, respectively. Approximately 3% of individuals demonstrated exceptional SARS-CoV-2 neutralization, with these “elite neutralizers” also possessing SARS-CoV-1 cross-neutralizing IgG. Multivariate statistical modeling revealed age, symptomatic infection, disease severity, and gender as key factors predicting SARS-CoV-2-neutralizing activity. A loss of reactivity to the virus spike protein was observed in 13% of individuals 10 months after infection. Neutralizing activity had half-lives of 14.7 weeks in serum versus 31.4 weeks in purified IgG, indicating a rather long-term IgG antibody response. Our results demonstrate a broad spectrum in the initial SARS-CoV-2-neutralizing antibody response, with sustained antibodies in most individuals for 10 months after mild COVID-19., Graphical abstract, Vanshylla et al. report longitudinal antibody kinetics in a mainly mild COVID-19 convalescent cohort of 963 individuals. There is broad variation in the initial response with older age and disease severity predicting higher SARS-CoV-2 neutralizing activity. Neutralizing IgG antibodies are detectable for up to 10 months in the majority of individuals.

The identification and isolation of highly infectious SARS-CoV-2-infected individuals is an important public health strategy. Rapid antigen detection tests (RADT) are promising candidates for large-scale screenings due to timely results and feasibility for on-site testing. Nonetheless, the diagnostic performance of RADT in detecting infectious individuals is yet to be fully determined. Two combined oro- and nasopharyngeal swabs were collected from individuals at a routine SARS-CoV-2 diagnostic center. Side-by-side evaluations of RT-qPCR and RADT as well as live virus cultures of positive samples were performed to determine the sensitivity of the Standard Q COVID-19 Ag Test (SD Biosensor/Roche) in detecting SARS-CoV-2-infected individuals with cultivable virus. A total of 2,028 samples were tested and 118 virus cultures inoculated. SARS-CoV-2 infection was detected in 210 samples by RT-qPCR, representing a positive rate of 10.36%. The Standard Q COVID-19 Ag Test yielded a positive result in 92 (4.54%) samples resulting in an overall sensitivity and specificity of 42.86% and 99.89%. For adjusted Ct values

Key message We studied the DNA-binding profile of the MADS-domain transcription factor SEPALLATA3 and mutant variants by SELEX-seq. DNA-binding characteristics of SEPALLATA3 mutant proteins lead us to propose a novel DNA-binding mode. Abstract MIKC-type MADS-domain proteins, which function as essential transcription factors in plant development, bind as dimers to a 10-base-pair AT-rich motif termed CArG-box. However, this consensus motif cannot fully explain how the abundant family members in flowering plants can bind different target genes in specific ways. The aim of this study was to better understand the DNA-binding specificity of MADS-domain transcription factors. Also, we wanted to understand the role of a highly conserved arginine residue for binding specificity of the MADS-domain transcription factor family. Here, we studied the DNA-binding profile of the floral homeotic MADS-domain protein SEPALLATA3 by performing SELEX followed by high-throughput sequencing (SELEX-seq). We found a diverse set of bound sequences and could estimate the in vitro binding affinities of SEPALLATA3 to a huge number of different sequences. We found evidence for the preference of AT-rich motifs as flanking sequences. Whereas different CArG-boxes can act as SEPALLATA3 binding sites, our findings suggest that the preferred flanking motifs are almost always the same and thus mostly independent of the identity of the central CArG-box motif. Analysis of SEPALLATA3 proteins with a single amino acid substitution at position 3 of the DNA-binding MADS-domain further revealed that the conserved arginine residue, which has been shown to be involved in a shape readout mechanism, is especially important for the recognition of nucleotides at positions 3 and 8 of the CArG-box motif. This leads us to propose a novel DNA-binding mode for SEPALLATA3, which is different from that of other MADS-domain proteins known.

A detailed understanding of antibody-based SARS-CoV-2 immunity has critical implications for overcoming the COVID-19 pandemic and for informing on vaccination strategies. In this study, we evaluated the dynamics of the SARS-CoV-2 antibody response in a cohort of 963 recovered individuals over a period of 10 months. Investigating a total of 2,146 samples, we detected an initial SARS-CoV-2 antibody response in 94.4% of individuals, with 82% and 79% exhibiting serum and IgG neutralization, respectively. Approximately 3% of recovered patients demonstrated exceptional SARS-CoV-2 neutralizing activity, defining them as ‘elite neutralizers’. These individuals also possessed effective cross-neutralizing IgG antibodies to SARS-CoV-1 without any known prior exposure to this virus. By applying multivariate statistical modeling, we found that sero-reactivity, age, time since disease onset, and fever are key factors predicting SARS-CoV-2 neutralizing activity in mild courses of COVID-19. Investigating longevity of the antibody response, we detected loss of anti-spike reactivity in 13% of individuals 10 months after infection. Moreover, neutralizing activity had an initial half-life of 6.7 weeks in serum versus 30.8 weeks in purified IgG samples indicating the presence of a more stable and long-term memory IgG B cell repertoire in the majority of individuals recovered from COVID-19. Our results demonstrate a broad spectrum of the initial SARS-CoV-2 neutralizing antibody response depending on clinical characteristics, with antibodies being maintained in the majority of individuals for the first 10 months after mild course of COVID-19.

A detailed understanding of antibody-based SARS-CoV-2 immunity has critical implications for overcoming the COVID-19 pandemic and informing vaccination strategies. We evaluated SARS-CoV-2 antibody response dynamics in a cohort of 963 individuals over 10 months. Investigating 2,146 samples, we initially detected SARS-CoV-2 antibodies in 94.4% individuals, with 82% and 79% exhibiting serum and IgG neutralization, respectively. Approximately 3% of patients demonstrated exceptional SARS-CoV-2-neutralization, with these ‘elite neutralizers’ also possessing cross-neutralizing IgG to SARS-CoV-1. Multivariate statistical modeling revealed sero-reactivity, age and fever as key factors predicting SARS-CoV-2 neutralizing activity. A loss of anti-spike reactivity in 13% individuals was detected 10 months after infection. Neutralizing activity had half-lives of 14.7 weeks in serum versus 31.4 weeks in purified IgG, indicating a stable long-term memory IgG B-cell repertoire. Our results demonstrate a broad spectrum in the initial SARS-CoV-2-neutralizing antibody response, with sustained antibodies in majority of individuals for 10 months after mild COVID-19. Funding: This work was funded by grants to Florian Kleinfrom the German Center for Infection Research (DZIF), the German Research Foundation (DFG) CRC1279 and CRC1310, European Research Council (ERC) ERC-stG639961 and COVIM: „NaFoUniMedCovid19“ (FKZ: 01KX2021). Ethical Approval: Blood samples were collected from donors who gave their written consent under the protocols 20-1187 and 16-054, approved by the Institutional Review Board (IRB) of the University Hospital Cologne.

Modern exact algorithms for structure learning in Bayesian networks first compute an exact local score of every candidate parent set, and then find a network structure by combinatorial optimization so as to maximize the global score. This approach assumes that each local score can be computed fast, which can be problematic when the scarcity of the data calls for structured local models or when there are both continuous and discrete variables, for these cases have lacked efficient-to-compute local scores. To address this challenge, we introduce a local score that is based on a class of classification and regression trees. We show that under modest restrictions on the possible branchings in the tree structure, it is feasible to find a structure that maximizes a Bayes score in a range of moderate-size problem instances. In particular, this enables global optimization of the Bayesian network structure, including the local structure. In addition, we introduce a related model class that extends ordinary conditional probability tables to continuous variables by employing an adaptive discretization approach. The two model classes are compared empirically by learning Bayesian networks from benchmark real-world and synthetic data sets. We discuss the relative strengths of the model classes in terms of their structure learning capability, predictive performance, and running time. (C) 2019 The Authors. Published by Elsevier Inc.

Parsimonious context trees, PCTs, provide a sparse parameterization of conditional probability distributions. They are particularly powerful for modeling context-specific independencies in sequential discrete data. Learning PCTs from data is computationally hard due to the combinatorial explosion of the space of model structures as the number of predictor variables grows. Under the score-and-search paradigm, the fastest algorithm for finding an optimal PCT, prior to the present work, is based on dynamic programming. While the algorithm can handle small instances fast, it becomes infeasible already when there are half a dozen four-state predictor variables. Here, we show that common scoring functions enable the use of new algorithmic ideas, which can significantly expedite the dynamic programming algorithm on typical data. Specifically, we introduce a memoization technique, which exploits regularities within the predictor variables by equating different contexts associated with the same data subset, and a bound-and-prune technique, which exploits regularities within the response variable by pruning parts of the search space based on score upper bounds. On real-world data from recent applications of PCTs within computational biology the ideas are shown to reduce the traversed search space and the computation time by several orders of magnitude in typical cases.

Recombinant vesicular stomatitis virus-Zaire Ebola virus (rVSV-ZEBOV) is the most advanced Ebola virus vaccine candidate and is currently being used to combat the outbreak of Ebola virus disease (EVD) in the Democratic Republic of the Congo (DRC). Here we examine the humoral immune response in a subset of human volunteers enrolled in a phase 1 rVSV-ZEBOV vaccination trial by performing comprehensive single B cell and electron microscopy structure analyses. Four studied vaccinees show polyclonal, yet reproducible and convergent B cell responses with shared sequence characteristics. EBOV-targeting antibodies cross-react with other Ebolavirus species, and detailed epitope mapping revealed overlapping target epitopes with antibodies isolated from EVD survivors. Moreover, in all vaccinees, we detected highly potent EBOV-neutralizing antibodies with activities comparable or superior to the monoclonal antibodies currently used in clinical trials. These include antibodies combining the IGHV3-15/IGLV1-40 immunoglobulin gene segments that were identified in all investigated individuals. Our findings will help to evaluate and direct current and future vaccination strategies and offer opportunities for novel EVD therapies.

Recombinant vesicular stomatitis virus–Zaire Ebola virus (rVSV-ZEBOV) is the most advanced Ebola virus vaccine candidate and is currently being used to combat the outbreak of Ebola virus disease (EVD) in the Democratic Republic of the Congo (DRC). Here we examine the humoral immune response in a subset of human volunteers enrolled in a phase 1 rVSV-ZEBOV vaccination trial by performing comprehensive single B cell and electron microscopy structure analyses. Four studied vaccinees show polyclonal, yet reproducible and convergent B cell responses with shared sequence characteristics. EBOV-targeting antibodies cross-react with other Ebolavirus species, and detailed epitope mapping revealed overlapping target epitopes with antibodies isolated from EVD survivors. Moreover, in all vaccinees, we detected highly potent EBOV-neutralizing antibodies with activities comparable or superior to the monoclonal antibodies currently used in clinical trials. These include antibodies combining the IGHV3–15/IGLV1–40 immunoglobulin gene segments that were identified in all investigated individuals. Our findings will help to evaluate and direct current and future vaccination strategies and offer opportunities for novel EVD therapies. Analysis of monoclonal antibody responses to the Ebola virus vaccine rVSV-ZEBOV in human volunteers.

Motivation Predictive models are a powerful tool for solving complex problems in computational biology. They are typically designed to predict or classify data coming from the same unknown distribution as the training data. In many real-world settings, however, uncontrolled biological or technical factors can lead to a distribution mismatch between datasets acquired at different times, causing model performance to deteriorate on new data. A common additional obstacle in computational biology is scarce data with many more features than samples. To address these problems, we propose a method for unsupervised domain adaptation that is based on a weighted elastic net. The key idea of our approach is to compare dependencies between inputs in training and test data and to increase the cost of differently behaving features in the elastic net regularization term. In doing so, we encourage the model to assign a higher importance to features that are robust and behave similarly across domains. Results We evaluate our method both on simulated data with varying degrees of distribution mismatch and on real data, considering the problem of age prediction based on DNA methylation data across multiple tissues. Compared with a non-adaptive standard model, our approach substantially reduces errors on samples with a mismatched distribution. On real data, we achieve far lower errors on cerebellum samples, a tissue which is not part of the training data and poorly predicted by standard models. Our results demonstrate that unsupervised domain adaptation is possible for applications in computational biology, even with many more features than samples. Availability and implementation Source code is available at https://github.com/PfeiferLabTue/wenda. Supplementary information Supplementary data are available at Bioinformatics online.

Summary Recent studies have shown that the traditional position weight matrix model is often insufficient for modeling transcription factor binding sites, as intra-motif dependencies play a significant role for an accurate description of binding motifs. Here, we present the Java application InMoDe, a collection of tools for learning, leveraging and visualizing such dependencies of putative higher order. The distinguishing feature of InMoDe is a robust model selection from a class of parsimonious models, taking into account dependencies only if justified by the data while choosing for simplicity otherwise. Availability and Implementation InMoDe is implemented in Java and is available as command line application, as application with a graphical user-interface, and as an integration into Galaxy on the project website at http://www.jstacs.de/index.php/InMoDe.

Alterations in gene regulation are considered major driving forces in divergent evolution. This is reflected in different species by the variable architecture of regulatory networks controlling highly conserved metabolic pathways. While many regulatory proteins are surprisingly conserved their wiring has evolved more rapidly. This project focuses on the adaptation to nutrient limitation, which requires the activation of the conserved AMP-activated protein kinase (AMPK alias Snf1 in yeast) and its downstream effectors. The goal is to uncover basic principles of adaptation and steps in the evolutionary process associated with regulatory network rearrangement. This requires improving the prediction of gene regulation based experimental data, DNA sequence information and information theory. In this project Context Tree (CT) models and Parsimonious Context Tree (PCT) models and the corresponding algorithms for extended Context Tree Maximization (CTM) and extended Parsimonious Context Tree Maximization (PCTM) are derived, implemented, and applied. Computational predictions and experimental validation will establish an iterative cycle to improve algorithms in each cycle leading to a growing set of experimentally verified and falsified predictions, finally allowing a deeper understanding of the evolution of the transcriptional regulatory network controlling energy metabolism, one of the most fundamental processes conserved across all kingdoms of life.

The binding motifs of many transcription factors (TFs) comprise a higher degree of complexity than a single position weight matrix model permits. Additional complexity is typically taken into account either as intra-motif dependencies via more sophisticated probabilistic models or as heterogeneities via multiple weight matrices. However, both orthogonal approaches have limitations when learning from in vivo data where binding sites of other factors in close proximity can interfere with motif discovery for the protein of interest. In this work, we demonstrate how intra-motif complexity can, purely by analyzing the statistical properties of a given set of TF-binding sites, be distinguished from complexity arising from an intermix with motifs of co-binding TFs or other artifacts. In addition, we study the related question whether intra-motif complexity is represented more effectively by dependencies, heterogeneities or variants in between. Benchmarks demonstrate the effectiveness of both methods for their respective tasks and applications on motif discovery output from recent tools detect and correct many undesirable artifacts. These results further suggest that the prevalence of intra-motif dependencies may have been overestimated in previous studies on in vivo data and should thus be reassessed.

Background Statistical modeling of transcription factor binding sites is one of the classical fields in bioinformatics. The position weight matrix (PWM) model, which assumes statistical independence among all nucleotides in a binding site, used to be the standard model for this task for more than three decades but its simple assumptions are increasingly put into question. Recent high-throughput sequencing methods have provided data sets of sufficient size and quality for studying the benefits of more complex models. However, learning more complex models typically entails the danger of overfitting, and while model classes that dynamically adapt the model complexity to data have been developed, effective model selection is to date only possible for fully observable data, but not, e.g., within de novo motif discovery. Results To address this issue, we propose a stochastic algorithm for performing robust model selection in a latent variable setting. This algorithm yields a solution without relying on hyperparameter-tuning via massive cross-validation or other computationally expensive resampling techniques. Using this algorithm for learning inhomogeneous parsimonious Markov models, we study the degree of putative higher-order intra-motif dependencies for transcription factor binding sites inferred via de novo motif discovery from ChIP-seq data. We find that intra-motif dependencies are prevalent and not limited to first-order dependencies among directly adjacent nucleotides, but that second-order models appear to be the significantly better choice. Conclusions The traditional PWM model appears to be indeed insufficient to infer realistic sequence motifs, as it is on average outperformed by more complex models that take into account intra-motif dependencies. Moreover, using such models together with an appropriate model selection procedure does not lead to a significant performance loss in comparison with the PWM model for any of the studied transcription factors. Hence, we find it worthwhile to recommend that any modern motif discovery algorithm should attempt to take into account intra-motif dependencies. Electronic supplementary material The online version of this article (doi:10.1186/s12859-015-0797-4) contains supplementary material, which is available to authorized users.

We introduce inhomogeneous parsimonious Markov models for modeling statistical patterns in discrete sequences. These models are based on parsimonious context trees, which are a generalization of context trees, and thus generalize variable order Markov models. We follow a Bayesian approach, consisting of structure and parameter learning. Structure learning is a challenging problem due to an overexponential number of possible tree structures, so we describe an exact and efficient dynamic programming algorithm for finding the optimal tree structures. We apply model and learning algorithm to the problem of modeling binding sites of the human transcription factor C/EBP, and find an increased prediction performance compared to fixed order and variable order Markov models. We investigate the reason for this improvement and find several instances of context-specific dependences that can be captured by parsimonious context trees but not by traditional context trees.

The binding affinity of DNA-binding proteins such as transcription factors is mainly determined by the base composition of the corresponding binding site on the DNA strand. Most proteins do not bind only a single sequence, but rather a set of sequences, which may be modeled by a sequence motif. Algorithms for de novo motif discovery differ in their promoter models, learning approaches, and other aspects, but typically use the statistically simple position weight matrix model for the motif, which assumes statistical independence among all nucleotides. However, there is no clear justification for that assumption, leading to an ongoing debate about the importance of modeling dependencies between nucleotides within binding sites. In the past, modeling statistical dependencies within binding sites has been hampered by the problem of limited data. With the rise of high-throughput technologies such as ChIP-seq, this situation has now changed, making it possible to make use of statistical dependencies effectively. In this work, we investigate the presence of statistical dependencies in binding sites of the human enhancer-blocking insulator protein CTCF by using the recently developed model class of inhomogeneous parsimonious Markov models, which is capable of modeling complex dependencies while avoiding overfitting. These findings lead to a more detailed characterization of the CTCF binding motif, which is only poorly represented by independent nucleotide frequencies at several positions, predominantly at the 3′ end.

To compare learning algorithms that differ by the adopted statistical paradigm, model class, or search heuristic, it is common to evaluate the performance on training data of varying size. Measuring the performance is straightforward if the data are generated from a known model, the ground truth. However, when the study concerns real-world data, the current methodology is limited to estimating predictive performance, typically by cross-validation. This work introduces a method to compare algorithms’ ability to learn the model structure, assuming no ground truth is given. The idea is to identify a partial structure on which the algorithms agree, and measure the performance in relation to that structure on subsamples of the data. The method is instantiated to structure learning in Bayesian networks, measuring the performance by the structural Hamming distance. It is tested using benchmark ground truth networks and algorithms that maximize various scoring functions. The results show that the method can produce evaluation outcomes that are close to those one would obtain if the ground truth was available.

Inhomogeneous parsimonious Markov models have recently been introduced for modeling symbolic sequences, with a main application being DNA sequence analysis. Structure and parameter learning of these models has been proposed using a Bayesian approach, which entails the practically challenging choice of the prior distribution. Cross validation is a possible way of tuning the prior hyperparameters towards a specific task such as prediction or classification, but it is overly time-consuming. On this account, robust learning methods, which do not require explicit prior specification and – in the absence of prior knowledge – no hyperparameter tuning, are of interest. In this work, we empirically investigate the performance of robust alternatives for structure and parameter learning that extend the practical applicability of parsimonious Markov models to more complex settings than before.

We give a novel algorithm for finding a parsimonious context tree (PCT) that best fits a given data set. PCTs extend traditional context trees by allowing context-specific grouping of the states of a context variable, also enabling skipping the variable. However, they gain statistical efficiency at the cost of computational efficiency, as the search space of PCTs is of tremendous size. We propose pruning rules based on efficiently computable score upper bounds with the aim of reducing this search space significantly. While our concrete bounds exploit properties of the BIC score, the ideas apply also to other scoring functions. Empirical results show that our algorithm is typically an order-of-magnitude faster than a recently proposed memory-intensive algorithm, or alternatively, about equally fast but using dramatically less memory.

Parsimonious Markov models, a generalization of variable order Markov models, have been recently introduced for modeling biological sequences. Up to now, they have been learned by Bayesian approaches. However, there is not always sufficient prior knowledge available and a fully uninformative prior is difficult to define. In order to avoid cumbersome cross validation procedures for obtaining the optimal prior choice, we here adapt scoring criteria for Bayesian networks that approximate the Normalized Maximum Likelihood (NML) to parsimonious Markov models. We empirically compare their performance with the Bayesian approach by classifying splice sites, an important problem from computational biology. Non