Randomized Controlled Trials (RCTs) are the gold standard for evaluating the effect of new medical treatments. Treatments must pass stringent regulatory conditions in order to be approved for widespread use, yet even after the regulatory barriers are crossed, real-world challenges might arise: Who should get the treatment? What is its true clinical utility? Are there discrepancies in the treatment effectiveness across diverse and under-served populations? We introduce two new objectives for future clinical trials that integrate regulatory constraints and treatment policy value for both the entire population and under-served populations, thus answering some of the questions above in advance. Designed to meet these objectives, we formulate Randomize First Augment Next (RFAN), a new framework for designing Phase III clinical trials. Our framework consists of a standard randomized component followed by an adaptive one, jointly meant to efficiently and safely acquire and assign patients into treatment arms during the trial. Then, we propose strategies for implementing RFAN based on causal, deep Bayesian active learning. Finally, we empirically evaluate the performance of our framework using synthetic and real-world semi-synthetic datasets.

MOTIVATION: Polygenic risk scores (PRSs) predict individuals' genetic risk of developing complex diseases. They summarize the effect of many variants discovered in genome-wide association studies (GWASs). However, to date, large GWASs exist primarily for the European population and the quality of PRS prediction declines when applied to other ethnicities. Genetic profiling of individuals in the discovery set (on which the GWAS was performed) and target set (on which the PRS is applied) is typically done by SNP arrays that genotype a fraction of common SNPs. Therefore, a key step in GWAS analysis and PRS calculation is imputing untyped SNPs using a panel of fully sequenced individuals. The imputation results depend on the ethnic composition of the imputation panel. Imputing genotypes with a panel of individuals of the same ethnicity as the genotyped individuals typically improves imputation accuracy. However, there has been no systematic investigation into the influence of the ethnic composition of imputation panels on the accuracy of PRS predictions when applied to ethnic groups that differ from the population used in the GWAS. RESULTS: We estimated the effect of imputation of the target set on prediction accuracy of PRS when the discovery and the target sets come from different ethnic groups. We analyzed binary phenotypes on ethnically distinct sets from the UK Biobank and other resources. We generated ethnically homogenous panels, imputed the target sets, and generated PRSs. Then, we assessed the prediction accuracy obtained from each imputation panel. Our analysis indicates that using an imputation panel matched to the ethnicity of the target population yields only a marginal improvement and only under specific conditions. AVAILABILITY AND IMPLEMENTATION: The source code used for executing the analyses is this paper is available at https://github.com/Shamir-Lab/PRS-imputation-panels.

MOTIVATION: Active module identification (AMI) is an essential step in many omics analyses. Such algorithms receive a gene network and a gene activity profile as input and report subnetworks that show significant over-representation of accrued activity signal ('active modules'). Such modules can point out key molecular processes in the analyzed biological conditions. RESULTS: We recently introduced a novel AMI algorithm called DOMINO and demonstrated that it detects active modules that capture biological signals with markedly improved rate of empirical validation. Here, we provide an online server that executes DOMINO, making it more accessible and user-friendly. To help the interpretation of solutions, the server provides GO enrichment analysis, module visualizations and accessible output formats for customized downstream analysis. It also enables running DOMINO with various gene identifiers of different organisms. AVAILABILITY AND IMPLEMENTATION: The server is available at http://domino.cs.tau.ac.il. Its codebase is available at https://github.com/Shamir-Lab.

MOTIVATION: Bacteriophages and plasmids usually coexist with their host bacteria in microbial communities and play important roles in microbial evolution. Accurately identifying sequence contigs as phages, plasmids and bacterial chromosomes in mixed metagenomic assemblies is critical for further unraveling their functions. Many classification tools have been developed for identifying either phages or plasmids in metagenomic assemblies. However, only two classifiers, PPR-Meta and viralVerify, were proposed to simultaneously identify phages and plasmids in mixed metagenomic assemblies. Due to the very high fraction of chromosome contigs in the assemblies, both tools achieve high precision in the classification of chromosomes but perform poorly in classifying phages and plasmids. Short contigs in these assemblies are often wrongly classified or classified as uncertain. RESULTS: Here we present 3CAC, a new three-class classifier that improves the precision of phage and plasmid classification. 3CAC starts with an initial three-class classification generated by existing classifiers and improves the classification of short contigs and contigs with low confidence classification by using proximity in the assembly graph. Evaluation on simulated metagenomes and on real human gut microbiome samples showed that 3CAC outperformed PPR-Meta and viralVerify in both precision and recall, and increased F1-score by 10-60 percentage points. AVAILABILITY AND IMPLEMENTATION: The 3CAC software is available on https://github.com/Shamir-Lab/3CAC. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Sequencing long reads presents novel challenges to mapping. One such challenge is low sequence similarity between the reads and the reference, due to high sequencing error and mutation rates. This occurs, e.g., in a cancer tumor, or due to differences between strains of viruses or bacteria. A key idea in mapping algorithms is to sketch sequences with their minimizers. Recently, syncmers were introduced as an alternative sketching method that is more robust to mutations and sequencing errors. RESULTS: We introduce parameterized syncmer schemes (PSS), a generalization of syncmers, and provide a theoretical analysis for multi-parameter schemes. By combining PSS with downsampling or minimizers we can achieve any desired compression and window guarantee. We implemented the use of PSS in the popular minimap2 and Winnowmap2 mappers. In tests on simulated and real long-read data from a variety of genomes, the PSS-based algorithms, with scheme parameters selected on the basis of our theoretical analysis, reduced unmapped reads by 20-60% at high compression while usually using less memory. The advantage was more pronounced at low sequence identity. At sequence identity of 75% and medium compression, PSS-minimap had only 37% as many unmapped reads, and 8% fewer of the reads that did map were incorrectly mapped. Even at lower compression and error rates, PSS-based mapping mapped more reads than the original minimizer-based mappers as well as mappers using the original syncmer schemes. We conclude that using PSS can improve mapping of long reads in a wide range of settings.

The International Society for Computational Biology (ISCB) recognizes the achievements of an early to mid-career scientist each year with the Overton Prize. This prize honors the untimely death of Dr. G. Christian Overton, a respected computational biologist and founding ISCB Board member. The Overton Prize recognizes independent investigators who are in the early to middle phases of their careers and are selected because of their significant contributions to computational biology through research, teaching and service. ISCB is pleased to recognize Dr. Jian Peng, Assistant Professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign as the 2020 winner of the Overton Prize. Peng will be presenting a keynote presentation at the 2020 International Conference on Intelligent Systems for Molecular Biology virtual meeting being held on July 13–16, 2020. Jian Peng grew up in Yichang, Hubei Province, China to parents who were both university professors. His earliest memories include taking pleasure in his time spent reading from his parents’ home library, even when he could not fully comprehend the content of some the books. He recalled, ‘My parents were college professors, who always gave me the freedom to choose what I liked to do.’ Peng was 10 years old when his parents gave him his first personal computer. He was quickly drawn to computer programming. He spent many hours teaching himself to program and read programming books on C/C++, Windows and data structures. In high school, Peng became interested in chemistry, but he returned to his early interest in computer programming while pursuing his bachelor’s and master’s degrees in computer science at Wuhan University. As an undergraduate, Peng became deeply interested in mathematical logic and its applications to programming languages and wanted to pursue this topic in graduate school. He said, ‘I didn’t find many places to study this topic. I was fortunate to meet with Professor Jinbo Xu, who was giving a bioinformatics talk at Tsinghua University and kindly showed me several fascinating papers, including his seminal work on the protein side chain packing problem. He suggested that I spend time reading textbooks on machine learning (ML), as he believed that ML would become a very useful tool in computational biology when more data become available.’ Peng went on to complete his PhD in 2013 at the Toyota Technological Institute at Chicago under Xu, where his research focused on protein structure prediction and modeling using ML methods. These methods, which are known as RaptorX and are still widely used today, have excelled at alignments of hard targets. Peng then joined Bonnie Berger’s lab as a post-doc and expanded his research scope to include systems biology and functional genomics. He recalled, ‘We have had a great time working on a variety of problems, including structural bioinformatics, compressive genomics, systems biology and disease genomics. I also really appreciated my time in the lab of (the late) Susan Lindquist, where I learned a lot from experimental and wet lab biologists and found ways to help address important problems in neurodegenerative diseases using my computational skills.’ He is deeply appreciative of his mentorship under Xu, Berger and Lindquist not just for the areas of research he worked on with them but also for the lessons he learned in conducting experiments correctly and with rigor. In 2015, Peng was appointed as an assistant professor in the Department of Computer Science, and affiliated with the College of Medicine, at the University of Illinois at Urbana-Champaign. Peng’s perspective in identifying new research topics has evolved with his maturation as an academic. As a student, he was more drawn to problems that he thought were highly interesting, or he was swayed by the ‘coolness’ of a method. Now Peng appreciates that his research interests must also address important scientific problems, and he feels it is critical to convey this concept to his trainees as they apply their knowledge in computation and biology to solve problems that deeply interest them. Through his research experiences, Peng has learned that scientists are often surprised by unexpected findings. He said, ‘What I’ve learned in these years from successes and failures is how capable (and incapable) computational methods can be. Like many artificial intelligence/ML researchers, I was initially focused on developing powerful ML models for problems with large datasets, which hopefully can provide us new biological insights. However, in many important problems, such as those related to protein function and design, disease mutations studies and functional genomics, the effective sample sizes are much smaller than what we expect for ML.’ Peng’s research has always been driven by understanding the sequence-structure-function relationship. Currently, Peng’s research has shifted directions toward using biological insights for developing advanced ML models. Like Bayesian methods, he uses known biological insights to serve as the ‘structural’ prior to constrain ML models and generate new hypotheses in line with existing knowledge. Two recent notable projects in this line are the DeepContact algorithm for protein contact map prediction and the Mashup algorithm (with Berger and Cho) for heterogeneous biological network data integration. He is interested in understanding the functional and structural consequences of protein mutations. Peng appreciates the importance of this area in terms of designing proteins with better and more biologically relevant functions, but also improving the annotation of missense mutations in human genomes for gaining insights in molecular mechanisms of human diseases. Peng is greatly humbled and honored to receive the 2020 ICSB Overton Prize as it is a recognition from his peers within the ISCB community, and he shares his gratitude with the mentors, students and collaborators that have brought his work to fruition.

The International Society for Computational Biology (ISCB) Innovator Award recognizes a scientist who is within two decades of completing her or his graduate degree and has made significant contributions to the field of computational biology. The 2020 awardee is Dr. Xiaole Shirley Liu, Professor of Biostatistics and Computational Biology at the Harvard T.H. Chan School of Public Health and Co-Director of the Center for Functional Cancer Epigenetics at the Dana-Farber Cancer Institute. Liu will be recognized for her award and deliver a keynote presentation at the 2020 ISMB virtual meeting on July 13–16, 2020. X. Shirley Liu grew up in Tianjin, China and her elder brother sparked her interest in biology at an early age. She transferred from Peking University during her freshman year to pursue her undergraduate degree at Smith College in the USA. Liu was working toward a degree in biochemistry when she took a basic computer literacy course. From that class, Liu became drawn to computer programing and quickly immersed herself in computer science courses in her junior year. In summer 1996, she had a transformative experience, she recalled, ‘At the recommendations of my advisors Jeanne Powell and Steven Williams, I went to a University of Washington summer workshop in bioengineering and visited several universities in the West Coast. The visit to Stanford helped me realize how I could combine computer science and biology.’ Liu graduated summa com laude from Smith College in 1997 with a double major in biochemistry and computer science. She pursued a PhD in the nascent field of biomedical informatics, with a minor in computer science, at Stanford University. At the time, Pat Brown and Ron Davis’ laboratories developed DNA microarrays to study gene expression, transcription regulation and protein-DNA interactions. Under the guidance of her PhD advisors Douglas Brutlag and Jun Liu, she developed algorithms for finding protein-DNA binding motifs (BioProspector, MDscan and MotifRegressor) from co-expressed gene clusters and chromatin-immunoprecipitation microarrays. Liu accepted a faculty position right after PhD and became an assistant professor in the Department of Biostatistics and Computational Biology in the Dana-Farber Cancer Institute/Harvard School of Public Health in 2003. She recalled, ‘I was very lucky to collaborate with many wonderful colleagues at Harvard, especially with Myles Brown early in my faculty career. We share research interests in gene regulation and both believe the power of technology. Myles showed me how to use technologies cost effectively to tackle interesting biological problems, how to be open-minded when data lead us to unexpected results, and how to understand the mechanisms underlying our observations.’ They developed numerous algorithms and tools (MAT, MACS, Cistrome, LISA and MAESTRO) to model transcription factor binding and chromatin dynamics that are important to understand gene regulation in development and diseases. Liu and Brown continue to be close collaborators and have published around 70 papers together. As a member of the ENCODE consortium, Shirley Liu’s Lab continued to maintain and update these algorithms and tools, which have helped many other scientists adopt new genomics technologies and generate hypotheses. Liu became drawn to translational cancer research in 2012 after reading the Pulitzer Prize winning book, The Emperor of All Maladies, by Siddhartha Mukherjee. She had just been tenured and wanted to broaden her research areas and take more risks in her projects. Liu developed new methods (MAGeCK) to design and analyze genome-wide CRISPR/Cas9 knockout screens. Her team used computational approaches integrating large-scale compound and genetic screens, as well as functional genomics profiles from cancer cell lines and tumor cohorts, to refine our understanding of hormone receptor therapies, epigenetic inhibitors, gamma-secretase inhibitors, receptor tyrosine kinase inhibitors and immune checkpoint inhibitors in different cancers. She also developed novel algorithms TIMER and TRUST to comprehensively characterize tumor-infiltrating immune cells and immune receptor repertoires in over 10 000 tumors from The Cancer Genome Atlas. Liu continues to make significant contributions to cancer gene regulation. Liu is the principal investigator of the Cancer Immunologic Data Commons, a part of the NCI Cancer Moonshot project that aims to develop better cancer immunotherapy biomarkers and optimize treatment strategies. Liu considers her role as a mentor to be a critical part of her job. She said, ‘I want trainees to explore projects that build on their interests and previous expertise and combine that with my lab’s knowledge on gene regulation. This helps each trainee to develop a unique identity.’ She has already mentored 18 trainees who have moved on to tenure track faculty positions and continues to welcome a diverse array of trainees with computational and experimental expertise. Liu is a highly cited researcher with a prodigious publication record that includes more than 200 papers published by her group, many of them in high-profile journals and highly cited. Liu has served on the editorial boards of leading genomic and computational biology journals throughout her career. She has also served on a number of conference organizing committees and study sections. She received the Sloan Research Fellowship (2008), has been a Breast Cancer Research Foundation Investigator (2017) and became a Fellow of ISCB (2019). Liu’s open-access resources were recognized with the Benjamin Franklin Award for Open Access in the Life Sciences in 2020. Liu feels deeply honored to be recognized with the ISCB Innovator Award, especially as it comes from her peers in computational biology. She is inspired to continue pursuing projects that advance our understanding of basic biology and can be translated into clinical benefits to cancer patients.

