Search

Motivation With the wide availability of whole-genome genotype data, there is an increasing need for conducting genetic genealogical searches efficiently. Computationally, this task amounts to identifying shared DNA segments between a query individual and a very large panel containing millions of haplotypes. The celebrated Positional Burrows-Wheeler Transform (PBWT) data structure is a pre-computed index of the panel that enables constant time matching at each position between one haplotype and an arbitrarily large panel. However, the existing algorithm (Durbin’s Algorithm 5) can only identify set-maximal matches, the longest matches ending at any location in a panel, while in real genealogical search scenarios, multiple ‘good enough’ matches are desired. Results In this work, we developed two algorithmic extensions of Durbin’s Algorithm 5, that can find all L-long matches, matches longer than or equal to a given length L, between a query and a panel. In the first algorithm, PBWT-Query, we introduce ‘virtual insertion’ of the query into the PBWT matrix of the panel, and then scanning up and down for the PBWT match blocks with length greater than L. In our second algorithm, L-PBWT-Query, we further speed up PBWT-Query by introducing additional data structures that allow us to avoid iterating through blocks of incomplete matches. The efficiency of PBWT-Query and L-PBWT-Query is demonstrated using the simulated data and the UK Biobank data. Our results show that our proposed algorithms can detect related individuals for a given query efficiently in very large cohorts which enables a fast on-line query search. Availability and implementation genome.ucf.edu/pbwt-query Supplementary information Supplementary data are available at Bioinformatics online.

The lncRNA SPRIGHTLY interacts with the intronic regions of unprocessed mRNA precursors of its target mRNAs., Molecular mechanisms by which long noncoding RNA (lncRNA) molecules may influence cancerous condition are poorly understood. The aberrant expression of SPRIGHTLY lncRNA, encoded within the drosophila gene homolog Sprouty-4 intron, is correlated with a variety of cancers, including human melanomas. We demonstrate by SHAPE-seq and dChIRP that SPRIGHTLY RNA secondary structure has a core pseudoknotted domain. This lncRNA interacts with the intronic regions of six pre-mRNAs: SOX5, SMYD3, SND1, MEOX2, DCTN6, and RASAL2, all of which have cancer-related functions. Hemizygous knockout of SPRIGHTLY by CRISPR (clustered regularly interspaced short palindromic repeats)/Cas9 in melanoma cells significantly decreases SPRIGHTLY lncRNA levels, simultaneously decreases the levels of its interacting pre-mRNA molecules, and decreases anchorage-independent growth rate of cells and the rate of in vivo tumor growth in mouse xenografts. These results provide the first demonstration of an lncRNA’s three-dimensional coordinating role in facilitating cancer-related gene expression in human melanomas.