Richard Karp | PubMed Health

PubMed2026

The chromosomal genome sequence of the lesser starlet coral, Siderastrea radians (Pallas, 1766) (Scleractinia: Rhizangiidae) and its associated microbial metagenome sequences.

We present a genome assembly from a specimen of Siderastrea radians (lesser starlet coral; Cnidaria; Anthozoa; Scleractinia; Rhizangiidae). The genome sequence has a total length of 807.19 megabases. Most of the assembly (94.17%) is scaffolded into 14 chromosomal pseudomolecules. The mitochondrial genome has also been assembled, with a length of 19.38 kilobases. Gene annotation of this assembly by Ensembl identified 47 051 protein-coding genes. From the metagenome data, we recovered two binned metagenomes assigned to the bacterial phylum Bacteroidota and class Bacteroidia.

Scleractinia↗

PubMed2003

Discovering local structure in gene expression data: the order-preserving submatrix problem.

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 a very high success rate. Application of the methods to breast cancer data seem to reveal significant local patterns.

Algorithms↗