The Outstanding Contributions to IISCB honors a leader in the fields of computational biology and bioinformatics each year with the Accomplishments by a Senior Scientist Award. This award is the highest honor conferred by ISCB to a scientist who is recognized for significant research, education, and service contributions. Steven L. Salzberg, Bloomberg Distinguished Professor of Biomedical Engineering, Computer Science and Biostatistics at Johns Hopkins University and Director of the Center for Computational Biology, is being honored as the 2020 winner of the ISCB Accomplishments by a Senior Scientist Award. He will be recognized and give a keynote address at ISMB 2020 virtual conference being held on July 13–16, 2020. Steven Salzberg grew up in Columbia, SC. Throughout his childhood and young adulthood, he was always interested in science and deeply enjoyed reading science fiction. Salzberg was also fascinated by astronomy and considered studying physics. As an undergraduate at Yale University in the 1970’s, he explored several majors and thought he had settled on English Literature but added Computer Science as a second major upon taking an introductory computer programming class. He recalled, ‘This is the kind of math I thought I would really like to study’, and he was soon captivated by artificial intelligence (AI) and natural language processing. At the advice of his undergraduate advisor, Salzberg spent a year after graduation gaining more programming experience by working at a local power company in South Carolina, where he worked on an IBM mainframe and used self-training courses to learn COBOL and IBM assembler. Salzberg said, ‘It was a very boring sort of application, but I was still interested in programming. I liked the idea I could work on something technical and within a short period of time, I would have results that would do what I intended’. Salzberg returned to Yale and completed his M.S. in computer science. He then joined a startup in Boston during the first blush of AI, although this and many other AI startups failed in the late 1980’s due to lack of computing power and other technical limitations. One of Salzberg’s advisors at the startup was AI pioneer Bill Woods, who held an adjunct appointment at Harvard University and later became Salzberg’s graduate advisor in the Department of Computer Science. Salzberg had managed to avoid taking any biology classes as an undergraduate, but he heard about the Human Genome Project (HGP) while he was in graduate school in the late 1980’s. He said, ‘The Human Genome Project sounded like the most exciting thing in all of science at the time, and I wanted to be a part of that’. While completing his PhD project in machine learning, he started sitting in on biology classes, including a course by the late Stephen Jay Gould and reading on his own to learn about genomics and genetics. He was determined to figure out a way to using his computing knowledge to get involved in the HGP. Salzburg continued doing research in machine learning as he started in his first academic position at Johns Hopkins University. He was still curious about genomics and recalled going to a talk in the early 1990’s by Temple Smith about sequence differences between exons and introns. It dawned on Salzberg that he could use machine learning to distinguish exons from introns, which could be used as a strategy for gene finding. This became Salzberg’s entrance into genomics. During this time, Salzberg was also introduced to Nobel Laureate Hamilton Smith, a notable microbiologist who discovered type II restriction enzymes. Salzberg recalled, ‘[Smith] had a secret passion for computer programming. He wanted to talk to computer scientists who were interested in genomics—that was me. And I was interested in learning more about genomics’. Salzberg and Smith began working together to understand how computer programs could be made for tasks like gene finding. Smith had also started collaborating with J. Craig Venter, and in 1997, both Smith and Salzberg began working at Venter’s non-profit research institute, The Institute for Genomic Research (TIGR). Salzberg became the Director of Bioinformatics at TIGR and developed with his colleague Art Delcher the GLIMMER gene finder, a software system still used today to identify coding regions in bacteria, archea and viruses. In the early 2000’s, the first Mycobacterium tuberculosis genomes were being sequenced by both TIGR and The Sanger Center. This led Salzberg and his colleagues to develop MUMmer, a system that could be used to compare large genomes. He also got involved in the HGP through the development of a gene finder that could analyze the human genome and, with his colleague Mihaela Pertea, also built other eukaryotic gene finders for plant, fungus and parasite genomes. Salzberg and his colleagues were called upon by the FBI after the 2001 anthrax attacks to analyze the genome of the anthrax bacteria, and that work identified genetic mutations that eventually pinpointed the source of the bacteria to a biodefense lab in Fort Detrick, Maryland. In 2003, Salzberg co-founded the Influenza Genome Sequencing project with David Lipman, which involved the sequencing and analysis of thousands of influenza isolates. Salzberg then moved to the University of Maryland, College Park in 2005, where he was the Horvitz Professor of Computer Science. He returned to JHU in 2011, where he is currently the Bloomberg Distinguished Professor of Biomedical Engineering, Computer Science and Biostatistics and the Director of the Center for Computational Biology in the Whiting School of Engineering. As next-generation sequencing technology developed, Salzberg’s research interests shifted toward developing algorithms for large-scale genome assembly and sequence alignment, including the development of the open-source Tuxedo suite of programs (Bowtie, Tophat and Cufflinks). Salzberg’s current interests include the development of an improved human gene catalog and assembly and annotation of an Ashkenazi human reference genome. Recent technical advances have made this undertaking feasible, and the research community has desperately needed other reference genomes beyond the only publicly available genome, GRCh38. Salzberg is also working with colleagues on developing methods for using shotgun sequencing as a diagnostic tool for infectious diseases. They have tested their techniques on biopsy materials from patients with difficult-to-diagnose brain infections and on samples collected from eye infections, and the technology has the potential to work on a much broad range of infections. Salzberg has trained numerous students and post-doctoral fellows throughout his time in academia and at TIGR, and he has focused on matching highly motivated individuals with projects that get them excited. Like many computational biologists, Salzberg is continually in search of interesting data associated with problems that matter, whether they involve the nature of the human genome, human health and disease, or any of a much broader range of microbial, plant and animal genomes. Salzberg’s body of work includes more than 300 publications, including many highly cited manuscripts. His contributions have been recognized through his election as a member of the American Academy of Arts and Sciences, a Fellow of the American Association for the Advancement of Science, a Fellow of the International Society for Computational Biology (ISCB) and a member of the Board of Scientific Counselors of the National Library of Medicine at NIH. All of Salzberg’s bioinformatics systems have been released as free, open-source software and he won the 2013 Benjamin Franklin Award for Open Science for his advocacy of open-source software and of open sharing of genome sequence data. Salzberg is also a contributor to Forbes magazine and writes a widely read column that debunks pseudoscience and explains scientific and medical findings with honesty and clarity. Salzberg is greatly honored to be the 2020 recipient of ISCB’s Accomplishments by a Senior Scientist award. He has always felt at home at ISMB meetings since their inception and is touched by this award since it is bestowed upon him by his computational biology colleagues.

The Outstanding Contributions to the International Society of Computational Biology (ISCB) Award recognizes outstanding service contributions to the Society by any member through exemplary leadership, education, service, or a combination of these three elements. Judith Blake, Professor at the Jackson Laboratory in Bar Harbor, ME, USA is the 2020 winner of the Outstanding Contributions to ISCB Award and will be recognized at the 2020 ISMB virtual meeting being held on July 13–16, 2020. Judith Blake has spent most of her career at the Jackson Laboratory in Bar Harbor, ME, USA developing bioinformatics systems for integrating genetic, genomic and phenotypic information and working to make data from different genomes more accessible for genomics and genetics research. Early in Blake’s career at the Jackson Laboratory, she became a principal investigator with the Mouse Genome Informatics (MGI) project, a widely used international open access database resource for the laboratory mouse, providing integrated genetic, genomic and biological data to facilitate the study of human health and disease. Blake’s work on the MGI led to her interest in bio-ontologies. During the 1998 ISMB meeting, she and other colleagues working on genome projects in different model organisms recognized a need for open access bio-ontologies, which are controlled structured vocabularies for molecular biology that support the comparison of data across different genomes. She is one of the founding principal investigators and one of current leaders of the Gene Ontology (GO) Consortium group. Together with her research team, she has spent many years contributing to development of bio-ontology systems and to supporting integration of functional genomics data for mouse, in particular, within MGI and the GO project. Beyond Blake’s contributions to the bioinformatics and data curation communities, she has served ISCB in many ways. She recalls attending the first ISMB meeting at the National Library of Medicine in Bethesda, MD, USA in 1993, which led to the eventual formation of ISCB. Blake said, ‘Here, I found a community of investigators actively engaged in creating new tools and approaches to computational scientific investigations. My colleagues in ISCB shared my excitement as new innovations were developed to understand molecular systems and data’. She has come to appreciate how ISCB brings together scientists from academia, industry and technology in an open and supportive environment that fosters the building of new tools to advance the understanding of biological systems. Blake has served on the ISCB Board of Directors and chaired the ISCB Public Affairs and Policy committee, as well as working on other program and review committees. She has also represented ISCB on the Federation of American Societies for Experimental Biology Board of Directors. Blake sees many benefits in pursuing scientific service opportunities and said, ‘I encourage young scientists and trainees to engage in those ISCB activities that match their passions. The opportunity to support their colleagues and to engage in a scientific network will both enhance the interactions of a global network of scientists but will also bring new insights to their own scientific investigations’.

MOTIVATION: Problems of genome rearrangement are central in both evolution and cancer research. Most genome rearrangement models assume that the genome contains a single copy of each gene and the only changes in the genome are structural, i.e. reordering of segments. In contrast, tumor genomes also undergo numerical changes such as deletions and duplications, and thus the number of copies of genes varies. Dealing with unequal gene content is a very challenging task, addressed by few algorithms to date. More realistic models are needed to help trace genome evolution during tumorigenesis. RESULTS: Here, we present a model for the evolution of genomes with multiple gene copies using the operation types double-cut-and-joins, duplications and deletions. The events supported by the model are reversals, translocations, tandem duplications, segmental deletions and chromosomal amplifications and deletions, covering most types of structural and numerical changes observed in tumor samples. Our goal is to find a series of operations of minimum length that transform one karyotype into the other. We show that the problem is NP-hard and give an integer linear programming formulation that solves the problem exactly under some mild assumptions. We test our method on simulated genomes and on ovarian cancer genomes. Our study advances the state of the art in two ways: It allows a broader set of operations than extant models, thus being more realistic and it is the first study attempting to re-construct the full sequence of structural and numerical events during cancer evolution. AVAILABILITY AND IMPLEMENTATION: Code and data are available in https://github.com/Shamir-Lab/Sorting-Cancer-Karyotypes. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Evolution of cancer is driven by few somatic mutations that disrupt cellular processes, causing abnormal proliferation and tumor development, whereas most somatic mutations have no impact on progression. Distinguishing those mutated genes that drive tumorigenesis in a patient is a primary goal in cancer therapy: Knowledge of these genes and the pathways on which they operate can illuminate disease mechanisms and indicate potential therapies and drug targets. Current research focuses mainly on cohort-level driver gene identification but patient-specific driver gene identification remains a challenge. METHODS: We developed a new algorithm for patient-specific ranking of driver genes. The algorithm, called PRODIGY, analyzes the expression and mutation profiles of the patient along with data on known pathways and protein-protein interactions. Prodigy quantifies the impact of each mutated gene on every deregulated pathway using the prize-collecting Steiner tree model. Mutated genes are ranked by their aggregated impact on all deregulated pathways. RESULTS: In testing on five TCGA cancer cohorts spanning >2500 patients and comparison to validated driver genes, Prodigy outperformed extant methods and ranking based on network centrality measures. Our results pinpoint the pleiotropic effect of driver genes and show that Prodigy is capable of identifying even very rare drivers. Hence, Prodigy takes a step further toward personalized medicine and treatment. AVAILABILITY AND IMPLEMENTATION: The Prodigy R package is available at: https://github.com/Shamir-Lab/PRODIGY. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

