In genome/transcriptome assembly and similar scenarios, we are usually given millions of fragments and ready to assemble them into longer contigs by first aligning them to a reference sequence. Since one fragment may be aligned to different locations due to sequence repetition, mutation, and artificial factors the alignment tools concern, users of alignment tools must make their own strategies for choosing one location for each fragment. Commonly used strategies usually assign the same value for each location or assign values according to alignment scores without taking into account the optimization. Considering that a reasonable strategy should ensure that the coverage at each base is similar, we depict the problem of assigning fragments to properly aligned positions as an optimization problem that minimizes the maximum coverage over all bases, studying the computational complexities for some cases and designing polynomial-time or approximate polynomial-time algorithms for them and some others.

We focus on a new problem that is formulated to find a longest k-tuple of common sub-strings (abbr. k-CSSs) of two or more strings. We present a suffix tree based algorithm for this problem, which can find a longest k-CSS of m strings in $O(kmn^{k})$ time and $O(kmn)$ space where n is the length sum of the m strings. This algorithm can be used to approximate the longest k-CSS problem to a performance ratio $\frac{1}{\epsilon}$ in $O(kmn^{\lceil\epsilon k\rceil})$ time for $\epsilon\in(0,1]$. Since the algorithm has the space complexity in linear order of n, it will show advantage in comparing particularly long strings. This algorithm proves that the problem that asks to find a longest gapped pattern of non-constant number of strings is polynomial time solvable if the gap number is restricted constant, although the problem without any restriction on the gap number was proved NP-Hard. Using a C++ tool that is reliant on the algorithm, we performed experiments of finding longest 2-CSSs, 3-CSSs and 5-CSSs of 2 ~ 14 COVID-19 S-proteins. Under the help of longest 2-CSSs and 3-CSSs of COVID-19 S-proteins, we identified the mutation sites in the S-proteins of two COVID-19 variants Delta and Omicron. The algorithm based tool is available for downloading at https://github.com/lytt0/k-CSS.

Metagenome takes the genome of microbial communities in a specific environment as the research object. It is of great significance in analyzing microbial diversity and exploring the relationship of microbial communities. This paper mainly discusses metagenomic identification, especially the identification of viruses in metagenomes. The identifications of viruses and other sequences are the first step in microbial analysis, and their validity may have implications for downstream work. We develop DLmeta, a deep learning method for accomplishing metagenomic identification. DLmeta obtains domains through gene prediction and protein domain prediction, and uses a model that combines Convolutional Neural Network (CNN) and Transformer to complete the metagenomic identification. We benchmarked DLmeta on data of three species that were viruses, bacteria, and plasmids. The results showed that DLmeta was able to accurately identify species sequences from the metagenomes simultaneously, outperforming other state-of-the-art methods. In the ablation experiment, we demonstrated that our model uses CNN to capture local features and Transformer to capture global features, which can greatly improve the performance of metagenomic identification. DLmeta also can be applied to other metagenomic environments. DLmeta is available at https://github.con xiaozhangzhangl23/DLmeta.

Recent advances in RNA-seq technology have made identification of expressed genes affordable, and thus boosting repaid development of transcriptomic studies. Transcriptome assembly, reconstructing all expressed transcripts from RNA-seq reads, is an essential step to understand genes, proteins, and cell functions. Transcriptome assembly remains a challenging problem due to complications in splicing variants, expression levels, uneven coverage and sequencing errors. Here, we formulate the transcriptome assembly problem as path extraction on splicing graphs (or assembly graphs), and propose a novel algorithm MultiTrans for path extraction using mixed integer linear programming. MultiTrans is able to take into consideration coverage constraints on vertices and edges, the number of paths and the paired-end information simultaneously. We benchmarked MultiTrans against two state-of-the-art transcriptome assemblers, TransLiG and rnaSPAdes. Experimental results show that MultiTrans generates more accurate transcripts compared to TransLiG (using the same splicing graphs) and rnaSPAdes (using the same assembly graphs). MultiTrans is freely available at https://github.com/jzbio/MultiTrans.

High-throughput sequencing of mRNA (RNA-seq) provides a promise for transcriptome reconstruction by producing hundreds of millions of short reads. Current salient methods for genome-based transcriptome reconstruction almost unanimously sank into details instead of considering it in a whole picture. We present TransCoord, which inclusively gathers all kinds of candidate transcripts into a two-phased linear programming model that aims both to minimize coverage deviation and reserve least transcripts under conserving the must. In this way, the outcome is a coordination of all candidates, instead of a union of all independently assembled parts. Test on 19 human and 5 Arabidopsis thaliana real RNA-seq datasets, TransCoord outperformed all 4 compared salient assemblers in sensitivity. TransCoord is available at https://github.com/lcc121/TransCoord

