A Fixed-Parameter Tractable Algorithm for Finding Agreement Cherry-Reduced Subnetworks in Level-1 Orchard Networks.

Phylogenetic networks are increasingly being considered better suited to represent the complexity of the evolutionary relationships between species. One class of phylogenetic networks that have received a lot of attention recently is the class of orchard networks, which is composed of networks that can be reduced to a single leaf using cherry reductions. Cherry reductions, also called cherry-picking operations, remove either a leaf of a simple cherry (sibling leaves sharing a parent) or a reticulate edge of a reticulate cherry (two leaves whose parents are connected by a reticulate edge). In this article, we present a fixed-parameter tractable algorithm to solve the problem of finding a maximum agreement cherry-reduced subnetwork (MACRS) between two rooted binary level-1 networks. This is the first exact algorithm proposed to solve the MACRS problem. As proven in an earlier work, there is a direct relationship between finding an MACRS and calculating a distance based on cherry operations. As a result, the proposed algorithm also provides a distance that can be used for the comparison of level-1 networks.

Use of Wearable and Wireless Technology in Real-World Clinical Settings to Improve Patient Outcomes in Chronic Kidney Disease: A Mixed Methods Pilot Prospective Trial.

Background: During the 30-day period prior to initiating dialysis, there is a 10-fold rise in emergency department visits and hospitalizations related to kidney failure. Objective: The Virtual Ward Incorporating Electronic Wearables (VIEWER) trial implemented a home telemonitoring system to track changes in patients' vitals and assess their adherence and the acceptability of telemonitoring in a chronic kidney disease (CKD) population. Design: A pilot prospective clinical trial using a mixed methods approach was performed. Setting: The research was conducted in Winnipeg, Manitoba. Participants: There were 2 phases: Phase 1 was a 2-week-long pilot trial consisting of 10 participants. Phase 2 was a 3-month-long trial with a total of 26 participants. Patients with an estimated glomerular filtration rate <15 and a >40% risk of beginning dialysis in the next 2 years according to the kidney failure risk equation were eligible to participate in the study. Methods: The primary quantitative outcome was adherence, defined as the proportion of daily self-assessments completed using VIEWER over the follow-up period. The usability and acceptability of VIEWER was assessed qualitatively at the end of the trial through structured questionnaires and focus groups. Results: Phase 1 participants (n = 10) had a median adherence of 77.17% for the 2-week observation period. Phase 2 participants (n = 26) showed a lower median adherence of 36% for the 3-month period. Focus group participants (n = 11) identified many positive aspects of VIEWER, including increased awareness and empowerment over health, simplicity of the data platform, and the ability to show clinical staff their health trends. Some challenges identified with VIEWER were connectivity issues with the Bluetooth, perceived inconvenience, and negative thoughts toward their health. Limitations: Limitations of the study include a small sample size, which limited our ability to measure quantitative outcomes. In addition, patients agreeing to participate in any trial are generally more highly motivated and engaged in their care than those declining participation. Therefore, our results may not be generalizable to individuals who are not interested in self-management of their health. Conclusion: Our results suggest that home telemonitoring in patients with advanced CKD is feasible using a CKD-specific platform like VIEWER. We anticipate that improved functionality with incorporation of feedback from this study will result in greater long-term adherence. A future randomized clinical trial is planned.

