MOTIVATION: Whole genome sequencing of paired-end reads can be applied to characterize the landscape of large somatic rearrangements of cancer genomes. Several methods for detecting structural variants with whole genome sequencing data have been developed. So far, none of these methods has combined information about abnormally mapped read pairs connecting rearranged regions and associated global copy number changes automatically inferred from the same sequencing data file. Our aim was to create a computational method that could use both types of information, i.e. normal and abnormal reads, and demonstrate that by doing so we can highly improve both sensitivity and specificity rates of structural variant prediction. RESULTS: We developed a computational method, SV-Bay, to detect structural variants from whole genome sequencing mate-pair or paired-end data using a probabilistic Bayesian approach. This approach takes into account depth of coverage by normal reads and abnormalities in read pair mappings. To estimate the model likelihood, SV-Bay considers GC-content and read mappability of the genome, thus making important corrections to the expected read count. For the detection of somatic variants, SV-Bay makes use of a matched normal sample when it is available. We validated SV-Bay on simulated datasets and an experimental mate-pair dataset for the CLB-GA neuroblastoma cell line. The comparison of SV-Bay with several other methods for structural variant detection demonstrated that SV-Bay has better prediction accuracy both in terms of sensitivity and false-positive detection rate. AVAILABILITY AND IMPLEMENTATION: https://github.com/InstitutCurie/SV-Bay CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Genomic sequences are highly redundant and contain many types of repetitive DNA. Fuzzy tandem repeats (FTRs) are of particular interest. They are found in regulatory regions of eukaryotic genes and are reported to interact with transcription factors. However, accurate assessment of FTR occurrences in different genome segments requires specific algorithm for efficient FTR identification and classification. RESULTS: We have obtained formulas for P-values of FTR occurrence and developed an FTR identification algorithm implemented in TandemSWAN software. Using TandemSWAN we compared the structure and the occurrence of FTRs with short period length (up to 24 bp) in coding and non-coding regions including UTRs, heterochromatic, intergenic and enhancer sequences of Drosophila melanogaster and Drosophila pseudoobscura. Tandems with period three and its multiples were found in coding segments, whereas FTRs with periods multiple of six are overrepresented in all non-coding segment. Periods equal to 5-7 and 11-14 were characteristic of the enhancer regions and other non-coding regions close to genes. AVAILABILITY: TandemSWAN web page, stand-alone version and documentation can be found at http://bioinform.genetika.ru/projects/swan/www/ SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Many important RNA molecules contain pseudoknots, which are generally excluded by the definition of the secondary structure, mainly for computational reasons. Still, most existing algorithms for secondary structure prediction are not satisfactory in results and complexities, even when pseudoknots are not allowed. We present an algorithm, called P-DCFold, for the prediction of RNA secondary structures including all kinds of pseudoknots. It is based on the comparative approach. The helices are searched recursively, from more "likely" to less "likely", using the "Divide and Conquer" approach. This approach, which allows to limit the amount of searching, is possible when only non-interleaved helices are searched for. The pseudoknots are therefore searched in several steps, each helix of the pseudoknot being selected in a different step. P-DCFold has been applied to tmRNA and RnaseP sequences. In less than two seconds, their respective secondary structures, including their pseudoknots, have been recovered very efficiently.

Evaluation of the frequency of occurrences of a given set of patterns in a DNA sequence has numerous applications and has been extensively studied recently. We provide a unified framework for this evaluation that adapts to various constraints and allow to extend previous results. We assume successively that the patterns may, then may not, overlap. We derive asymptotic and exact formulae for the moments in a Markovian model. We show that our formulae, that occasionnally simplify previous results, are computable at low cost, which makes them useful for practical applications. 1 Introduction Repeated patterns and related phenomena in sequences (also called words or strings) are studied in molecular biology. A survey on various methods can be found in [Li97]. One fundamental question that arises is the frequency of pattern occurrences in another string known as the text. This question is addressed below for a set of patterns (H i ) and various assumptions on the counting of possible overl...

A precise asymptotic expansion of the variance of the size of a trie built on random binary strings is presented. This data structure appears in some hashing schemes and communications protocols. The variance is asymptotically linear, and numerical results are given. The reader is referred to an earlier work for formal proofs.>

The author presents an analysis of trie hashing for alphanumerical keys. He proposes a variant that uses a binary code and an asymptotic analysis of the size of the index. This provides, for biased distribution, a computable formula that predicts the size of the index as a function of the frequencies of the characters and the transition frequencies between these characters. These results are confirmed by a simulation. The author considers a Markovian probabilistic method and uses the Mellin transform.>