ISCB honors a leader in the fields of computational biology and bioinformatics each year with the Accomplishments by a Senior Scientist Award. This award is the highest honor conferred by ISCB to a scientist who is recognized for significant research, education and service contributions. Bonnie Berger, Simons Professor of Mathematics and Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology (MIT), is the 2019 recipient of the Accomplishments by a Senior Scientist Award. She is receiving her award and presenting a keynote address at the 2019 Joint International Conference on Intelligent Systems for Molecular Biology/European Conference on Computational Biology in Basel, Switzerland on July 21–25, 2019. Bonnie Berger grew up in Miami, Florida with her parents and older brother and has early memories of being curious about mathematics. She recalled, ‘As a young child, I responded, ‘I want one too, please’, when my father slipped math problems under my brother’s door. My father would continue to challenge me with math riddles and chess puzzles. He would also engage me in science projects. Our relationship laid the foundation for my comfort with, and interest in, math and science, even though it was not so common for girls at the time’. Berger’s early interest in math and science led her to complete her AB in computer science at Brandeis University. In 1990, she completed her PhD in computer science at MIT under the mentorship of Silvio Micali. Berger’s dissertation research on randomized and parallel algorithms was recognized by the Machtey Award for a manuscript that she co-published with fellow graduate student John Rompel, as well as the George M. Sprowles Award. After graduate school, Berger remained at MIT and stumbled upon computational biology quite unexpectedly. She recounted, ‘My postdoc supervisor Daniel J. Kleitman, who has Erdos #1 and solved dynamic programming for RNA base-pairings with Ruth Nussinov, had just come back from an NSF workshop whose goal was to get mathematicians and biologists together to solve challenges at the interface between the two fields. He was so taken with Michael Levitt’s talk that he said, ‘Proteins, that’s what you should do’. Well, fortunately, he didn’t say, ‘Plastics’, as in ‘The Graduate’, or I might have ended up a material scientist’. She appreciates the freedom she had as a postdoc and took to heart the advice Kleitman gave her when he told her, ‘We are applied mathematicians looking for interesting problems to investigate’. Following her postdoc, Berger became an Assistant Professor of Mathematics at MIT, and as a PI, she has pioneered the use of computer algorithms for analyzing, interpreting and sharing diverse types of biological data. Among Berger’s scientific contributions, she developed the use of pairwise residue correlations to predict protein structure from sequence through her highly cited Paircoil/Multicoil programs. Her seminal work on the hardness of protein folding was recognized with the 2010 RECOMB Test of Time Award. Berger’s interest in genomics included development of the ARACHNE genome assembly tool, which was used by the Human Genome Consortium for whole genome assembly. She also initiated the area of comparative genomics with her cutting-edge work comparing human and mouse genomes. Berger launched the subfield of global network alignment with her Isorank/IsorankN programs and advanced protein structure alignment with her MATT program. More recently, Berger has founded the field of compressive genomics by designing algorithms that can be used for genomic analysis on compressed data in order to keep pace with data generation. She has also spearheaded efforts to improve biomedical data privacy, including the development of tools to securely crowdsource genomic and pharmacological data at scale. Berger considers her theoretical computer science background to be critical to her success in identifying and studying computational biology problems. She said, ‘I have realized that with my algorithms background and flexibility, I can easily shift between areas as the research landscape changes. As I gain knowledge across diverse research areas, I can see connections between them and techniques that can be used to address them’. Berger has also come to appreciate the many mentors that helped her bridge the gap between computer science and biology, including Peter Shor, Peter S. Kim and Jonathan King. She recalled, ‘[They] taught me biology on a need-to-know basis. It took many rounds of back-and-forth by, would you believe, fax machine with Peter Kim for me to turn my early Paircoil writeup from definitions and theorems to one accessible to a biology audience’. Berger has trained numerous graduate students and postdocs, using an approach she learned from her NSF Postdoc supervisor. She said, ‘[Kleitman] gave me a lot of freedom to pursue whatever interested me, and that’s how I mentor my students. I ask them what interests them and suggest several research problems, or I encourage them to bring entirely new research areas to us’. Many of her trainees have become leaders in the field of computational biology. Berger is also fascinated by developing methods to improve data sharing and said, ‘I am interested in individuals, labs and companies owning rights to their own data but providing provably secure algorithms so that they can for the first time share their data at scaleto enable biomedical insights across different nations and diverse data. Recently, I am interested in developing sketching algorithms that take advantage of the geometry of single-cell RNA-seq data to better share, analyze and draw insights from the data’. Berger has served the computational biology community in many capacities, including her roles as Vice President of ISCB and Head of the RECOMB Steering Committee; as well as her service on multiple editorial boards, and program and conference committees. Her scientific contributions have been recognized by numerous awards, including the NSF Career Award, Biophysical Society Dayhoff Award for Research, inaugural Technology Review Top 100 Innovators, ACM Fellow, ISCB Fellow, AMS Fellow, AIMBE Fellow, NIH Margaret Pittman Award for Outstanding Scientific Achievement & Lectureship, election to the American Academy of Arts & Sciences and an Honorary Doctorate from EPFL. Berger is extremely grateful for this recognition by ISCB, especially considering her longtime involvement with the Society. She said, ‘It’s a tremendous honor to join such a distinguished and accomplished group of scientists’.

Abstract

The Outstanding Contributions to the International Society of Computational Biology (ISCB) Award recognizes outstanding service contributions to the Society by any member through exemplary leadership, education, service or a combination of these three elements. Barbara (Barb) Bryant, Senior Director at Constellation Pharmaceuticals, is the 2019 ISCB winner of the Outstanding Contributions to ISCB Award and will be recognized at the 2019 Joint Intelligent Systems for Molecular Biology/European Conference on Computational Biology (ISMB/ECCB) in Basel, Switzerland on July 21–25, 2019. Barb Bryant has spent much of her career as a computational biologist working in the pharmaceutical industry, where she has managed and directed a wide array of bioinformatics projects related to cancer diagnostics, clinical biomarker identification and mechanism of action of small molecule inhibitors. Bryant first became involved with ISCB by attending conferences like ISMB and engaging in leadership opportunities through ISCB. She has continued to be involved with ISCB because she has benefited and genuinely treasured being a part of this unique community. She said, ‘I have enjoyed working with colleagues to find ways to support other computational biologists, particularly students and postdocs. It was great to have a shared purpose, in contrast to the somewhat competitive nature you can sometimes find in scientific research. It is gratifying to be able to see progress on community projects such as nurturing the Student Council, encouraging open sharing of data and software, putting on conferences or developing publishing venues. Above all, I value the friendships that I have developed with others on the Board and Committees’. Bryant has served on the ISCB Board of Directors in several capacities, including ISCB Secretary (2002–2005) and Vice President (2005–2007). She also chaired the Public Affairs Committee during this time and was instrumental in maintaining ISCB’s affiliation with FASEB. Bryant worked on the Editorial Board of PLoS Computational Biology and has been thankful for these diverse service opportunities. She said, ‘I loved collaborating with Phil Bourne on the Editorial Board of PLoS Computational Biology. It is great to work with colleagues who have a ton of great ideas and an inclusive, forward-looking attitude. Thinking about how to bring positive change on the Board and within the Society has also been a good challenge. I appreciated serving as the representative of ISCB to FASEB in order to have a voice in Washington at a critical time, post-9/11, when it was becoming harder to travel to the USA for scientific conferences and collaboration’. Bryant sees ISCB playing a critical future role in advancing important initiatives related to computational biology, including advocating for improved research funding and open access to findings from government funded research. She considers one of ISCB’s strengths to be in the exchange of scientific information through conferences and publications, and she hopes the Society can continue to innovate novel approaches to enhance the communication and dissemination of computational biology research. Bryant hopes trainees and junior faculty members seek out constructive service opportunities with ISCB and other similar organizations. She said, ‘There are two key aspects of serving that I think matter even more than the particular area of service. The first is to find a way to make a positive difference—to change how the world operates. The second is to do it with other people who are positive and effective and fun to be with. If it is a toxic environment, leave. If the people are awesome, stick with it and find a way to contribute, no matter how hard the problem!’ Bryant will be recognized for her distinguished service to ISCB at the 2019 Joint ISMB/ECCB conference in Basel, Switzerland alongside this year’s other ISCB award recipients.

The ISCB Innovator Award honors an ISCB scientist who is within two decades of having completed his or her graduate degree and has made outstanding contributions to the field of computational biology. The 2019 winner is Dr. William Stafford Noble, Professor in the Department of Genome Science, University of Washington. Noble will receive his award and deliver a keynote presentation at the 2019 Joint International Conference on Intelligent Systems for Molecular Biology/European Conference on Computational Biology in Basel, Switzerland being held on July 21–25, 2019. William Stafford Noble was raised in Naperville, IL, with his brothers and his parents who were both college professors. As a child, he didn’t have a specific interest in science, but he remembered, ‘I was just interested in learning stuff’. A simple test gave Noble a peek into his future career path. Noble recalled, ‘I took a career aptitude test in high school, and the results said I should be a college professor or computer scientist, but at that point I had never touched a computer’. Noble went to Stanford University to complete a bachelor’s degree in Symbolic Systems, with a concentration in Philosophy. He has come to appreciate the multidisciplinary nature of his undergraduate degree, which included a broad range of coursework in computer science, cognitive science, linguistics, philosophy and mathematics. After graduating in 1991, Noble gained work experience in the field of speech recognition, and he also spent two years in the US Peace Corps in Lesotho, Africa. Noble said, ‘Both of my brothers went overseas after college, so I picked the Peace Corps. It seemed to be a little better organized than some other options’. Noble spent two years teaching math, physics and English literature to secondary students and had to develop teaching skills to explain complex material in a clear and straightforward way, training that has served him well throughout his career. All the while, he kept thinking about computer programming, and he would write down programs on paper in his free time. At the end of his first year in Lesotho, his parents visited him and brought him a laptop, so he could use the brief hours of evening electricity to transfer his programs from paper to a computer. Noble also developed an interest at this time in artificial life, which was a relatively new field. He got his hands on several artificial life conference proceedings and set off to study this area as a newly minted graduated student at the University of California, San Diego in 1994. Relatively quickly, he came to feel that this field was too descriptive, so he began to search for a different dissertation subject. His future Ph.D. mentor, Charles Elkan, emailed him about a funding opportunity that would allow him to study hidden Markov models (HMMs) in protein and DNA sequences. Noble was open to this topic because he was already familiar with HMMs from his work in speech recognition, and he went on to complete his Ph.D. in computer science and cognitive science in 1998. Noble’s first bioinformatics publication, which was based on his Ph.D. research, described a web server for motif-based sequence analysis (the MEME Suite) that is still in use today. Noble went on to David Haussler’s lab at the University of California, Santa Cruz as a Sloan/DOE postdoctoral fellow and co-authored the first paper that applied support vector machines to microarray gene expression data. He also developed kernel functions that could be used to represent a variety of data types, and he showed how kernels could be used to perform inference jointly from these heterogenous types of data. This work was ultimately developed into applications in inference of protein-protein interactions and gene function that are used by many researchers. In 1999, Noble became an Assistant Professor in the Department of Computer Science at Columbia University, with a joint appointment at the Columbia Genome Center. He moved to his current appointment at the University of Washington in 2002 in the newly formed Department of Genome Sciences with adjunct appointments in the Department of Computer Science and Engineering, the Department of Medicine and the Department of Biomedical Informatics and Medical Education. As an independent investigator, Noble has expanded his research interests including the development of unsupervised machine learning methods for semi-automated genome annotation, and the application of machine learning and statistical methods to analyze proteomic data. He has also worked with collaborators to develop high-throughput assays to characterize the 3D structure of DNA in the nucleus. Throughout his career, Noble has grown as a scientist and mentor by learning from those who have mentored him, as well as observing how his collaborators mentor students and run their labs. Noble also credits his wife, Nancy Stafford Noble, for being a valuable sounding board and providing her expertise as an executive coach as he has navigated the many challenges of being a PI. Noble’s prodigious body of work includes authorship of over 230 peer-reviewed articles. He has trained and advised 15 graduate students and 21 postdoctoral fellows, many of whom now hold faculty appointments, and he was honored with the Postdoc Mentor of the Year Award by the University of Washington Postdoctoral Association. Outside of the lab, Noble is an active member of the global computational biology community through his service on multiple editorial boards, conference committees, study sections and roles on the ISCB Board and various committees. Noble has been a part of ISCB since its early years and has always felt at home at ISMB meetings, which he considers one of the few gatherings that brings together computational biologists who bridge the gap between basic computer science and applications in biology. Noble feels deeply honored by his recognition with the 2019 ISCB Innovator Award, particularly as this award is bestowed upon him by colleagues for whom he holds great respect and admiration.

Many bacteria contain plasmids, but separating between contigs that originate on the plasmid and those that are part of the bacterial genome can be difficult. This is especially true in metagenomic assembly, which yields many contigs of unknown origin. Existing tools for classifying sequences of plasmid origin give less reliable results for shorter sequences, are trained using a fraction of the known plasmids, and can be difficult to use in practice. We present PlasClass, a new plasmid classifier. It uses a set of standard classifiers trained on the most current set of known plasmid sequences for different sequence lengths. We tested PlasClass sequence classification on held-out data and simulations, as well as publicly available bacterial isolates and plasmidome samples and plasmids assembled from metagenomic samples. PlasClass outperforms the state-of-the-art plasmid classification tool on shorter sequences, which constitute the majority of assembly contigs, allowing it to achieve higher F1 scores in classifying sequences from a wide range of datasets. PlasClass also uses significantly less time and memory. PlasClass can be used to easily classify plasmid and bacterial genome sequences in metagenomic or isolate assemblies. It is available under the MIT license from: https://github.com/Shamir-Lab/PlasClass.

Recent advances in experimental biology allow creation of datasets where several genome-wide data types (called omics) are measured per sample. Integrative analysis of multi-omic datasets in general, and clustering of samples in such datasets specifically, can improve our understanding of biological processes and discover different disease subtypes. In this work we present MONET (Multi Omic clustering by Non-Exhaustive Types), which presents a unique approach to multi-omic clustering. MONET discovers modules of similar samples, such that each module is allowed to have a clustering structure for only a subset of the omics. This approach differs from most existent multi-omic clustering algorithms, which assume a common structure across all omics, and from several recent algorithms that model distinct cluster structures. We tested MONET extensively on simulated data, on an image dataset, and on ten multi-omic cancer datasets from TCGA. Our analysis shows that MONET compares favorably with other multi-omic clustering methods. We demonstrate MONET's biological and clinical relevance by analyzing its results for Ovarian Serous Cystadenocarcinoma. We also show that MONET is robust to missing data, can cluster genes in multi-omic dataset, and reveal modules of cell types in single-cell multi-omic data. Our work shows that MONET is a valuable tool that can provide complementary results to those provided by existent algorithms for multi-omic analysis.

MOTIVATION: Cancer subtypes were usually defined based on molecular characterization of single omic data. Increasingly, measurements of multiple omic profiles for the same cohort are available. Defining cancer subtypes using multi-omic data may improve our understanding of cancer, and suggest more precise treatment for patients. RESULTS: We present NEMO (NEighborhood based Multi-Omics clustering), a novel algorithm for multi-omics clustering. Importantly, NEMO can be applied to partial datasets in which some patients have data for only a subset of the omics, without performing data imputation. In extensive testing on ten cancer datasets spanning 3168 patients, NEMO achieved results comparable to the best of nine state-of-the-art multi-omics clustering algorithms on full data and showed an improvement on partial data. On some of the partial data tests, PVC, a multi-view algorithm, performed better, but it is limited to two omics and to positive partial data. Finally, we demonstrate the advantage of NEMO in detailed analysis of partial data of AML patients. NEMO is fast and much simpler than existing multi-omics clustering algorithms, and avoids iterative optimization. AVAILABILITY AND IMPLEMENTATION: Code for NEMO and for reproducing all NEMO results in this paper is in github: https://github.com/Shamir-Lab/NEMO. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Analysis of large genomic datasets along with their accompanying clinical information has shown great promise in cancer research over the last decade. Such datasets typically include thousands of samples, each measured by one or several high-throughput technologies ('omics') and annotated with extensive clinical information. While instrumental for fulfilling the promise of personalized medicine, the analysis and visualization of such large datasets is challenging and necessitates programming skills and familiarity with a large array of software tools to be used for the various steps of the analysis. RESULTS: We developed PROMO (Profiler of Multi-Omic data), a friendly, fully interactive stand-alone software for analyzing large genomic cancer datasets together with their associated clinical information. The tool provides an array of built-in methods and algorithms for importing, preprocessing, visualizing, clustering, clinical label enrichment testing, and survival analysis that can be performed on a single or multi-omic dataset. The tool can be used for quick exploration and stratification of tumor samples taken from patients into clinically significant molecular subtypes. Identification of prognostic biomarkers and generation of simple subtype classifiers are additional important features. We review PROMO's main features and demonstrate its analysis capabilities on a breast cancer cohort from TCGA. CONCLUSIONS: PROMO provides a single integrated solution for swiftly performing a complete analysis of cancer genomic data for subtype discovery and biomarker identification without writing a single line of code, and can, therefore, make the analysis of these data much easier for cancer biologists and biomedical researchers. PROMO is freely available for download at http://acgt.cs.tau.ac.il/promo/.