Contexte: Les visites aux urgences et les hospitalisations en lien avec l'insuffisance rénale augmentent d'environ dix fois dans les 30 jours qui précèdent le début de la dialyse. Objectif: L'essai VIEWER a mis en œuvre un système de télésurveillance à domicile qui permet de suivre les changements dans les paramètres vitaux des patients atteints d'insuffisance rénale chronique (IRC). L'essai permet également d'évaluer l'observance et l'acceptabilité de la télésurveillance dans cette population. Conception: Un essai clinique pilote prospectif utilisant une approche par méthodes mixtes. Cadre: Les recherches ont été menées à Winnipeg, au Manitoba. Sujets: L'essai s'est déroulé en deux phases: un essai pilote de deux semaines avec 10 participants (phase 1) et un essai de trois mois avec un total de 26 participants (phase 2). Étaient admissibles à participer: les patients présentant un DFGe inférieur à 15 ml/kg/1,73 m2 et une probabilité d'au moins 40 % d'amorcer des traitements de dialyse dans les deux ans, selon l'équation KFRE (kidney failure risk equation). Méthodologie: Le principal critère d'évaluation quantitatif était l'observance, définie par la proportion d'auto-évaluations réalisées quotidiennement à l'aide VIEWER au cours de la période de suivi. La facilité d'utilisation et l'acceptabilité de VIEWER ont été évaluées qualitativement à la fin de l'essai au moyen de questionnaires structurés et de groupes de discussion. Résultats: Les participants à la phase 1 (n=10) ont montré une observance médiane de 77,17 % pendant les deux semaines d'observation. Les participants à la phase 2 (n=26) ont montré une observance médiane inférieure, soit de 36 %, pendant les trois mois du suivi. Les participants au groupe de discussion (n=11) ont identifié plusieurs aspects positifs de VIEWER, notamment: une sensibilisation et une responsabilisation accrues à l'égard de la santé, la simplicité de la plateforme de données, et le fait de pouvoir montrer leurs tendances de santé au personnel clinique. Parmi les défis identifiés figurent des problèmes de connectivité avec Bluetooth, des désagréments perçus à son utilisation et des pensées négatives à l'égard de la santé. Limites: La faible taille des échantillons a limité notre capacité à mesurer les résultats quantitatifs. En outre, les patients qui acceptent de participer à un essai clinique sont généralement plus motivés et impliqués dans leurs soins que ceux qui refusent de participer. Par conséquent, nos résultats pourraient ne pas être généralisables aux personnes qui ne sont pas intéressées par l'autogestion de leur santé. Conclusion: Nos résultats suggèrent que la télésurveillance des patients atteints d'IRC avancée est réalisable par le biais d'une plateforme spécifique à l'IRC comme VIEWER. Nous pensons que l'amélioration de sa fonctionnalité, découlant des résultats de cette étude, se traduira par une plus grande observance à long terme. Un futur essai clinique randomisé est prévu.

The effective reproductive number: Modeling and prediction with application to the multi-wave Covid-19 pandemic.

Classical compartmental models of infectious disease assume that spread occurs through a homogeneous population. This produces poor fits to real data, because individuals vary in their number of epidemiologically-relevant contacts, and hence in their ability to transmit disease. In particular, network theory suggests that super-spreading events tend to happen more often at the beginning of an epidemic, which is inconsistent with the homogeneity assumption. In this paper we argue that a flexible decay shape for the effective reproductive number (Rt) indexed by the susceptible fraction (St) is a theory-informed modeling choice, which better captures the progression of disease incidence over human populations. This, in turn, produces better retrospective fits, as well as more accurate prospective predictions of observed epidemic curves. We extend this framework to fit multi-wave epidemics, and to accommodate public health restrictions on mobility. We demonstrate the performance of this model by doing a prediction study over two years of the SARS-CoV2 pandemic.

The Development of a Comprehensive Clinicopathologic Registry for Glomerular Diseases Using Natural Language Processing.

Background: Glomerulonephritis (GN) represents a common cause of chronic kidney disease, and treatment to slow or prevent progression of GN is associated with significant morbidity. Large patient registries have improved the understanding of risk stratification, treatment selection, and definitions of treatment response in GN, but can be resource-intensive, with incomplete patient capture. Objective: To describe the creation of a comprehensive clinicopathologic registry for all patients undergoing kidney biopsy in Manitoba, using natural language processing software for data extraction from pathology reports, as well as to describe cohort characteristics and outcomes. Design: Retrospective population-based cohort study. Setting: Tertiary care center in the province of Manitoba. Patients: All patients undergoing a kidney biopsy in the province of Manitoba from 2002 to 2019. Measurements: Descriptive statistics are presented for the most common glomerular diseases, along with outcomes of kidney failure and mortality for the individual diseases. Methods: Data from native kidney biopsy reports from January 2002 to December 2019 were extracted into a structured database using a natural language processing algorithm employing regular expressions. The pathology database was then linked with population-level clinical, laboratory, and medication data, creating a comprehensive clinicopathologic registry. Kaplan-Meier curves and Cox models were constructed to assess the relationship between type of GN and outcomes of kidney failure and mortality. Results: Of 2421 available biopsies, 2103 individuals were linked to administrative data, of which 1292 had a common glomerular disease. The incidence of yearly biopsies increased almost 3-fold over the study period. Among common glomerular diseases, immunoglobulin A (IgA) nephropathy was the most common (28.6%), whereas infection-related GN had the highest proportions of kidney failure (70.3%) and all-cause mortality (42.3%). Predictors of kidney failure included urine albumin-to-creatinine ratio at the time of biopsy (adjusted hazard ratio [HR] = 1.43, 95% confidence interval [CI] = 1.24-1.65), whereas predictors of mortality included age at the time of biopsy (adjusted HR = 1.05, 95% CI = 1.04-1.06) and infection-related GN (adjusted HR = 1.85, 95% CI = 1.14-2.99, compared with the reference category of IgA nephropathy). Limitations: Retrospective, single-center study with a relatively small number of biopsies. Conclusions: Creation of a comprehensive glomerular diseases registry is feasible and can be facilitated through the use of novel data extraction methods. This registry will facilitate further epidemiological research in GN.

