Single nucleotide variants (SNVs) are very common in human genome and pose a significant effect on cellular proliferation and tumorigenesis in various cancers. Somatic variant and germline variant are the two forms of SNVs. They are the major drivers of inherited diseases and acquired tumors respectively. A reasonable analysis of the next generation sequencing data profiles from cancer genomes could provide crucial information for cancer diagnosis and treatment. Accurate detection of SNVs and distinguishing the two forms are still considered challenging tasks in cancer analysis. Herein, we propose a new approach, LDSSNV, to detect somatic SNVs without matched normal samples. LDSSNV predicts SNVs by training the XGboost classifier on a concise combination of features and distinguishes the two forms based on linkage disequilibrium which is a trait between germline mutations. LDSSNV provides two modes to distinguish the somatic variants from germline variants, the single-mode and multiple-mode by respectively using a single tumor sample and multiple tumor samples. The performance of the proposed method is assessed on both simulation data and real sequencing datasets. The analysis shows that the LDSSNV method outperforms competing methods and can become a robust and reliable tool for analyzing tumor genome variation.

DNA motif is the pattern shared by similar fragments in DNA sequences, which plays a key role in regulating gene expression, and DNA motif discovery has become a key research topic. Exact planted ( l,d )-motif search (PMS) is one of the motif discovery approaches, which aims to find from t sequences all the ( l,d )-motifs that are motifs of l length appearing in at least qt sequences with at most d mismatches. The existing exact PMS algorithms are only suitable for small datasets of DNA sequences. The development of high-throughput sequencing technology generates vast amount of DNA sequence data, which brings challenges to solving exact PMS problems efficiently. Therefore, we propose an efficient exact PMS algorithm called PMmotif for large datasetsof DNA sequences, after analyzing the time complexity of the existing exact PMS algorithms. PMmotif finds ( l,d ) -motifs with strategy by searching the branches on the pattern tree that may contain ( l,d ) -motifs. It is verified by experiments that the running time ratio of the existing excellentPMS algorithmstoPMmotif isbetween14.83and 58.94. In addition, for the first time, PMmotif can solve the (15,5) and(17,6) challenge problem instances on large DNA sequence datasets within 24 hours.

Copy number variation (CNV) has been increasingly recognized as a type of genomic/genetic variation that plays a critical role in driving human diseases and genomic diversity. CNV detection and analysis from cancer genomes could provide crucial information for cancer diagnosis and treatment. There still remain considerable challenges in the control-free calling of CNVs accurately in cancer analysis, although advances in next-generation sequencing (NGS) technology have been inspiring the development of various computational methods. Herein, we propose a new read-depth (RD)-based approach, called CNVbd, to explore CNVs from single tumor samples of NGS data. CNVbd assembles three statistics drawn from the density peak clustering algorithm and isolation forest algorithm based on the denoised RD profile and establishes a back propagation neural network model to predict CNV bins. In addition, we designed a revision process and a boundary search algorithm to correct the false-negative predictions and refine the CNV boundaries. The performance of the proposed method is assessed on both simulation data and real sequencing datasets. The analysis shows that CNVbd is a very competitive method and can become a robust and reliable tool for analyzing CNVs in the tumor genome.

Let $G$ be a simple connected graph of order $n$ and $\partial(G)$ is the spectral radius of the distance matrix $D(G)$ of $G$. The transmission $D_i$ of vertex $i$ is the $i$-th row sum of $D(G)$. Denote by $D_{\max}(G)$ the maximum of transmissions over all vertices of $G$, and $\partial^Q(G)$ is the spectral radius of the distance signless Laplacian matrix $D(G)+\mbox{diag}(D_1,D_2,\ldots,D_n)$. In this paper, we present a sharp lower bound of $2D_{\max}(G)-\partial^Q(G)$ among all $n$-vertex connected graphs, and characterize the extremal graphs. Furthermore, we give the minimum values of respective $D_{\max}(G)-\partial(G)$ and $2D_{\max}(G)-\partial^Q(G)$ on trees and characterize the extremal trees.