Generalized nucleus segmentation techniques can contribute greatly to reducing the time to develop and validate visual biomarkers for new digital pathology datasets. We summarize the results of MoNuSeg 2018 Challenge whose objective was to develop generalizable nuclei segmentation techniques in digital pathology. The challenge was an official satellite event of the MICCAI 2018 conference in which 32 teams with more than 80 participants from geographically diverse institutes participated. Contestants were given a training set with 30 images from seven organs with annotations of 21,623 individual nuclei. A test dataset with 14 images taken from seven organs, including two organs that did not appear in the training set was released without annotations. Entries were evaluated based on average aggregated Jaccard index (AJI) on the test set to prioritize accurate instance segmentation as opposed to mere semantic segmentation. More than half the teams that completed the challenge outperformed a previous baseline. Among the trends observed that contributed to increased accuracy were the use of color normalization as well as heavy data augmentation. Additionally, fully convolutional networks inspired by variants of U-Net, FCN, and Mask-RCNN were popularly used, typically based on ResNet or VGG base architectures. Watershed segmentation on predicted semantic segmentation maps was a popular post-processing strategy. Several of the top techniques compared favorably to an individual human annotator and can be used with confidence for nuclear morphometrics.

IEF LC-MS/MS is an analytical method that incorporates a two-step sample separation prior to MS identification of proteins. When analyzing complex samples this preparatory separation allows for higher analytical depth and improved quantification accuracy of proteins. However, cost and analysis time are greatly increased as each analyzed IEF fraction is separately profiled using LC-MS/MS. We propose an approach that selects a subset of IEF fractions for LC-MS/MS analysis that is highly informative in the context of a group of proteins of interest. Specifically, our method allows a significant reduction in cost and instrument time as compared to the standard protocol of running all fractions, with little compromise to coverage. We develop algorithmics to optimize the selection of the IEF fractions on which to run LC-MS/MS. We translate the fraction optimization task to Minimum Set Cover, a well-studied NP-hard problem. We develop heuristic solutions and compare them in terms of effectiveness and running times. We provide examples to demonstrate advantages and limitations of each algorithmic approach. Finally, we test our methodology by applying it to experimental data obtained from IEF LC-MS/MS analysis of yeast and human samples. We demonstrate the benefit of this approach for analyzing complex samples with a focus on different protein sets of interest.

IEF LC-MS/MS (Iso-Electric-Focusing Liquid-Chromatography Tandem-Mass-Spectrometry) is an analytical method that incorporates a two-step sample separation prior to MS identification of proteins. When analyzing complex samples this preparatory separation allows for higher analytical depth and improved quantification accuracy of proteins and PTMs. IEF fractionation builds upon isoelectric point (pI) differences between peptides or proteins. In standard IEF LC-MS/MS, each fraction is separately profiled using LC-MS/MS. The cost of the complete assay, therefore, is strongly dependent on the number of pI fractions being analyzed. Commonly, studies are focused on a specific group of proteins. We propose an approach that selects a subset of fractions for LC-MS/MS analysis that is highly informative in the context of the proteins of interest. Specifically, our method allows a significant reduction in cost and instrument time as compared to the standard protocol of running all fractions, with little compromise to coverage. We develop algorithmics to optimize the selection of the IEF fractions on which to run LC-MS/MS. We translate the fraction optimization task to Minimum Set Cover (MSC), a well-studied NP-hard problem. We develop heuristic solutions and compare them in terms of effectiveness and of practical running times. We provide examples to demonstrate advantages and limitations of each algorithmic approach. Finally, we test our methodology by applying it to experimental data obtained from IEF LC-MS/MS analysis of yeast and human samples. We demonstrate the benefit of this approach for analyzing complex samples with a focus on different protein sets of interest.

We study a design and optimization problem that occurs, for example, when single nucleotide polymorphisms (SNPs) are to be genotyped using a universal DNA tag array. The problem of optimizing the universal array to avoid disruptive cross-hybridization between universal components of the system was addressed in a previous work. However, cross-hybridization can also occur assay-specifically, due to unwanted complementarity involving assay-specific components. Here we examine the problem of identifying the most economic experimental configuration of the assay-specific components that avoids cross-hybridization. Our formalization translates this problem into the problem of covering the vertices of one side of a bipartite graph by a minimum number of balanced subgraphs of maximum degree 1. We show that the general problem is NP-complete. However, in the real biological setting the vertices that need to be covered have degrees bounded by d. We exploit this restriction and develop an O(d)-approximation algorithm for the problem. We also give an O(d)-approximation for a variant of the problem in which the covering subgraphs are required to be vertex-disjoint. In addition, we propose a stochastic model for the input data and use it to prove a lower bound on the cover size. We complement our theoretical analysis by implementing two heuristic approaches and testing their performance on simulated and real SNP data.

