An efficient exact algorithm for planted motif search on large DNA sequence datasets.

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.

LDSSNV: A Linkage Disequilibrium-Based Method for the Detection of Somatic Single-Nucleotide Variants.

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.