Motivation: Large-scale publicly available genomic data on many disease phenotypes could improve our understanding of the molecular basis of disease. Tools that undertake this challenge by jointly analyzing multiple phenotypes are needed. Results: ADEPTUS is a web-tool that enables various functional genomics analyses based on a high-quality curated database spanning >38, 000 gene expression profiles and >100 diseases. It offers four types of analysis. (i) For a gene list provided by the user it computes disease ontology (DO), pathway, and gene ontology (GO) enrichment and displays the genes as a network. (ii) For a given disease, it enables exploration of drug repurposing by creating a gene network summarizing the genomic events in it. (iii) For a gene of interest, it generates a report summarizing its behavior across several studies. (iv) It can predict the tissue of origin and the disease of a sample based on its gene expression or its somatic mutation profile. Such analyses open novel ways to understand new datasets and to predict primary site of cancer. Availability and implementation: Data and tool: http://adeptus.cs.tau.ac.il/home Analyses: Supplementary Material. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

Each year the International Society for Computational Biology (ISCB) recognizes the achievements of an early to mid-career scientist with the Overton Prize. This prize honors the untimely death of Dr. G. Christian Overton, a respected computational biologist and founding ISCB Board member. The Overton Prize recognizes independent investigators who are in the early to middle phases of their careers and are selected because of their significant contributions to computational biology through research, teaching, and service. ISCB is pleased to recognize Dr. Cole Trapnell, Assistant Professor of Genome Sciences at the University of Washington as the 2018 winner of the Overton Prize. Trapnell will be presenting a keynote presentation at the 2018 International Conference on Intelligent Systems for Molecular Biology in Chicago, Illinois being held from July 6 to 10, 2018. Cole Trapnell’s earliest interest in science began at home. He was born in Cheverly, MD and spent his childhood living in College Park, right near the University of Maryland. His father, Bruce Trapnell, is a physician scientist, and Cole has fond memories of accompanying his father to the lab. Beyond the hands-on experiences of doing restriction digests with his dad as young child, Trapnell most appreciates how his father encouraged him to think scientifically. He recalled, ‘One time we were playing a board game, and I remarked that because the last dice roll was a six, the next one wouldn’t be. My dad decided to correct my thinking, so the next thing I knew, we were flipping a penny 1000 times to estimate the probability distribution of getting heads versus tails. I still have the plot that we drew by hand on 1 mm graph paper.’ Trapnell was first interested in physics and abstract mathematics and was drawn to how these fields tackled complex ideas in terms of ‘first principles.’ He began learning programming as a high school student and worked as a student engineer on a robotics project for the US Army. Trapnell honed his coding skills as an undergraduate by working for a startup that developed software for the areas of retail stock, futures and foreign currency trading, and he learned how to develop tools that can do complex calculations with large amounts of data in real time. He completed a dual BS degree in computer science and mathematics at the University of Maryland, College Park in 2005 and then began his PhD in computer science there as well. Trapnell thought he would work on problems in supercomputing, but then he took Steven Salzberg’s class on bioinformatics. This brought his attention to the emergence of ‘next-generation’ sequencing technology, and he realized the potential for high throughput computing to handle this sequence data. Trapnell’s PhD research focused on sequence alignment, and he adapted the Bowtie algorithm developed by Ben Langmead into a program called TopHat that could handle transcriptomic data. During this time, Trapnell moved to the University of California, Berkeley, where his wife was pursuing her PhD in mathematics, and he started working with Lior Pachter, who became his co-advisor with Salzberg at UMD. As Trapnell developed TopHat and the companion tool, Cufflinks, he tested them with datasets from Barbara Wold’s lab, and he began to develop an appreciation for biological questions, especially in gene regulation. Trapnell was drawn to doing bench research, and his labmate Rob Bradley encouraged him to take that leap. He recalled, ‘Rob Bradley convinced me that to become a really good biologist, I should learn to do experiments. Rob, who trained as a biophysicist, had gone off to do a postdoc at the bench. I followed suit and joined John Rinn’s lab (at Harvard University), where I worked to both do experiments and analyze them myself.’ Trapnell’s time in Rinn’s lab not only helped him get his hands dirty doing bench research, but gave him the unique perspective of working under a scientist who pioneered the field of long noncoding RNAs. Trapnell’s postdoctoral training opened his eyes to the realities of experimental biology and he acknowledges that these experiences have made him a better computational biologist. While Cufflinks could help him predict which individual splice isoforms may be elevated under certain disease conditions, he came to realize how hard it can be to validate these observations at the lab bench: a specific antibody may not exist for a western blot or technical difficulties may make it difficult to knock down a gene isoform in a particular model system. Trapnell had to adjust to the different culture associated with working in a wet lab. He recounted, ‘Computational people are often mystified and frustrated by how often their experiments fail. I like to tell them a story of my own frustration: A little while after starting my wet lab postdoc training, I was complaining to my labmate, Dave Hendrickson, that my experiments were constantly failing. He asked me how long I’d been at it, and I told him about six months. He said, ‘Well, give it another six months.’ I thought he meant I would get better at doing experiments but what he actually said next was, ‘It’ll hurt less when they don’t work.’ This was a tremendously eye opening thing for me, because he was trying to tell me that being an effective experimentalist means anticipating failure, planning for it, designing controls that can detect it, and parallelizing work within projects so that you can make progress in one direction even when you’re stuck in another. There are similar cultural differences that experimentalists encounter when learning to program.’ As a PI, Trapnell is supportive of students and trainees that want to gain both experimental and computational experience, but he wants to them to learn to understand the culture of these two realms and not just acquire the necessary skills to do experiments or develop algorithms. Throughout his training, Trapnell has valued the guidance of his mentors. His current lab is positioned between the labs of Stan Fields and Bob Waterson, both leaders in the field of genomics, and they been invaluable advisors to Trapnell. He said, ‘Despite their fame and their busy lives, both go way out of their way to advise me on how to bring my research and lab to its potential.’ All of his mentors have inspired Trapnell to build a lab culture that encourages open, inspiring and rigorous science. As he established his own lab at the University of Washington, he has started to think differently as a PI and said, ‘I am continually faced with the question: What do I think is the most important scientific contribution I can make?’ Shifting his mindset has been a challenge, but he is still broadly interested in gene regulation, especially gaining a more quantitative understanding of the epigenome. Trapnell considers the advances in single-cell measurements as critical to quantifying aspects of gene regulation, and his team is developing tools for single-cell measurements of gene expression, chromatin accessibility, and other features of the molecular state of the genome. Much of this work is in collaboration with Jay Shendure, whose lab specializes in molecular biotechnology development. Trapnell is keen on this collaboration: ‘Jay and I have very different approaches but share a common goal to transform our understanding of development and disease using single-cell technologies. Our collaboration has been fantastically productive and fun so far, and there’s a lot more to come.’ Trapnell is deeply honored to selected for the Overton Prize, and said, ‘I feel strongly that my success is at least as much a product of my being in the right place at the right time with the right collaborators as from any choices I made. I have been repeatedly given great opportunities and I’ve tried to make the best use of them, but I would have gotten nowhere if not for the generous help and creativity of a long list of mentors, collaborators and colleagues.’