This paper concerns the discovery of patterns in gene expression matrices, in which each element gives the expression level of a given gene in a given experiment. Most existing methods for pattern discovery in such matrices are based on clustering genes by comparing their expression levels in all experiments, or clustering experiments by comparing their expression levels for all genes. Our work goes beyond such global approaches by looking for local patterns that manifest themselves when we focus simultaneously on a subset G of the genes and a subset T of the experiments. Specifically, we look for order-preserving submatrices (OPSMs), in which the expression levels of all genes induce the same linear ordering of the experiments (we show that the OPSM search problem is NP-hard in the worst case). Such a pattern might arise, for example, if the experiments in T represent distinct stages in the progress of a disease or in a cellular process, and the expression levels of all genes in G vary across the stages in the same way.We define a probabilistic model in which an OPSM is hidden within an otherwise random matrix. Guided by this model we develop an efficient algorithm for finding the hidden OPSM in the random matrix. In data generated according to the model the algorithm recovers the hidden OPSM with very high success rate. Application of the methods to breast cancer data seems to reveal significant local patterns.Our algorithm can be used to discover more than one OPSM within the same data set, even when these OPSMs overlap. It can also be adapted to handle relaxations and extensions of the OPSM condition. For example, we may allow the different rows of G x T to induce similar but not identical orderings of the columns, or we may allow the set T to include more than one representative of each stage of a biological process.

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.

Recent studies (Alizadeh et al, [1]; Bittner et al,[5]; Golub et al, [11]) demonstrate the discovery of putative disease subtypes from gene expression data. The underlying computational problem is to partition the set of sample tissues into statistically meaningful classes. In this paper we present a novel approach to class discovery and develop automatic analysis methods. Our approach is based on statistically scoring candidate partitions according to the overabundance of genes that separate the different classes. Indeed, in biological datasets, an overabundance of genes separating known classes is typically observed. we measure overabundance against a stochastic null model. This allows for highlighting subtle, yet meaningful, partitions that are supported on a small subset of the genes.

Constantly improving gene expression profiling technologies are expected to provide understanding and insight into cancer related cellular processes. Gene expression data is also expected to significantly and in the development of efficient cancer diagnosis and classification platforms. In this work we examine two sets of gene expression data measured across sets of tumor and normal clinical samples One set consists of 2,000 genes, measured in 62 epithelial colon samples [1]. The second consists of ≈ 100,000 clones, measured in 32 ovarian samples (unpublished, extension of data set described in [26]).

Custom-designed DNA arrays offer the possibility of simultaneously monitoring thousands of hybridization reactions These arrays show great potential for many medical and scientific applications such as polymorphism analysis and genotyping. Relatively high costs are associated with the need to specifically design and synthesize problem specific arrays. Recently, an alternative approach was suggested that utilizes fixed, universal arrays. This approach presents an interesting design problem—the arrays should contain as many probes as possible, while minimizing experimental errors caused by cross-hybridization. We use a simple thermodynamic model to cast this design problem in a formal mathematical framework. Employing new combinatorial ideas, we derive an efficient construction for the design problem, and prove that our construction is near-optimal.

With the advance of hybridization array technology researchers can measure expression levels of sets of genes across different conditions and over time.Analysis of data produced by such experiments offers potential insight into gene function and regulatory mechanisms.We describe the problem of clustering multi-condition gene expression patterns.We define an appropriate stochastic model of the input, and use this model for performance evaluations.We present a O(n(log(n))c)time algorithm that recovers cluster structures with high probability, in this model, where n is the number of genes.In addition to the theoretical treatment, we suggest a practical heuristic approach based on the same ideas.We demonstrate the algorithm's performance first on simulated data, and then on actual gene expression data.

No abstract available.

Article Free Access Share on On constructing radiation hybrid maps (extended abstract) Authors: Amir Ben-Dor Dept. of Computer Science, Technion, Haifa 32000, Israel Dept. of Computer Science, Technion, Haifa 32000, IsraelView Profile , Benny Chor Dept. of Computer Science, Technion, Haifa 32000, Israel Dept. of Computer Science, Technion, Haifa 32000, IsraelView Profile Authors Info & Claims RECOMB '97: Proceedings of the first annual international conference on Computational molecular biologyJanuary 1997 Pages 17–26https://doi.org/10.1145/267521.267525Online:19 January 1997Publication History 4citation228DownloadsMetricsTotal Citations4Total Downloads228Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We study the problem of packet routing in synchronous networks. We put forward a notion of greedy hot-potato routing algorithms and devise techniques for analyzing such algorithms. A greedy hot-potato routing algorithm is one where ffl The processors have no buffer space for storing delayed packets. Therefore, each packet must leave any intermediate processor at the step following its arrival. ffl Packets always advance towards their destination if they can. Namely, a packet must leave its current intermediate node via a link which takes it closer to its destination, unless all these links are taken by other packets. Moreover, in this case all these other packets must advance towards their destinations. We use potential function analysis to obtain an upper bound of O(n p k) on the running time of a wide class of algorithms in the 2-dimensional n \\Theta n mesh, for routing problems with total of k packets. The same techniques can be generalized to obtain an upper bound of O(exp(d)...