High-throughput sequencing of mRNA has made the deep and efficient probing of transcriptome more affordable. However, the vast amounts of short RNA-seq reads make de novo transcriptome assembly an algorithmic challenge. In this work, we present IsoTree, a novel framework for transcripts reconstruction in the absence of reference genomes. Unlike most of de novo assembly methods that build de Bruijn graph or splicing graph by connecting k- mers which are sets of overlapping substrings generated from reads, IsoTree constructs splicing graph by connecting reads directly. For each splicing graph, IsoTree applies an iterative scheme of mixed integer linear program to build a prefix tree, called isoform tree. Each path from the root node of the isoform tree to a leaf node represents a plausible transcript candidate which will be pruned based on the information of paired-end reads. Experiments showed that in most cases IsoTree performs better than other leading transcriptome assembly programs. IsoTree is available at https://github.com/Jane110111107/IsoTree.

Presents corrections to author information in the above named paper.

BACKGROUND: Alternative splicing allows the pre-mRNAs of a gene to be spliced into various mRNAs, which greatly increases the diversity of proteins. High-throughput sequencing of mRNAs has revolutionized our ability for transcripts reconstruction. However, the massive size of short reads makes de novo transcripts assembly an algorithmic challenge. RESULTS: We develop a novel radical framework, called DTA-SiST, for de novo transcriptome assembly based on suffix trees. DTA-SiST first extends contigs by reads that have the longest overlaps with the contigs' terminuses. These reads can be found in linear time of the lengths of the reads through a well-designed suffix tree structure. Then, DTA-SiST constructs splicing graphs based on contigs for each gene locus. Finally, DTA-SiST proposes two strategies to extract transcript-representing paths: a depth-first enumeration strategy and a hybrid strategy based on length and coverage. We implemented the above two strategies and compared them with the state-of-the-art de novo assemblers on both simulated and real datasets. Experimental results showed that the depth-first enumeration strategy performs always better with recall and also better with precision for smaller datasets while the hybrid strategy leads with precision for big datasets. CONCLUSIONS: DTA-SiST performs more competitive than the other compared de novo assemblers especially with precision measure, due to the read-based contig extension strategy and the elegant transcripts extraction rules.

A short swap switches two elements with at most one element caught between them. Sorting permutation by short swaps asks to find a shortest short swap sequence to transform a permutation into another. A short swap can eliminate at most three inversions. It is still open for whether a permutation can be sorted by short swaps each of which can eliminate three inversions. In this paper, we present a polynomial time algorithm to solve the problem, which can decide whether a permutation can be sorted by short swaps each of which can eliminate 3 inversions in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time, where n is the number of elements in the permutation. A short swap can cause the total length of two element vectors to decrease by at most 4. We further propose an algorithm to recognize a permutation which can be sorted by short swaps each of which can cause the element vector length sum to decrease by 4 in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time. This improves upon the O(n^2) algorithm proposed by Heath and Vergara to decide whether a permutation is so called lucky.

Gene controls biological character by various proteins that are formed by isoforms. Through alternative splicing, gene can express multiple isoforms. The next generation of high-throughput RNA sequencing has provided facilitation for quantifying isoform expression level. Extensive efforts have been made in stimulating isoform abundance from RNA-Seq data, but the accuracy still needs to be improved. In this article, we propose a statistical method combined with Particle Swarm Optimization to estimate isoform abundance from RNA-Seq data. After a series of statistical analysis and experiments, we decided on the forms and values of coefficients in Particle Swarm Optimization model. We analyzed the performance of our approach on both simulated and real datasets. Experiment results showed that comparing to Cufflinks our approach makes acceptable improvement on accuracy and is more sensitive to condition changes in most cases.

We are interested in the problem of word extraction from Chinese text collections. We define a word to be a meaningful string composed of several Chinese characters. For example, ‘percent’, and, ‘more and more’, are not recognized as traditional Chinese words from the viewpoint of some people. However, in our work, they are words because they are very widely used and have specific meanings. We start with the viewpoint that a word is a distinguished linguistic entity that can be used in many different language environments. We consider the characters that are directly before a string (predecessors) and the characters that are directly after a string (successors) as important factors for determining the independence of the string. We call such characters accessors of the string, consider the number of distinct predecessors and successors of a string in a large corpus (TREC 5 and TREC 6 documents), and use them as the measurement of the context independency of a string from the rest of the sentences in the document. Our experiments confirm our hypothesis and show that this simple rule gives quite good results for Chinese word extraction and is comparable to, and for long words outperforms, other iterative methods.

The internet can be viewed as a database with a huge amount of information. Powerful search engines present to users web pages that contain useful information, ranked according to the relevance to a particular query, and the quality of the web pages. However, users may have different interests even for the same query. In this work, we develop an on-line approach to learn to rank the web pages according to user preference.