Every year ISCB recognizes a leader in the computational biology and bioinformatics fields with the Accomplishments by a Senior Scientist Award. This is the highest award bestowed by ISCB in recognition of a scientist’s significant research, education and service contributions. Ruth Nussinov, Senior Principal Scientist and Principal Investigator at the National Cancer Institute, National Institutes of Health and Professor Emeritus in the Department of Human Molecular Genetics & Biochemistry, School of Medicine at Tel Aviv University, Israel is being honored as the 2018 winner of the Accomplishment by a Senior Scientist Award. She will receive her award and present a keynote address at ISCB’s premiere annual meeting, the 2018 Intelligent Systems for Molecular Biology (ISMB) conference in Chicago, IL being held on July 6–10, 2018. Ruth Nussinov is a computational biologist with research interests that have touched every aspect of the field, from her PhD research on RNA secondary structure prediction to her visionary work on DNA sequence analysis, to proposing that all protein (and other biomacromolecules) conformations pre-exist and that all dynamic proteins are allosteric, to her current studies focused on Ras signaling in cancer. Nussinov’s deep intellectual curiosity has guided her research interests throughout her career. Nussinov was raised in Rehovot, Israel, and attributes her early interest in science to watching her father conduct pioneering agricultural research that focused on adapting crops to the Israeli climate (http://en.hafakulta.agri.huji.ac.il/people/shmuel-hurwitz; Nussinov, 2017). Nussinov’s father, Shmuel Hurwitz was born in Minsk, Russia and studied chemistry at Moscow University but later immigrated to Palestine (present-day Israel) after his arrest for Zionist activities. It was here he discovered the great need for agricultural research. He pursued these studies at Berlin University but left Nazi Germany after his graduation in 1933 to found the Agricultural Research Station in Rehovot. Hurwitz was a founding member of the Faculty of Agriculture at the Hebrew University and was recognized for his significant contributions to advancing Israel agriculture with the 1957 Israeli Prize. As a child, Nussinov often joined her father on trips to his field sites, and his devotion to research and intense work ethic influenced her deeply and shaped how she approaches her work. Nussinov also attributes her success as a scientist to the unwavering support from her husband, Shmuel Nussinov. They married just after she completed her service in the Israeli Army, during which time he was pursuing his graduate studies in particle physics at the Weizmann Institute. Her husband’s research advisor moved to the University of Washington, so Nussinov continued her undergraduate studies there (in microbiology) and went on to pursue her Master’s degree in biochemistry at Rutgers University while her husband pursued postdoctoral research at Princeton University. They returned to Israel when Shmuel Nussinov joined the faculty at Tel Aviv University. When they came back to the USA several years later for his sabbatical, Ruth Nussinov enrolled in a PhD program in biochemistry at Rutgers and was mentored by a newly arrived assistant professor named George Pieczenik who had just come from Cambridge (UK). Nussinov recalled, ‘He said, “You know Ruth, Fred Sanger has just developed a DNA sequencing method and consequently there will be RNA sequences, and we will need an algorithm for the prediction of the secondary structure of RNA.”’ She ran with this idea and worked tirelessly to develop the foundational Nussinov dynamic programming algorithm that is still in use today (Nussinov, 1978). Nussinov’s PhD research has driven her career-long search for questions that tackle issues of biological significance. She worked relatively independently on her project and was able to graduate in two years, and this early autonomy was critical to shaping her career path as an independent researcher. Nussinov and her family returned to Israel and she pursued postdoctoral studies in the Structural Chemistry Department of the Weizmann Institute and made several seminal contributions to DNA sequence analysis. She also worked as a Visiting Scientist in the Chemistry Department at the University of California, Berkeley and in the Biochemistry Department at Harvard University. In spite of her impressive body of work and concept-driven approach to scientific inquiry, Nussinov faced difficulties in securing a position at Tel Aviv University in the mid-1980s given her husband’s existing position at the university and her unconventional, independent career path (Shehu, 2013). In 1985, Nussinov was finally appointed as an Associate Professor at Tel Aviv University and also became affiliated with NCI/NIH. During these early years, she credits her husband for giving her valuable advice about handling criticism from manuscript reviewers. He urged her to trust in her work and to reflect on and revise her manuscripts and resubmit them, as publications matter to the progress of a junior and unknown scientist (Nussinov, 2017). One of Nussinov’s most profound contributions to the field is the ‘conformational selection and population shift’ model of molecular recognition (Boehr et al., 2009; Ma et al., 1999, 2002; Tsai et al., 1999a, b). She and her colleagues first proposed this model in 1999 as an alternative paradigm to the ‘induced-fit’ model of protein–protein interactions. The induced-fit model hypothesizes that conformational changes to a protein occur in a stepwise fashion upon binding to a ligand. In contrast, the conformational selection model portends that unbound molecules exist in all possible structural conformations, but some unbound higher-energy conformations preferentially associate with a binding partner and cause a shift in equilibrium that favors this conformation. This model can explain numerous interactions observed for protein–ligand, RNA–ligand, protein–protein, protein–DNA and protein–RNA interactions, and can explain mechanisms of biological regulation, including oncogenic signaling. Nussinov is currently focused on the Ras protein and its interactions with effectors, with a particular interest in KRAS-driven adenocarcinomas. She observed that self-association of GTP-dependent K-Ras dimers at different interfaces regulates which effectors bind to the dimers, which can alter downstream activity (Nussinov et al., 2018). Nussinov and her team have also described the critical role of calmodulin selectively binding to the GTP-bound K-Ras4B oncogenic isoform, which promotes the initiation and progression of adenocarcinomas due to full activation of PI3Kα/Akt signaling in addition to the MAPK pathway. These mechanistic insights are critical to developing better cancer drugs, and this work was recognized in the ‘Best of the AACR Journals Collection 2015’. Nussinov is also starting to explore interactions between the human proteome and pathogens, given the growing appreciation of the microbiome on human health. Nussinov’s impact to the fields of computational biology and bioinformatics is notable. She has published more than 500 articles and has been ranked as a Highly Cited Researcher (ranking among the top 3000 researchers or 1% across all fields according to Thomson Reuters Essential Science Indicators, http://highlycited.com/December 2015) with more than 43 000 citations to date. Nussinov has also given over 300 invited talks and continues to maintain an active speaker schedule. Nussinov serves as the Editor-in-Chief of PLOS Computational Biology, and she has also served as an editor and reviewer for numerous leading journals. Her scientific contributions have been recognized through her election as a Fellow of the Biophysical Society (2011) and an ISCB Fellow (2013). Nussinov has been a devoted mentor and advisor to graduate students and trainees throughout her career, and she has mentored dozens of PhD students, including numerous women. She has tried to model her mentorship to how she was trained, and she said, ‘I very much encourage independence and like for students to suggest a problem to study’. Nussinov has always felt close connection with ISCB and her recognition with the 2018 ISCB Accomplishments by a Senior Scientist Award is a fitting tribute to her contributions to ISCB and to computational biology in general. She said, ‘I feel that’s where I belong and that’s where I want to be. I care very much about the development and sustainability and contribution of computational biology to all biological, chemical and physical sciences’. Conflict of Interest: none declared.

The Outstanding Contributions to International Society for Computational Biology (ISCB) Award was introduced in 2015 to recognize Society members who have made lasting and beneficial contributions through their leadership, service and educational work or a combination of these areas. Russ Altman, Kenneth Fong Professor and Professor of Bioengineering, of Genetics, of Medicine (General Medicine Discipline), of Biomedical Data Science and, by courtesy, of Computer Science, is the 2018 winner of the Outstanding Contributions to ISCB Award and will be recognized at the 2018 Intelligent Systems for Molecular Biology (ISMB) meeting in Chicago, IL being held on July 6–10, 2018. Altman’s years of dedicated service to ISCB began when he attended the very first ISMB meeting in 1993. As a brand new faculty member, he remembered how he felt at home at ISMB, surrounded by a community of scientists also interested in computational biology and bioinformatics. Altman’s enthusiasm at this first ISMB meeting led him to help organize the next ISMB meeting. He recalled, “It became clear that there was no obvious ‘host’ for ISMB 1994, so I volunteered to host it at Stanford, where we had a lovely meeting with a couple of hundred people. We had some extra money after paying our bills, so we wanted to send the money to wherever ISMB 1995 was going to be (UK). For the first few years, this is how ISMB worked—the organizers from 1 year would send the leftover funds as a seed for the next ISMB. There was no organization, and as the size of the leftover check increased, we started getting nervous and realized we needed to create a legal entity.” ISCB was born at ISMB 1997 in Halkidiki, Greece, where organizers of former ISMB meetings and others sat at dinner on the beach and planned the society and figured out how to incorporate it. Altman has warm recollections of that historic gathering and said, ‘There are pictures of that great dinner and group, and I treasure the memory of that meeting’. Altman has enjoyed serving ISCB at all levels since its inception, from work on the Publications Committee and as a conference organizer, to his tenure on the ISCB Board of Directors (1997–2005) and as ISCB President (2002–2005). Altman’s early work on the Publications Committee included applying for PubMED to index the ISMB proceedings, which was a critical step in helping ISCB members receive academic credit for their conference papers. Altman also helped negotiate the agreement to have Bioinformatics named as an official ISCB journal. Beyond ISMB, Altman has been an organizer of the Pacific Symposium on Biocomputing, and has facilitated the relationship between this conference and ISCB. As computational biology and bioinformatics have grown into stand-alone fields, Altman has made many critical scientific contributions through his research. Altman and his research group have developed numerous computational tools that address problems in basic biology and medicine, with a particular interest in understanding drug responses. His work has included studies of structure-function relationships in macromolecules, understanding RNA structure and folding and assessing drug responses at the molecular, cellular, organismal and population levels. Altman believes that it is critical to bring awareness to the greater scientific community that computational biologists and bioinformaticians are more than just great collaborators, but they also lead major research projects. He considers service to ISCB as a way established principal investigators, junior faculty, and trainees can help bring about this awareness to advance the field. Altman considers ISCB to be a community that provides both valuable service opportunities and sources of mentorship and collaboration for scientists. Altman’s dedication to the field computational biology has been recognized by his election as an ISCB Fellow (2010), as well as with numerous other honors, including election as a member of the National Academy of Medicine (formerly the Institute of Medicine, 2009) and a Fellow of the American Association for the Advancement of Science (2014). Altman has also worked as an editor and reviewer for numerous scientific journals, including serving as Co-Editor-in-Chief of the Annual Review of Biomedical Data Science. Altman’s many years of service to ISCB have been critical to the very formation and evolution of the Society from its infancy as a small meeting to the globally recognized professional organization that it is today.

The ISCB Innovator Award recognizes an ISCB scientist who is within two decades of having completed his or her graduate degree and has consistently made outstanding contributions to the field of computational biology. The 2018 winner is Dr. M. Madan Babu, Programme Leader at the MRC Laboratory of Molecular Biology, Cambridge, UK. Madan will receive his award and deliver a keynote presentation at the 2018 International Conference on Intelligent Systems for Molecular Biology in Chicago, Illinois being held on July 6–10, 2018. M. Madan Babu is the head of the Regulatory Genomics and Systems Biology group at the MRC Laboratory of Molecular Biology, Cambridge, UK. His work focuses on understanding how cellular systems are regulated at different scales (molecular, systems and genomic levels) and how this impacts genome evolution. Madan grew up in Chennai, India and developed early interests in computer science and biotechnology. As a young child, he has vivid memories of his father bringing home a personal computer and soon after he became interested in learning to program. He also remembers when his family first started using the internet, and recalled, ‘In the mid-90’s, we started having access to the Internet. This made a big difference in the days where access to information beyond textbooks was not readily available; so thanks to my father I had these opportunities early in my life’. Madan discovered biotechnology as a high school student, and attributes his lifelong interest in biology to the impact of his biology teacher, Dr. M.C. Aruna, who discussed foundational biological concepts with him, including how genetic information can be used to understand living systems. Madan went on to pursue a Bachelor of Technology (Biotechnology) degree at Anna University, Center for Biotechnology in Chennai, India. He first became of aware of computational biology during year undergraduate research internship, at which time he was exposed to the work of Cyrus Chothia and Arthur Lesk in a course on protein structure. He became fascinated with this research area and then delved into seminal papers on computational genomics, protein engineering and structural bioinformatics. As an intern, Madan pursued undergraduate research under the guidance of Prof. Balaram and Prof. K. Sankran, and saw this key turning point in his career path. He recollected, ‘We started applying methods from computer science to study protein sequences and structures. For the first time, I experienced how to define a scientific problem, develop computational methods to solve it and write up and defend the findings for publication. This really got me excited and that was when I decided that I would like to pursue a career in computational biology’. Madan recognizes that his interest in computational biology was fostered by his ability to access publicly-available protein and genomic data on his own computer, as well as the open access he had to lecture materials, methods and algorithms from computational biologists spanning the globe. He said, ‘I cannot forget the day when I wrote an email to RCSB from India and received a five-part CD-ROM with co-ordinate data for all protein structures. Being able to look at protein structures using RASMOL from home and writing FORTRAN programs to analyze structures as an undergraduate student was one of the most exciting experiences that really captured my interest in the field’. Madan left India in 2001 to pursue his PhD in computational genomics at the MRC Laboratory of Molecular Biology and Trinity College, University of Cambridge, UK under the guidance of Dr. Sarah Teichmann. His PhD research explored various aspects of gene regulatory networks, and marked the beginning of a very fruitful mentorship under Teichmann. Madan carried out his post-doctoral training at the National Center for Biotechnology Information, NIH in Bethesda, MD, USA under the guidance of Dr. L. Aravind, during which time he learned the importance of having broad interests in diverse subject areas as well as critically analyzing the complexity of biological systems at every possible level of detail. After a brief but extremely productive post-doctoral fellowship, Madan became a group leader at the age of 26 of the Regulatory Genomics and Systems Biology Group at the MRC Laboratory of Molecular Biology in 2006. As a PI, he has come to appreciate how his team of scientists can work together to tackle scientific questions on a much larger scale and shed new light on long-standing, fundamental questions. He said, ‘One of the things that I really enjoy about the field of computational biology is that you really integrate knowledge from various disciplines––biology, statistics, computer science, mathematics, physics and chemistry. This means our lab is an amalgamation of people across disciplines that are really passionate about using interdisciplinary approaches to solve the problems they are working on’. Madan’s group currently focuses on several areas of research, including studies on G-protein coupled receptors, a protein family involved in almost every aspect of human physiology and targeted by numerous drugs. Madan’s group is also using a combination of computational and experimental approaches to discover which parts of unstructured protein regions are functional and understand what makes them functional. His group is interested in applying developments in statistical learning and advances in large-scale genome sequencing to better understand natural variation in the human population as well as gain insight into how genomic variation impact rare and common diseases. Madan is greatly honored to be selected as the recipient of the 2018 ISCB Innovator Award. He is grateful for his academic mentors and colleagues, including Sarah Teichmann, L. Avarind, Cyrus Chothia, Michael Levitt, Veronica Van Heyningen, Eugene Koonin, Stephen Michnick, Richard Kriwacki, Uri Alon, Gebhard Schertler, Peter Wright, Keith Dunker, Janet Thornton, Tom Blundell and Venki Ramakrishnan, who have inspired him through their work and/or provided him valuable advice at various stages of his career. He is also appreciative of his past and present group members, and the MRC Laboratory of Molecular Biology for the freedom to develop new skills and take risks in pursuing research that pushes scientific boundaries. Conflict of Interest: C.N. Fogg was paid to write this article.

Motivation: We present Faucet, a two-pass streaming algorithm for assembly graph construction. Faucet builds an assembly graph incrementally as each read is processed. Thus, reads need not be stored locally, as they can be processed while downloading data and then discarded. We demonstrate this functionality by performing streaming graph assembly of publicly available data, and observe that the ratio of disk use to raw data size decreases as coverage is increased. Results: Faucet pairs the de Bruijn graph obtained from the reads with additional meta-data derived from them. We show these metadata-coverage counts collected at junction k-mers and connections bridging between junction pairs-contain most salient information needed for assembly, and demonstrate they enable cleaning of metagenome assembly graphs, greatly improving contiguity while maintaining accuracy. We compared Fauceted resource use and assembly quality to state of the art metagenome assemblers, as well as leading resource-efficient genome assemblers. Faucet used orders of magnitude less time and disk space than the specialized metagenome assemblers MetaSPAdes and Megahit, while also improving on their memory use; this broadly matched performance of other assemblers optimizing resource efficiency-namely, Minia and LightAssembler. However, on metagenomes tested, Faucet,o outputs had 14-110% higher mean NGA50 lengths compared with Minia, and 2- to 11-fold higher mean NGA50 lengths compared with LightAssembler, the only other streaming assembler available. Availability and implementation: Faucet is available at https://github.com/Shamir-Lab/Faucet. Contact: [email protected] or [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

Altman's years of dedicated service to ISCB began when he attended the very first ISMB meeting in 1993.As a brand new faculty member, he remembered how he felt at home at ISMB, surrounded by a community of scientists also interested in computational biology and bioinformatics.Altman's enthusiasm at this first ISMB meeting led him to help organize the next ISMB meeting.He recalled, "It became clear that there was no obvious 'host' for ISMB 1994, so I volunteered to host it at Stanford, where we had a lovely meeting with a couple of hundred people.We had some extra money after paying our bills, so we wanted to send the money to wherever ISMB 1995 was going to be (UK).For the first few years, this is how ISMB worked-the organizers from one year would send the leftover funds as a seed for the next ISMB.There was no organization, and as the size of the leftover check increased, we started getting nervous and realized we needed to create a legal entity."ISCB was born at ISMB 1997 in Halkidiki, Greece, where organizers of former ISMB meetings and others sat at dinner on the beach and planned the society and figured out how to incorporate it.Altman has warm recollections of that historic gathering and said, "There are pictures of that great dinner and group, and I treasure the memory of that meeting".Altman has enjoyed serving ISCB at all levels since its inception, from work on the Publications Committee and as a conference organizer to his tenure on the ISCB Board of Directors (

In search of biological significanceRuth Nussinov (Fig 1) is a computational biologist with research interests that have touched every aspect of the field, from her PhD research on RNA secondary structure prediction to her visionary work on DNA sequence analysis, to proposing that all protein (and other biomacromolecules) conformations preexist and that all dynamic proteins are allosteric, to her current studies focused on Ras signaling in cancer.Nussinov's deep intellectual curiosity has guided her research interests throughout her career.Nussinov was raised in Rehovot, Israel, and attributes her early interest in science to watching her father conduct pioneering agricultural research that focused on adapting crops to the Israeli climate [1,2].Nussinov's father, Shmuel Hurwitz, was born in Minsk, Russia, and studied chemistry at Moscow University but later immigrated to Palestine (present-day Israel) after his arrest for Zionist activities.

DOAJ is a unique and extensive index of diverse open access journals from around the world, driven by a growing community, committed to ensuring quality content is freely available online for everyone.

DOAJ is a unique and extensive index of diverse open access journals from around the world, driven by a growing community, committed to ensuring quality content is freely available online for everyone.

MOTIVATION: The minimizers scheme is a method for selecting k -mers from sequences. It is used in many bioinformatics software tools to bin comparable sequences or to sample a sequence in a deterministic fashion at approximately regular intervals, in order to reduce memory consumption and processing time. Although very useful, the minimizers selection procedure has undesirable behaviors (e.g. too many k -mers are selected when processing certain sequences). Some of these problems were already known to the authors of the minimizers technique, and the natural lexicographic ordering of k -mers used by minimizers was recognized as their origin. Many software tools using minimizers employ ad hoc variations of the lexicographic order to alleviate those issues. RESULTS: We provide an in-depth analysis of the effect of k -mer ordering on the performance of the minimizers technique. By using small universal hitting sets (a recently defined concept), we show how to significantly improve the performance of minimizers and avoid some of its worse behaviors. Based on these results, we encourage bioinformatics software developers to use an ordering based on a universal hitting set or, if not possible, a randomized ordering, rather than the lexicographic order. This analysis also settles negatively a conjecture (by Schleimer et al. ) on the expected density of minimizers in a random sequence. AVAILABILITY AND IMPLEMENTATION: The software used for this analysis is available on GitHub: https://github.com/gmarcais/minimizers.git . CONTACT: [email protected] or [email protected].

Motivation: Plasmids and other mobile elements are central contributors to microbial evolution and genome innovation. Recently, they have been found to have important roles in antibiotic resistance and in affecting production of metabolites used in industrial and agricultural applications. However, their characterization through deep sequencing remains challenging, in spite of rapid drops in cost and throughput increases for sequencing. Here, we attempt to ameliorate this situation by introducing a new circular element assembly algorithm, leveraging assembly graphs provided by a conventional de novo assembler and alignments of paired-end reads to assemble cyclic sequences likely to be plasmids, phages and other circular elements. Results: We introduce Recycler, the first tool that can extract complete circular contigs from sequence data of isolate microbial genomes, plasmidome and metagenome sequence data. We show that Recycler greatly increases the number of true plasmids recovered relative to other approaches while remaining highly accurate. We demonstrate this trend via simulations of plasmidomes, comparisons of predictions with reference data for isolate samples, and assessments of annotation accuracy on metagenome data. In addition, we provide validation by DNA amplification of 77 plasmids predicted by Recycler from the different sequenced samples in which Recycler showed mean accuracy of 89% across all data types-isolate, microbiome and plasmidome. Availability and Implementation: Recycler is available at http://github.com/Shamir-Lab/Recycler. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

BACKGROUND: During cancer progression genomes undergo point mutations as well as larger segmental changes. The latter include, among others, segmental deletions duplications, translocations and inversions.The result is a highly complex, patient-specific cancer karyotype. Using high-throughput technologies of deep sequencing and microarrays it is possible to interrogate a cancer genome and produce chromosomal copy number profiles and a list of breakpoints ("jumps") relative to the normal genome. This information is very detailed but local, and does not give the overall picture of the cancer genome. One of the basic challenges in cancer genome research is to use such information to infer the cancer karyotype. We present here an algorithmic approach, based on graph theory and integer linear programming, that receives segmental copy number and breakpoint data as input and produces a cancer karyotype that is most concordant with them. We used simulations to evaluate the utility of our approach, and applied it to real data. RESULTS: By using a simulation model, we were able to estimate the correctness and robustness of the algorithm in a spectrum of scenarios. Under our base scenario, designed according to observations in real data, the algorithm correctly inferred 69% of the karyotypes. However, when using less stringent correctness metrics that account for incomplete and noisy data, 87% of the reconstructed karyotypes were correct. Furthermore, in scenarios where the data were very clean and complete, accuracy rose to 90%-100%. Some examples of analysis of real data, and the reconstructed karyotypes suggested by our algorithm, are also presented. CONCLUSION: While reconstruction of complete, perfect karyotype based on short read data is very hard, a large fraction of the reconstruction will still be correct and can provide useful information.

In almost every field in genomics, large-scale biomedical datasets are used to report associations. Extracting associations that recur across multiple studies while controlling the false discovery rate is a fundamental challenge. Here, we propose a new method to allow joint analysis of multiple studies. Given a set of p-values obtained from each study, the goal is to identify associations that recur in at least k > 1 studies while controlling the false discovery rate. We propose several new algorithms that differ in how the study dependencies are modeled, and compare them and extant methods under various simulated scenarios. The top algorithm, SCREEN (Scalable Cluster-based REplicability ENhancement), is our new algorithm that works in three stages: (1) clustering an estimated correlation network of the studies, (2) learning replicability (e.g., of genes) within clusters, and (3) merging the results across the clusters. When we applied SCREEN to two real datasets it greatly outperformed the results obtained via standard meta-analysis. First, on a collection of 29 case-control gene expression cancer studies, we detected a large set of consistently up-regulated genes related to proliferation and cell cycle regulation. These genes are both consistently up-regulated across many cancer studies, and are well connected in known gene networks. Second, on a recent pan-cancer study that examined the expression profiles of patients with and without mutations in the HLA complex, we detected a large active module of up-regulated genes that are both related to immune responses and are well connected in known gene networks. This module covers thrice more genes as compared to the original study at a similar false discovery rate, demonstrating the high power of SCREEN. An implementation of SCREEN is available in the supplement.

With the rapidly increasing volume of deep sequencing data, more efficient algorithms and data structures are needed. Minimizers are a central recent paradigm that has improved various sequence analysis tasks, including hashing for faster read overlap detection, sparse suffix arrays for creating smaller indexes, and Bloom filters for speeding up sequence search. Here, we propose an alternative paradigm that can lead to substantial further improvement in these and other tasks. For integers k and L > k, we say that a set of k-mers is a universal hitting set (UHS) if every possible L-long sequence must contain a k-mer from the set. We develop a heuristic called DOCKS to find a compact UHS, which works in two phases: The first phase is solved optimally, and for the second we propose several efficient heuristics, trading set size for speed and memory. The use of heuristics is motivated by showing the NP-hardness of a closely related problem. We show that DOCKS works well in practice and produces UHSs that are very close to a theoretical lower bound. We present results for various values of k and L and by applying them to real genomes show that UHSs indeed improve over minimizers. In particular, DOCKS uses less than 30% of the 10-mers needed to span the human genome compared to minimizers. The software and computed UHSs are freely available at github.com/Shamir-Lab/DOCKS/ and acgt.cs.tau.ac.il/docks/, respectively.

Problems of genome rearrangement are central in both evolution and cancer. Most evolutionary scenarios have been studied under the assumption that the genome contains a single copy of each gene. In contrast, tumor genomes undergo deletions and duplications, and thus the number of copies of genes varies. The number of copies of each gene along a chromosome is called its copy number profile. Understanding copy number profile changes can assist in predicting disease progression and treatment. To date, questions related to distances between copy number profiles gained little scientific attention. Here we focus on the following fundamental problem, introduced by Schwarz et al. (PLOS Comp. Biol., 2014): given two copy number profiles, u and v, compute the edit distance from u to v, where the edit operations are segmental deletions and amplifications. We establish the computational complexity of this problem, showing that it is solvable in linear time and constant space.

MOTIVATION: Detecting modules of co-ordinated activity is fundamental in the analysis of large biological studies. For two-dimensional data (e.g. genes × patients), this is often done via clustering or biclustering. More recently, studies monitoring patients over time have added another dimension. Analysis is much more challenging in this case, especially when time measurements are not synchronized. New methods that can analyze three-way data are thus needed. RESULTS: We present a new algorithm for finding coherent and flexible modules in three-way data. Our method can identify both core modules that appear in multiple patients and patient-specific augmentations of these core modules that contain additional genes. Our algorithm is based on a hierarchical Bayesian data model and Gibbs sampling. The algorithm outperforms extant methods on simulated and on real data. The method successfully dissected key components of septic shock response from time series measurements of gene expression. Detected patient-specific module augmentations were informative for disease outcome. In analyzing brain functional magnetic resonance imaging time series of subjects at rest, it detected the pertinent brain regions involved. AVAILABILITY AND IMPLEMENTATION: R code and data are available at http://acgt.cs.tau.ac.il/twigs/.

doi:10.1093/bioinformatics/btt230 Bioinformatics (2013) 29(13), i71–i79 In the above paper, there were several mistakes due to copyediting error. In Theorem 1 ‘if’ should be replaced by ‘iff’ and should read as follows: For odd k, an RC complete sequence s achieves the lower bound (Proposition 1) iff there exist two edge-disjoint paths with no repeating edges, corresponding to s and RC(s), that together cover all edges of the de Bruijn graph of order k − 1. In Algorithm 1 ‘although’ should be replaced by ‘while’, and should read as follows: 1. Initially all edges are unmarked, F=R=∅⁠, and A={u}⁠, an arbitrary vertex. 2. While A≠∅ do 3. F=R=∅⁠. 4. Pick any starting vertex v=[x1,…,xk−1] from A. 5. While there exists an unmarked edge e=(x1,…,xk) outgoing from v do 6. Append e to F. Prepend RC(e) to R. 7. Mark e and RC(e). 8. Set v=[x2,…,xk]⁠; A=A∪{v}⁠. 9. Remove v from A. 10. If F≠∅⁠, add F to F⁠; add R to R⁠; 11. Merge the cycles in F to obtain a single forward path. Do the same for R⁠.

BACKGROUND: Data from large Next Generation Sequencing (NGS) experiments present challenges both in terms of costs associated with storage and in time required for file transfer. It is sometimes possible to store only a summary relevant to particular applications, but generally it is desirable to keep all information needed to revisit experimental results in the future. Thus, the need for efficient lossless compression methods for NGS reads arises. It has been shown that NGS-specific compression schemes can improve results over generic compression methods, such as the Lempel-Ziv algorithm, Burrows-Wheeler transform, or Arithmetic Coding. When a reference genome is available, effective compression can be achieved by first aligning the reads to the reference genome, and then encoding each read using the alignment position combined with the differences in the read relative to the reference. These reference-based methods have been shown to compress better than reference-free schemes, but the alignment step they require demands several hours of CPU time on a typical dataset, whereas reference-free methods can usually compress in minutes. RESULTS: We present a new approach that achieves highly efficient compression by using a reference genome, but completely circumvents the need for alignment, affording a great reduction in the time needed to compress. In contrast to reference-based methods that first align reads to the genome, we hash all reads into Bloom filters to encode, and decode by querying the same Bloom filters using read-length subsequences of the reference genome. Further compression is achieved by using a cascade of such filters. CONCLUSIONS: Our method, called BARCODE, runs an order of magnitude faster than reference-based methods, while compressing an order of magnitude better than reference-free methods, over a broad range of sequencing coverage. In high coverage (50-100 fold), compared to the best tested compressors, BARCODE saves 80-90% of the running time while only increasing space slightly.

MOTIVATION: Horizontal gene transfer (HGT) plays a crucial role in the evolution of prokaryotic species. Typically, no more than a few genes are horizontally transferred between any two species. However, several studies identified pairs of species (or linages) between which many different genes were horizontally transferred. Such a pair is said to be linked by a highway of gene sharing. Inferring such highways is crucial to understanding the evolution of prokaryotes and for inferring past symbiotic and ecological associations among different species. RESULTS: We present a new improved method for systematically detecting highways of gene sharing. As we demonstrate using a variety of simulated datasets, our method is highly accurate and efficient, and robust to noise and high rates of HGT. We further validate our method by applying it to a published dataset of >22 000 gene trees from 144 prokaryotic species. Our method makes it practical, for the first time, to perform accurate highway analysis quickly and easily even on large datasets with high rates of HGT. AVAILABILITY AND IMPLEMENTATION: An implementation of the method can be freely downloaded from: http://acgt.cs.tau.ac.il/hide.

MOTIVATION: Novel technologies can generate large sets of short double-stranded DNA sequences that can be used to measure their regulatory effects. Microarrays can measure in vitro the binding intensity of a protein to thousands of probes. Synthetic enhancer sequences inserted into an organism's genome allow us to measure in vivo the effect of such sequences on the phenotype. In both applications, by using sequence probes that cover all k-mers, a comprehensive picture of the effect of all possible short sequences on gene regulation is obtained. The value of k that can be used in practice is, however, severely limited by cost and space considerations. A key challenge is, therefore, to cover all k-mers with a minimal number of probes. The standard way to do this uses the de Bruijn sequence of length . However, as probes are double stranded, when a k-mer is included in a probe, its reverse complement k-mer is accounted for as well. RESULTS: Here, we show how to efficiently create a shortest possible sequence with the property that it contains each k-mer or its reverse complement, but not necessarily both. The length of the resulting sequence approaches half that of the de Bruijn sequence as k increases resulting in a more efficient array, which allows covering more longer sequences; alternatively, additional sequences with redundant k-mers of interest can be added. AVAILABILITY: The software is freely available from our website http://acgt.cs.tau.ac.il/shortcake/.

Comparing the gene-expression profiles of sick and healthy individuals can help in understanding disease. Such differential expression analysis is a well-established way to find gene sets whose expression is altered in the disease. Recent approaches to gene-expression analysis go a step further and seek differential co-expression patterns, wherein the level of co-expression of a set of genes differs markedly between disease and control samples. Such patterns can arise from a disease-related change in the regulatory mechanism governing that set of genes, and pinpoint dysfunctional regulatory networks. Here we present DICER, a new method for detecting differentially co-expressed gene sets using a novel probabilistic score for differential correlation. DICER goes beyond standard differential co-expression and detects pairs of modules showing differential co-expression. The expression profiles of genes within each module of the pair are correlated across all samples. The correlation between the two modules, however, differs markedly between the disease and normal samples. We show that DICER outperforms the state of the art in terms of significance and interpretability of the detected gene sets. Moreover, the gene sets discovered by DICER manifest regulation by disease-specific microRNA families. In a case study on Alzheimer's disease, DICER dissected biological processes and protein complexes into functional subunits that are differentially co-expressed, thereby revealing inner structures in disease regulatory networks.

BACKGROUND: RNA-Seq is a technique that uses Next Generation Sequencing to identify transcripts and estimate transcription levels. When applying this technique for quantification, one must contend with reads that align to multiple positions in the genome (multireads). Previous efforts to resolve multireads have shown that RNA-Seq expression estimation can be improved using probabilistic allocation of reads to genes. These methods use a probabilistic generative model for data generation and resolve ambiguity using likelihood-based approaches. In many instances, RNA-seq experiments are performed in the context of a population. The generative models of current methods do not take into account such population information, and it is an open question whether this information can improve quantification of the individual samples RESULTS: In order to explore the contribution of population level information in RNA-seq quantification, we apply a hierarchical probabilistic generative model, which assumes that expression levels of different individuals are sampled from a Dirichlet distribution with parameters specific to the population, and reads are sampled from the distribution of expression levels. We introduce an optimization procedure for the estimation of the model parameters, and use HapMap data and simulated data to demonstrate that the model yields a significant improvement in the accuracy of expression levels of paralogous genes. CONCLUSIONS: We provide a proof of principal of the benefit of drawing on population commonalities to estimate expression. The results of our experiments demonstrate this approach can be beneficial, primarily for estimation at the gene level.

The NP-hard gene-duplication problem takes as input a collection of gene trees and seeks a species tree that requires the fewest number of gene duplications to reconcile the input gene trees. An oft-cited, decade-old result by Stege states that the gene-duplication problem is fixed parameter tractable when parameterized by the number of gene duplications necessary for the reconciliation. Here, we uncover an error in this fixed parameter algorithm and show that this error cannot be corrected without sacrificing the fixed parameter tractability of the algorithm. Furthermore, we show a link between the gene-duplication problem and the minimum rooted triplets inconsistency problem which implies that the gene-duplication problem is 1) W[2]-hard when parameterized by the number of gene duplications necessary for the reconciliation and 2) hard to approximate to better than a logarithmic factor.