Contexte: La glomérulonéphrite (GN) est une cause courante d'insuffisance rénale chronique. Le traitement pour ralentir ou prévenir la progression de la GN est associé à une morbidité significative. Les vastes registres de patients ont permis de mieux comprendre la stratification des risques, la sélection du traitement et les définitions de la réponse au traitement en contexte de GN, mais ces registres exigent beaucoup de ressources et la saisie des données du patient peut être incomplète. Objectifs: Décrire, à l'aide d'un logiciel de traitement en langage naturel pour l'extraction des données des rapports pathologiques, la création d'un registre clinicopathologique complet pour tous les patients subissant une biopsie rénale au Manitoba, et décrire les caractéristiques et les résultats de la cohorte. Conception: Étude de cohorte rétrospective basée sur la population. Cadre: Centre de soins tertiaires de la province du Manitoba. Sujets: Tous les patients ayant subi une biopsie rénale entre 2002 et 2019 au Manitoba. Mesures: Des statistiques descriptives sont présentées pour les maladies glomérulaires les plus courantes, accompagnées des résultats d'insuffisance rénale et de mortalité pour les maladies individuelles. Méthodologie: Les données des rapports de biopsie sur un rein natif entre janvier 2002 et décembre 2019 ont été extraites d'une base de données structurée à l'aide d'un algorithme de traitement en langage naturel utilisant des expressions régulières. La base de données des pathologies a ensuite été reliée aux données cliniques, de laboratoire et de médicaments au niveau de la population, pour créer un registre clinicopathologique complet. Des courbes Kaplan-Meier et des modèles de Cox ont été construits pour évaluer la relation entre le type de GN et les résultats d'insuffisance rénale et de mortalité. Résultats: Des 2 421 biopsies réalisées, 2 103 concernaient des individus liés à des données administratives; de ceux-ci, 1 292 étaient atteints d'une maladie glomérulaire courante. L'incidence des biopsies annuelles a presque été multipliée par trois au cours de la période étudiée. Parmi les maladies glomérulaires courantes, la néphropathie à IgA était la plus fréquente (28,6 %). Les GN liées à une infection présentaient les proportions les plus élevées d'insuffisance rénale (70,3 %) et de mortalité toutes causes confondues (42,3 %). Les facteurs prédictifs de l'insuffisance rénale comprenaient le rapport albumine/créatinine urinaire au moment de la biopsie (rapport de risque corrigé [RRc]: 1,43; intervalle de confiance à 95 % [IC 95 %]: 1,24-1,65), alors que les facteurs prédictifs de la mortalité incluaient l'âge au moment de la biopsie (RRc: 1,05; IC 95 %: 1,04-1,06) et les GN liées à une infection (RRc: 1,85; IC 95 %: 1,14-2,99; par rapport à la catégorie de référence de la néphropathie à IgA). Limites: Étude rétrospective menée dans un seul centre sur un nombre relativement faible de biopsies. Conclusion: La création d'un registre complet des maladies glomérulaires est réalisable et peut être facilitée par l'utilisation de nouvelles méthodes d'extraction des données. Ce registre facilitera de futures recherches épidémiologiques sur la GN. Enregistrement de l'essai: ne s'applique pas, cette étude n'est pas un essai clinique.