In the network querying problem, one is given a protein complex or pathway of species A and a protein-protein interaction network of species B; the goal is to identify subnetworks of B that are similar to the query in terms of sequence, topology, or both. Existing approaches mostly depend on knowledge of the interaction topology of the query in the network of species A; however, in practice, this topology is often not known. To address this problem, we develop a topology-free querying algorithm, which we call Torque. Given a query, represented as a set of proteins, Torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the network, while allowing both insertions and deletions. The algorithm uses alternatively dynamic programming and integer linear programming for the search task. We test Torque with queries from yeast, fly, and human, where we compare it to the QNet topology-based approach, and with queries from less studied species, where only topology-free algorithms apply. Torque detects many more matches than QNet, while giving results that are highly functionally coherent.

MOTIVATION: Microarray-based gene expression studies have great potential but are frequently difficult to interpret due to their overwhelming dimensions. Recent studies have shown that the analysis of expression data can be improved by its integration with protein interaction networks, but the performance of these analyses has been hampered by the uneven quality of the interaction data. RESULTS: We present Co-Expression Zone ANalysis using NEtworks (CEZANNE), a novel confidence-based method for extraction of functionally coherent co-expressed gene sets. CEZANNE uses probabilities for individual interactions, which can be computed by any available method. We propose a probabilistic model and a weighting scheme in which the likelihood of the connectivity of a subnetwork is related to the weight of its minimum cut. Applying CEZANNE to an expression dataset of DNA damage response in Saccharomyces cerevisiae, we recover both known and novel modules and predict novel protein functions. We show that CEZANNE outperforms previous methods for analysis of expression and interaction data. AVAILABILITY: CEZANNE is available as part of the MATISSE software at http://acgt.cs.tau.ac.il/matisse. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Biological signaling pathways that govern cellular physiology form an intricate web of tightly regulated interlocking processes. Data on these regulatory networks are accumulating at an unprecedented pace. The assimilation, visualization and interpretation of these data have become a major challenge in biological research, and once met, will greatly boost our ability to understand cell functioning on a systems level. RESULTS: To cope with this challenge, we are developing the SPIKE knowledge-base of signaling pathways. SPIKE contains three main software components: 1) A database (DB) of biological signaling pathways. Carefully curated information from the literature and data from large public sources constitute distinct tiers of the DB. 2) A visualization package that allows interactive graphic representations of regulatory interactions stored in the DB and superposition of functional genomic and proteomic data on the maps. 3) An algorithmic inference engine that analyzes the networks for novel functional interplays between network components.SPIKE is designed and implemented as a community tool and therefore provides a user-friendly interface that allows registered users to upload data to SPIKE DB. Our vision is that the DB will be populated by a distributed and highly collaborative effort undertaken by multiple groups in the research community, where each group contributes data in its field of expertise. CONCLUSION: The integrated capabilities of SPIKE make it a powerful platform for the analysis of signaling networks and the integration of knowledge on such networks with omics data.