Defining Phylogenetic Network Distances Using Cherry Operations.

In phylogenetic networks, picking a cherry consists of removing a leaf that shares a parent with another leaf, or removing a reticulate edge whose endpoints are parents of leaves. Cherry-picking operations were recently shown to have several structural and algorithmic applications in the study of networks, for instance in determining their reconstructibility or in solving the network hybridization and network containment problems. In particular, some networks within certain classes are isomorphic if they can be reduced to a single node by the same sequence of cherry-picking operations. Therefore, cherry-picking sequences contain information on the level of similarity between two networks. In this paper, we expand on this idea by devising four novel distances on networks based on cherry picking and their reverse operation. We provide bounds between these distances and show that three of them are equal despite their different formulations. We also show that computing these three equivalent distances is NP-hard, even when restricted to comparing a tree and a network. On the positive side, we show that they can be computed in quadratic time on two trees, providing a new comparative measure for phylogenetic trees that can be computed efficiently.

Human-supervised clustering of multidimensional data using crowdsourcing.

Clustering is a central task in many data analysis applications. However, there is no universally accepted metric to decide the occurrence of clusters. Ultimately, we have to resort to a consensus between experts. The problem is amplified with high-dimensional datasets where classical distances become uninformative and the ability of humans to fully apprehend the distribution of the data is challenged. In this paper, we design a mobile human-computing game as a tool to query human perception for the multidimensional data clustering problem. We propose two clustering algorithms that partially or entirely rely on aggregated human answers and report the results of two experiments conducted on synthetic and real-world datasets. We show that our methods perform on par or better than the most popular automated clustering algorithms. Our results suggest that hybrid systems leveraging annotations of partial datasets collected through crowdsourcing platforms can be an efficient strategy to capture the collective wisdom for solving abstract computational problems.

BOPAL 2.0 and a study of tRNA and rRNA gene evolution in Clostridium.

We present BOPAL 2.0, an improved version of the BOPAL algorithm for the evolutionary history inference of tRNA and rRNA genes in bacterial genomes. Our approach can infer complete evolutionary scenarios and ancestral gene orders on a phylogeny and considers a wide range of events such as duplications, deletions, substitutions, inversions and transpositions. It is based on the fact that tRNA and rRNA genes are often organized in operons/clusters in bacteria, and this information is used to help identify orthologous genes for each genome comparison. BOPAL 2.0 introduces new features, such as a triple-wise alignment step, context-aware singleton matching and a second pass of the algorithm. Evaluation on simulated datasets shows that BOPAL 2.0 outperforms the original BOPAL in terms of the accuracy of inferred events and ancestral genomes. We also present a study of the tRNA/rRNA gene evolution in the Clostridium genus, in which the organization of these genes is very divergent. Our results indicate that tRNA and rRNA genes in Clostridium have evolved through numerous duplications, losses, transpositions and substitutions, but very few inversions were inferred.

Operon-based approach for the inference of rRNA and tRNA evolutionary histories in bacteria.

BACKGROUND: In bacterial genomes, rRNA and tRNA genes are often organized into operons, i.e. segments of closely located genes that share a single promoter and are transcribed as a single unit. Analyzing how these genes and operons evolve can help us understand what are the most common evolutionary events affecting them and give us a better picture of ancestral codon usage and protein synthesis. RESULTS: We introduce BOPAL, a new approach for the inference of evolutionary histories of rRNA and tRNA genes in bacteria, which is based on the identification of orthologous operons. Since operons can move around in the genome but are rarely transformed (e.g. rarely broken into different parts), this approach allows for a better inference of orthologous genes in genomes that have been affected by many rearrangements, which in turn helps with the inference of more realistic evolutionary scenarios and ancestors. CONCLUSIONS: From our comparisons of BOPAL with other gene order alignment programs using simulated data, we have found that BOPAL infers evolutionary events and ancestral gene orders more accurately than other methods based on alignments. An analysis of 12 Bacillus genomes also showed that BOPAL performs just as well as other programs at building ancestral histories in a minimal amount of events.

Reconstruction of ancestral RNA sequences under multiple structural constraints.