In comparative genomics one analyzes jointly evolutionarily related species in order to identify conserved and diverged sequences and to infer their function. While such studies enabled the detection of conserved sequences in large genomes, the evolutionary dynamics of regulatory regions as a whole remain poorly understood. Here we present a probabilistic model for the evolution of promoter regions in yeast, combining the effects of regulatory interactions of many different transcription factors. The model expresses explicitly the selection forces acting on transcription factor binding sites in the context of a dynamic evolutionary process. We develop algorithms to compute likelihood and to learn de novo collections of transcription factor binding motifs and their selection parameters from alignments. Using the new techniques, we examine the evolutionary dynamics in Saccharomyces species promoters. Analyses of an evolutionary model constructed using all known transcription factor binding motifs and of a model learned from the data automatically reveal relatively weak selection on most binding sites. Moreover, according to our estimates, strong binding sites are constraining only a fraction of the yeast promoter sequence that is under selection. Our study demonstrates how complex evolutionary dynamics in noncoding regions emerges from formalization of the evolutionary consequences of known regulatory mechanisms.

A haplotype is an m-long binary vector. The XOR-genotype of two haplotypes is the m-vector of their coordinate-wise XOR. We study the following problem: Given a set of XOR-genotypes, reconstruct their haplotypes so that the set of resulting haplotypes can be mapped onto a perfect phylogeny (PP) tree. The question is motivated by studying population evolution in human genetics, and is a variant of the perfect phylogeny haplotyping problem that has received intensive attention recently. Unlike the latter problem, in which the input is "full" genotypes, here we assume less informative input, and so may be more economical to obtain experimentally. Building on ideas of Gusfield, we show how to solve the problem in polynomial time, by a reduction to the graph realization problem. The actual haplotypes are not uniquely determined by that tree they map onto, and the tree itself may or may not be unique. We show that tree uniqueness implies uniquely determined haplotypes, up to inherent degrees of freedom, and give a sufficient condition for the uniqueness. To actually determine the haplotypes given the tree, additional information is necessary. We show that two or three full genotypes suffice to reconstruct all the haplotypes, and present a linear algorithm for identifying those genotypes.

BACKGROUND: Genotype information generated by individual and international efforts carries the promise of revolutionizing disease studies and the association of phenotypes with alleles and haplotypes. Given the enormous amounts of public genotype data, tools for analyzing, interpreting and visualizing these data sets are of critical importance to researchers. In past works we have developed algorithms for genotypes phasing and tag SNP selection, which were shown to be quick and accurate. Both algorithms were available until now only as batch executables. RESULTS: Here we present GEVALT (GEnotype Visualization and ALgorithmic Tool), a software package designed to simplify and expedite the process of genotype analysis, by providing a common interface to several tasks relating to such analysis. GEVALT combines the strong visual abilities of Haploview with our quick and powerful algorithms for genotypes phasing (GERBIL), tag SNP selection (STAMPA) and permutation testing for evaluating significance of association. All of the above are provided in a visually appealing and interactive interface. CONCLUSION: GEVALT is an integrated viewer that uses state of the art phasing and tag SNP selection algorithms. By streamlining the application of GERBIL and STAMPA together with strong visualization for assessment of the results, GEVALT makes the algorithms accessible to the broad community of researchers in genetics.

The following problems arise in the analysis of biological networks: We have a boolean function of n variables, each of which has some default value. An experiment fixes the values of any subset of the variables, the remaining variables assume their default values, and the function value is the result of the experiment. How many experiments are needed to determine (reconstruct) the function? How many experiments that involve fixing at most q values are needed? What are the answers to these questions when an unknown subset of the variables are actually involved in the function? In the biological context, the variables are genes and the values are gene expression intensities. An experiment measures the gene levels under conditions that perturb the values of a subset of the genes. The goal is to reconstruct the particular logic (regulation function) by which a subset of the genes together regulate one target gene, using few experiments that involve minor perturbations. We study these questions under the assumption that all functions belong to a biologically motivated set of so‐called chain functions. We give optimal reconstruction schemes for several scenarios and show their application in reconstructing the regulation of galactose utilization in yeast.

MOTIVATION: Alternative splicing is a major component of the regulatory action on mammalian transcriptomes. It is estimated that over half of all human genes have more than one splice variant. Previous studies have shown that alternatively spliced exons possess several features that distinguish them from constitutively spliced ones. Recently, we have demonstrated that such features can be used to distinguish alternative from constitutive exons. In the current study, we used advanced machine learning methods to generate robust classifier of alternative exons. RESULTS: We extracted several hundred local sequence features of constitutive as well as alternative exons. Using feature selection methods we find seven attributes that are dominant for the task of classification. Several less informative features help to slightly increase the performance of the classifier. The classifier achieves a true positive rate of 50% for a false positive rate of 0.5%. This result enables one to reliably identify alternatively spliced exons in exon databases that are believed to be dominated by constitutive exons.

BACKGROUND: Gene expression microarrays are a prominent experimental tool in functional genomics which has opened the opportunity for gaining global, systems-level understanding of transcriptional networks. Experiments that apply this technology typically generate overwhelming volumes of data, unprecedented in biological research. Therefore the task of mining meaningful biological knowledge out of the raw data is a major challenge in bioinformatics. Of special need are integrative packages that provide biologist users with advanced but yet easy to use, set of algorithms, together covering the whole range of steps in microarray data analysis. RESULTS: Here we present the EXPANDER 2.0 (EXPression ANalyzer and DisplayER) software package. EXPANDER 2.0 is an integrative package for the analysis of gene expression data, designed as a 'one-stop shop' tool that implements various data analysis algorithms ranging from the initial steps of normalization and filtering, through clustering and biclustering, to high-level functional enrichment analysis that points to biological processes that are active in the examined conditions, and to promoter cis-regulatory elements analysis that elucidates transcription factors that control the observed transcriptional response. EXPANDER is available with pre-compiled functional Gene Ontology (GO) and promoter sequence-derived data files for yeast, worm, fly, rat, mouse and human, supporting high-level analysis applied to data obtained from these six organisms. CONCLUSION: EXPANDER integrated capabilities and its built-in support of multiple organisms make it a very powerful tool for analysis of microarray data. The package is freely available for academic users at http://www.cs.tau.ac.il/~rshamir/expander.

We present a new algorithm for the problems of genotype phasing and block partitioning. Our algorithm is based on a new stochastic model, and on the novel concept of probabilistic common haplotypes. We formulate the goals of genotype resolving and block partitioning as a maximum likelihood problem, and solve it by an EM algorithm. When applied to real biological SNP data, our algorithm outperforms two state of the art phasing algorithms. Our algorithm is also considerably more sensitive and accurate than a previous method in predicting and identifying disease association.

Mounting evidence shows that many protein complexes are conserved in evolution. Here we use conservation to find complexes that are common to yeast S. Cerevisiae and bacteria H. pylori. Our analysis combines protein interaction data, that are available for each of the two species, and orthology information based on protein sequence comparison. We develop a detailed probabilistic model for protein complexes in a single species, and a model for the conservation of complexes between two species. Using these models, one can recast the question of finding conserved complexes as a problem of searching for heavy subgraphs in an edge- and node-weighted graph, whose nodes are orthologous protein pairs.We tested this approach on the data currently available for yeast and bacteria and detected 11 significantly conserved complexes. Several of these complexes match very well with prior experimental knowledge on complexes in yeast only, and serve for validation of our methodology. The complexes suggest new functions for a variety of uncharacterized proteins. By identifying a conserved complex whose yeast proteins function predominantly in the nuclear pore complex, we propose that the corresponding bacterial proteins function as a coherent cellular membrane transport system. We also compare our results to two alternative methods for detecting complexes, and demonstrate that our methodology obtains a much higher specificity.

Abstract Summary: Protein Interaction VisualizatiOn Tool (PIVOT) is a visualization tool for protein–protein interactions. It allows the user to create personal data sets of interactions by combining information from private and public data sources. The user can gradually access the interactions' data using a clear interactive map that is focused on the researcher's protein of interest, and is reshaped and expanded in response to his/her queries. It also offers several visual enhancements and intelligent queries that help the user efficiently study it. PIVOT allows the user to search the interactions data set for paths connecting proteins that are expected to co-operate. The user can also employ PIVOT to predict unknown interactions among proteins, based on interactions among their homologous proteins in other species. Availability: Freely available for academic users, at http://www.cs.tau.ac.il/~rshamir/pivot Supplementary information: A demonstration video clip is available at http://www.cs.tau.ac.il/~rshamir/pivot/Demo.avi

The study of haplotypes and their diversity in a population is central to disease-association research. We study several problems arising in haplotype block partitioning. Our objective function is the total number of distinct haplotypes in blocks. We show that the problem is NP-hard when there are errors or missing data, and provide approximation algorithms for several of its variants. We also give an algorithm that solves the problem with high probability under a probabilistic model that allows noise and missing data. In addition, we study the multipopulation case, where one has to partition the haplotypes into populations and seek a different block partition in each one. We provide a heuristic for that problem and use it to analyze simulated and real data. On simulated data, our blocks resemble the true partition more than the blocks generated by the LD-based algorithm of Gabriel et al (2002). On single-population real data, we generate a more concise block description than do extant approaches, with better average LD within blocks. The algorithm also gives promising results on real two-population genotype data.

Perfect phylogeny is one of the fundamental models for studying evolution. We investigate the following variant of the model: The input is a species-characters matrix. The characters are binary and directed; i.e., a species can only gain characters. The difference from standard perfect phylogeny is that for some species the states of some characters are unknown.The question is whether one can complete the missing states in a way that admits a perfect phylogeny. The problem arises in classical phylogenetic studies, when some states are missing or undetermined. Quite recently, studies that infer phylogenies using inserted repeat elements in DNA gave rise to the same problem. Extant solutions for it take time O(n 2m ) for n species and m characters. We provide a graph theoretic formulation of the problem as a graph sandwich problem, and give near-optimal $\tilde{O}(nm)$-time algorithms for the problem. We also study the problem of finding a single, general solution tree, from which any other solution can be obtained by node splitting. We provide an algorithm to construct such a tree, or determine that none exists.

The modeling of transcription regulation programs is a major focus of today's biology. The challenge is to utilize diverse high-throughput data (gene expression, promoter binding site localization assays, protein expression) in order to infer the mechanistic models of transcription control. We propose a new model which integrates transcription factor-gene affinities, protein abundance and gene expression levels. Transcription factor binding site activity is represented by a dose-affinity-response function, and regulation is assumed to be a combinatorial function of the activities of the binding sites in the gene's promoter sites.We develop algorithms that infer the model given complete data and give a fast polynomial time algorithm under reasonable assumptions. We also show how to assess initial values of missing data (notably protein abundance) using a novel framework for active motif detection, which may be of independent interest. We test the various components of the framework on gene expression data related to carbohydrate metabolism in yeast. The results demonstrate the high specificity and sensitivity of the approach and its advantages over extant motif activity detection methods. We are also able to predict new active motifs in the galactose pathway.A key feature of our method is the global approach to transcription factor activity and to the relation between this activity and promoter signals. We use dozens of genes, with many different promoter signals and expression levels in order to draw conclusions on the function of a single transcription factor. This provides us the robustness necessary in order to overcome the considerable level of noise in the data.

MOTIVATION: A central step in the analysis of gene expression data is the identification of groups of genes that exhibit similar expression patterns. Clustering gene expression data into homogeneous groups was shown to be instrumental in functional annotation, tissue classification, regulatory motif identification, and other applications. Although there is a rich literature on clustering algorithms for gene expression analysis, very few works addressed the systematic comparison and evaluation of clustering results. Typically, different clustering algorithms yield different clustering solutions on the same data, and there is no agreed upon guideline for choosing among them. RESULTS: We developed a novel statistically based method for assessing a clustering solution according to prior biological knowledge. Our method can be used to compare different clustering solutions or to optimize the parameters of a clustering algorithm. The method is based on projecting vectors of biological attributes of the clustered elements onto the real line, such that the ratio of between-groups and within-group variance estimators is maximized. The projected data are then scored using a non-parametric analysis of variance test, and the score's confidence is evaluated. We validate our approach using simulated data and show that our scoring method outperforms several extant methods, including the separation to homogeneity ratio and the silhouette measure. We apply our method to evaluate results of several clustering methods on yeast cell-cycle gene expression data. AVAILABILITY: The software is available from the authors upon request.