BACKGROUND: Secondary structures form the scaffold of multiple sequence alignment of non-coding RNA (ncRNA) families. An accurate reconstruction of ancestral ncRNAs must use this structural signal. However, the inference of ancestors of a single ncRNA family with a single consensus structure may bias the results towards sequences with high affinity to this structure, which are far from the true ancestors. METHODS: In this paper, we introduce achARNement, a maximum parsimony approach that, given two alignments of homologous ncRNA families with consensus secondary structures and a phylogenetic tree, simultaneously calculates ancestral RNA sequences for these two families. RESULTS: We test our methodology on simulated data sets, and show that achARNement outperforms classical maximum parsimony approaches in terms of accuracy, but also reduces by several orders of magnitude the number of candidate sequences. To conclude this study, we apply our algorithms on the Glm clan and the FinP-traJ clan from the Rfam database. CONCLUSIONS: Our results show that our methods reconstruct small sets of high-quality candidate ancestors with better agreement to the two target structures than with classical approaches. Our program is freely available at: http://csb.cs.mcgill.ca/acharnement .

Evolution of tRNA Repertoires in Bacillus Inferred with OrthoAlign.

OrthoAlign, an algorithm for the gene order alignment problem (alignment of orthologs), accounting for most genome-wide evolutionary events such as duplications, losses, rearrangements, and substitutions, was presented. OrthoAlign was used in a phylogenetic framework to infer the evolution of transfer RNA repertoires of 50 fully sequenced bacteria in the Bacillus genus. A prevalence of gene duplications and losses over rearrangement events was observed. The average rate of duplications inferred in Bacillus was 24 times lower than the one reported in Escherichia coli, whereas the average rates of losses and inversions were both 12 times lower. These rates were extremely low, suggesting a strong selective pressure acting on tRNA gene repertoires in Bacillus. An exhaustive analysis of the type, location, distribution, and length of evolutionary events was provided, together with ancestral configurations. OrthoAlign can be downloaded at: http://www.iro.umontreal.ca/~mabrouk/.

A graph-theoretic approach for inparalog detection.

Understanding the history of a gene family that evolves through duplication, speciation, and loss is a fundamental problem in comparative genomics. Features such as function, position, and structural similarity between genes are intimately connected to this history; relationships between genes such as orthology (genes related through a speciation event) or paralogy (genes related through a duplication event) are usually correlated with these features. For example, recent work has shown that in human and mouse there is a strong connection between function and inparalogs, the paralogs that were created since the speciation event separating the human and mouse lineages. Methods exist for detecting inparalogs that either use information from only two species, or consider a set of species but rely on clustering methods. In this paper we present a graph-theoretic approach for finding lower bounds on the number of inparalogs for a given set of species; we pose an edge covering problem on the similarity graph and give an efficient 2/3-approximation as well as a faster heuristic. Since the physical position of inparalogs corresponding to recent speciations is not likely to have changed since the duplication, we also use our predictions to estimate the types of duplications that have occurred in some vertebrates and drosophila.

Evolution of orthologous tandemly arrayed gene clusters.

BACKGROUND: Tandemly Arrayed Gene (TAG) clusters are groups of paralogous genes that are found adjacent on a chromosome. TAGs represent an important repertoire of genes in eukaryotes. In addition to tandem duplication events, TAG clusters are affected during their evolution by other mechanisms, such as inversion and deletion events, that affect the order and orientation of genes. The DILTAG algorithm developed in 1 makes it possible to infer a set of optimal evolutionary histories explaining the evolution of a single TAG cluster, from an ancestral single gene, through tandem duplications (simple or multiple, direct or inverted), deletions and inversion events. RESULTS: We present a general methodology, which is an extension of DILTAG, for the study of the evolutionary history of a set of orthologous TAG clusters in multiple species. In addition to the speciation events reflected by the phylogenetic tree of the considered species, the evolutionary events that are taken into account are simple or multiple tandem duplications, direct or inverted, simple or multiple deletions, and inversions. We analysed the performance of our algorithm on simulated data sets and we applied it to the protocadherin gene clusters of human, chimpanzee, mouse and rat. CONCLUSIONS: Our results obtained on simulated data sets showed a good performance in inferring the total number and size distribution of duplication events. A limitation of the algorithm is however in dealing with multiple gene deletions, as the algorithm is highly exponential in this case, and becomes quickly intractable.