MOTIVATION: Microarrays have become a central tool in biological research. Their applications range from functional annotation to tissue classification and genetic network inference. A key step in the analysis of gene expression data is the identification of groups of genes that manifest similar expression patterns. This translates to the algorithmic problem of clustering genes based on their expression patterns. RESULTS: We present a novel clustering algorithm, called CLICK, and its applications to gene expression analysis. The algorithm utilizes graph-theoretic and statistical techniques to identify tight groups (kernels) of highly similar elements, which are likely to belong to the same true cluster. Several heuristic procedures are then used to expand the kernels into the full clusters. We report on the application of CLICK to a variety of gene expression data sets. In all those applications it outperformed extant algorithms according to several common figures of merit. We also point out that CLICK can be successfully used for the identification of common regulatory motifs in the upstream regions of co-regulated genes. Furthermore, we demonstrate how CLICK can be used to accurately classify tissue samples into disease types, based on their expression profiles. Finally, we present a new java-based graphical tool, called EXPANDER, for gene expression analysis and visualization, which incorporates CLICK and several other popular clustering algorithms. AVAILABILITY: http://www.cs.tau.ac.il/~rshamir/expander/expander.html

Abstract A PCR primer sequence is called degenerate if some of its positions have several possible bases. The degeneracy of the primer is the number of unique sequence combinations it contains. We study the problem of designing a pair of primers with prescribed degeneracy that match a maximum number of given input sequences. Such problems occur when studying a family of genes that is known only in part, or is known in a related species. We prove that various simplified versions of the problem are hard, show the polynomiality of some restricted cases, and develop approximation algorithms for one variant. Based on these algorithms, we implemented a program called hyden for designing highly-degenerate primers for a set of genomic sequences. We report on the success of the program in an experimental scheme for identifying all human olfactory receptor (OR) genes. In that project, hyden was used to design primers with degeneracies up to 1010 that amplified with high specificity many novel genes of that family, tripling the number of OR genes known at the time. Availability: Available on request from the authors. Contact: [email protected]; [email protected] Keywords: PCR primer design; degenerate primers; optimization; human olfactory subgenome; protein families.

In gene expression data, a bicluster is a subset of the genes exhibiting consistent patterns over a subset of the conditions. We propose a new method to detect significant biclusters in large expression datasets. Our approach is graph theoretic coupled with statistical modelling of the data. Under plausible assumptions, our algorithm is polynomial and is guaranteed to find the most significant biclusters. We tested our method on a collection of yeast expression profiles and on a human cancer dataset. Cross validation results show high specificity in assigning function to genes based on their biclusters, and we are able to annotate in this way 196 uncharacterized yeast genes. We also demonstrate how the biclusters lead to detecting new concrete biological associations. In cancer data we are able to detect and relate finer tissue types than was previously possible. We also show that the method outperforms the biclustering algorithm of Cheng and Church (2000).

Most shotgun sequencing projects undergo a long and costly phase of finishing, in which a partial assembly forms several contigs whose order, orientation and relative distance is unknown. We propose here a new technique that supplements the shotgun assembly data by cheap and simple complete restriction digests of the target. By computationally combining information from the contig sequences and the fragment sizes measured for several different enzymes, we seek to form a "scaffold" on which the contigs will be placed in their correct orientation, order and distance. We give a heuristic search algorithm for solving the problem and report on promising preliminary simulation results. The key to the success of the search scheme is the very rapid solution of its two time-critical subproblems that are solved precisely in linear time.Our simulations indicate that with noise levels of some 3% relative error in measuring fragment sizes, using five enzymes, most datasets of 20 contigs can be correctly ordered, and the remaining ones have most of their pairs of neighboring contigs correct. Hence, the technique has a potential to provide real help to finishing. Even when the target clone remains unfinished, the ability to order and orient the contigs correctly makes the partial assembly both more accessible and more useful for biologists.

Sequencing by hybridization (SBH) is a DNA sequencing technique, in which the sequence is reconstructed using its k-mer content. This content, which is called the spectrum of the sequence, is obtained by hybridization to a universal DNA array. Standard universal arrays contain all k-mers for some fixed k, typically 8 to 10. Currently, in spite of its promise and elegance, SBH is not competitive with standard gel-based sequencing methods. This is due to two main reasons: lack of tools to handle realistic levels of hybridization errors, and an inherent limitation on the length of uniquely reconstructible sequence by standard universal arrays.In this paper we deal with both problems. We introduce a simple polynomial reconstruction algorithm which can be applied to spectra from standard arrays and has provable performance in the presence of both false negative and false positive errors. We also propose a novel design of chips containing universal bases, that differs from the one proposed by Preparata et al. We give a simple algorithm that uses spectra from such chips to reconstruct with high probability random sequences of length lower only by a squared log factor compared to the information theoretic bound. Our algorithm is very robust to errors, and has a provable performance even if there are both false negative and false positive errors. Simulations indicate that its sensitivity to errors is also very small in practice.

Sequencing by Hybridization is a method for reconstructing a DNA sequence based on its k-mer content. This content, called the spectrum of the sequence, can be obtained from hybridization with a universal DNA chip. However, even with a sequencing chip containing all 4 9 9-mers and assuming no hybridization errors, only about 400 bases-long sequences can be reconstructed unambiguously. Drmanac et al. suggested sequencing long DNA targets by obtaining spectra of many short overlapping fragments of the target, inferring their relative positions along the target and then computing spectra of subfragments that are short enough to be uniquely recoverable. Drmanac et al. do not treat the realistic case of errors in the hybridization process. In this paper we study the effect of such errors. We show that the probability of ambiguous reconstruction in the presence of (false negative) errors is close to the probability in the errorless case. More precisely, the ratio between these probabilities is 1 + O(p/(1 − p) 4 · 1/d) where d is the average length of subfragments, and p is the probability of a false negative. We also obtain lower and upper bounds for the probability of unambiguous reconstruction based on errorless spectrum. For realistic chip sizes, these bounds are tighter than those given by Arratia et al. Finally, we report results on simulations with real DNA sequences, showing that even in the presence of 50 % false negative errors, a target of cosmid length can be recovered with less than 0.1 % miscalled bases. 1

In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a graph, where a modification can be a deletion or an addition of a vertex or an edge. The objective is to maintain a representation of the graph as long as it remains a proper interval graph, and to detect when it ceases to be so. The representation should enable one to efficiently construct a realization of the graph by an inclusion-free family of intervals. This problem has important applications in physical mapping of DNA. We give a near-optimal fully dynamic algorithm for this problem. It operates in O(log n) worst-case time per edge insertion or deletion. We prove a close lower bound of $\Omega(\log n/(\log\log n+\log b))$ amortized time per operation in the cell probe model with word-size b. We also construct optimal incremental and decremental algorithms for the problem, which handle each edge operation in O(1) time. As a byproduct of our algorithm, we solve in O(log n) worst-case time the problem of maintaining connectivity in a dynamically changing proper interval graph.

In the minimum fill-in problem, one wishes to find a set of edges of smallest size, whose addition to a given graph will make it chordal. The problem has important applications in numerical algebra and has been studied intensively since the 1970s. We give the first polynomial approximation algorithm for the problem. Our algorithm constructs a triangulation whose size is at most eight times the optimum size squared. The algorithm builds on the recent parameterized algorithm of Kaplan, Shamir, and Tarjan for the same problem. For bounded degree graphs we give a polynomial approximation algorithm with a polylogarithmic approximation ratio. We also improve the parameterized algorithm.

We have developed a novel algorithm for cluster analysis that is based on graph theoretic techniques. A similarity graph is defined and clusters in that graph correspond to highly connected subgraphs. A polynomial algorithm to compute them efficiently is presented. Our algorithm produces a clustering with some provably good properties. The application that motivated this study was gene expression analysis, where a collection of cDNAs must be clustered based on their oligonucleotide fingerprints. The algorithm has been tested intensively on simulated libraries and was shown to outperform extant methods. It demonstrated robustness to high noise levels. In a blind test on real cDNA fingerprint data the algorithm obtained very good results. Utilizing the results of the algorithm would have saved over 70% of the cDNA sequencing cost on that data set. 1 Introduction Cluster analysis seeks grouping of data elements into subsets, so that elements in the same subset are in some sense more cl...

A new algorithm for the construction of physical maps from hybridization fingerprints of short oligonucleotide probes has been developed. Extensive simulations in high-noise scenarios show that the algorithm produces an essentially completely correct map in over 95% of trials. Tests for the influence of specific experimental parameters demonstrate that the algorithm is robust to both false positive and false negative experimental errors. The algorithm was also tested in simulations using real DNA sequences of E. coli, B. subtilis, M. tuberculosis, S. cerevisiae, C. elegans, and H. sapiens. To overcome the non-randomness of probe frequencies in these sequences, probes were preselected based on sequence statistics and a screening process of the hybridization data was developed. With these modifications, the algorithm produced very encouraging results. A preliminary version of the paper is to appear in Proc. RECOMB 99. y Department of Computer Science, Sackler Faculty of Ex...

We give a quadratic time algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

We study the parameterized complexity of three NP-hard graph completion problems. The minimum fill-in problem asks if a graph can be triangulated by adding at most k edges. We develop O(ck m) and O(k2mn+f(k)) algorithms for this problem on a graph with n vertices and m edges. Here f(k) is exponential in k and the constants hidden by the big-O notation are small and do not depend on k. In particular, this implies that the problem is fixed-parameter tractable (FPT). The proper interval graph completion problem, motivated by molecular biology, asks if a graph can be made proper interval by adding no more than k edges. We show that the problem is FPT by providing a simple search-tree-based algorithm that solves it in O(ck m)-time. Similarly, we show that the parameterized version of the strongly chordal graph completion problem is FPT by giving an O(ck m log n)-time algorithm for it. All of our algorithms can actually enumerate all possible k-completions within the same time bounds.

Optical mapping is a novel technique for determining the restriction sites on a DNA molecule by directly observing a number of partially digested copies of the molecule under a light microscope. The problem is complicated by uncertainty as to the orientation of the molecules and by erroneous detection of cuts. In this paper we study the problem of constructing a restriction map based on optical mapping data. We give several variants of a polynomial reconstruction algorithm, as well as an algorithm that is exponential in the number of cut sites, and hence is appropriate only for small number of cut sites. We give a simple probabilistic model for data generation and for the errors and prove probabilistic upper and lower bounds on the number of molecules needed by each algorithm in order to obtain a correct map, expressed as a function of the number of cut sites and the error parameters. To the best of our knowledge, this is the first probabilistic analysis of algorithms for the problem. ...

Abstract. In the minimum fill-in problem, one wishes to find a set of edges of smallest size, whose addition to a given graph will make it chordal. The problem has important applications in numerical algebra and has been studied intensively since the 1970s. We give the first polynomial approximation algorithm for the problem. Our algorithm constructs a triangulation whose size is at most eight times the optimum size squared. The algorithm builds on the recent parameterized algorithm of Kaplan, Shamir, and Tarjan for the same problem. For bounded degree graphs we give a polynomial approximation algorithm with a polylogarithmic approximation ratio. We also improve the parameterized algorithm.

No abstract available.

We study the following problem: given an interval graph, does it have a realization which satisfies additional constraints on the distances between interval endpoints? This problem arises in numerous applications in which topological information on intersection of pairs of intervals is accompanied by additional metric information on their order, distance, or size. An important application is physical mapping, a central challenge in the human genome project. Our results are (1) a polynomial algorithm for the problem on interval graphs which admit a unique clique order (UCO graphs). This class of graphs properly contains all prime interval graphs. (2) In case all constraints are upper and lower bounds on individual interval lengths, the problem on UCO graphs is linearly equivalent to deciding if a system of difference inequalities is feasible. (3) Even if all the constraints are prescribed lengths of individual intervals, the problem is NP-complete. Hence, problems (1) and (2) are also NP-complete on arbitrary interval graphs.

We study two related problems motivated by molecular biology. • Given a graph G and a constant k, does there exist a supergraph $G'$ of G that is a unit interval graph and has clique size at most k? • Given a graph G and a proper k-coloring c of G, does there exist a supergraph $G'$ of G that is properly colored by c and is a unit interval graph? We show that those problems are polynomial for fixed k. On the other hand, we prove that the first problem is equivalent to deciding if the bandwidth of G is at most $k - 1$. Hence, it is NP-hard and $W[t]$-hard for all t. We also show that the second problem is $W[1]$-hard for all t-hard. This implies that for fixed k, both of the problems are unlikely to have an $O(n^\alpha )$ algorithm, where a is a constant independent of k. A central tool in our study is a new graph-theoretic parameter closely related to pathwidth. An unexpected useful consequence is the equivalence of this parameter to the bandwidth of the graph.

We study the parameterized complexity of several NP-Hard graph completion problems: The minimum fill-in problem is to decide if a graph can be triangulated by adding at most k edges. We develop an O(k/sup 5/ mn+f(K)) algorithm for the problem on a graph with n vertices and m edges. In particular, this implies that the problem is fixed parameter tractable (FPT). proper interval graph completion problems, motivated by molecular biology, ask for adding edges in order to obtain a proper interval graph, so that a parameter in that graph does not exceed k. We show that the problem is FPT when k is the number of added edges. For the problem where k is the clique size, we give an O(f(k)n/sup k-1/) algorithm, so it is polynomial for fixed k. On the other hand, we prove its hardness in the parameterized hierarchy, so it is probably not FPT. Those results are obtained even when a set of edges which should not be added is given. That set can be given either explicitly or by a proper vertex coloring which the added edges should respect.>

Temporal events are regarded here as intervals on a time line, This paper deals with problems m reasoning about such intervals when the prccisc topological relationship between them is unknown or only partially specified, This work unifies notions of interval algebras in artificial intelligence with those of interval orders and mterwd gr~phs m combmatorlcs.The satqfahihty, znuumal Iabeltng, all solutLons.and all rcakatlons problems we considered for temporal (internal ) datti.Several versions are investigated by restricting the possible interval relationships yielding different complexity results, We show that even when the temporal data comprises of subsets of relatlons based on mtersectlon and precedence only, the satisfiabdlty question IS NP-complete.On the positive side, we give efficient algorithms for several restrictions of the problem.In the process, the irzterLa/ ,qrap/z satzdwzc/z problem is introduced, and is shown to be NP-complete This problem IS also important in molecular hlology, where it arlscs In physical mapping of DNA material.

Data flow machines whose task graphs are acyclic can be transformed into synchronous machines, thereby increasing pipelining and throughput. This is achieved by introducing delays or buffers on certain lines, so that the resulting graph is balanced, i.e., travel times along any two paths with common endpoints are the same. The buffer assignment problem is how to balance a rooted acyclic data flow graph with a minimum number of buffer units. Recently, an integer programming decomposition procedure was proposed for this problem. The decomposition was introduced in an attempt to circumvent the exponential blowup typical of integer programming algorithms. It is shown that the buffer assignment problem can in fact be solved to optimality in low-degree polynomial time. The result is obtained by a sequence of reformulations of the problem, leading to models to which simple and efficient network flow procedures can be successfully applied.>