Transposition is a well-known genome rearrangement event that switches two consecutive sub-strings on a string. Since a transposition makes changes to a string, the genome here is just a string. The problem of transforming one string into the other by a sequence of transposition operations has attracted a lot of attention. However, it has been reported that genome rearrangement events are often associated with repeated sub-strings. In particular, a transposition operation is most likely associated with three identical repeated sub-strings. A transposition operation on two consecutive sub-strings $x$ and $y$ switches the two sub-strings and transforms the whole string $zxyw$ into the other string $zyxw$, where $z$ and $w$ represents the two sub-strings on the left and right of $xy$, respectively. When repeated sub-strings are considered, the two consecutive sub-strings $x$ and $y$ are flanked with three identical repeated sub-strings $R$ and the flanked transposition transforms the whole string $zRxRyRw$ into $zRyRxRw$. For a flanked transposition operation, the neighbors of $x$ and $y$ remain the same before and after the transposition. In this paper, we investigate the problem of transforming one string into the other by a number of flanked transpositions. First, we present a necessary and sufficient condition to determine if a string can be transformed into the other by a sequence of flanked transpositions. We then design a decision algorithm with running time $\mathcal {O}(n)$ to test if such a condition holds. We also show that transforming one string into the other by using minimum number of flanked transpositions is NP-hard. A string $\pi$ of $n$ letters is simple if the $n-1$ consecutive pairs of letters are distinct. We present an $\mathcal {O}(n^{2})$ approximation algorithm with ratio 2 for the optimization version of the special case, where both input strings are simple.

Repetitive sequences are prevalent across all domains of life and play intricate roles in genetic regulation, stability, and evolution. To better understand the functions of these repetitive sequences, various methods have been developed for assembling short tandem repeats such as microsatellites, minisatellites, and satellites. However, existing assembly methods overlook a special case of ultra-long tandem repeat, where the length of a single repeat unit exceeds tens of thousands of base pairs. It is challenging for existing assembly methods to accurately reconstruct these repeatsHere we present ULTR-asm, an assembler specifically designed to tackle ultra-long tandem repeats. ULTR-asm builds on the overlap-layout-consensus (OLC) paradigm, with an additional polishing optimization step. Evaluations on simulated data demonstrated that ULTR-asm outperforms state-of-the-art assemblers, enhancing genome integrity and accuracy, and contributing to the assembly of more complete genomes.

The collision cross section (CCS) is a crucial parameter that reflects a molecule’s size and shape, offering valuable insights into its structural conformation. Accurate CCS predictions can significantly enhance the identification and separation of compounds in mass spectrometry, proving particularly useful in fields such as proteomics and drug discovery. The CCS of a peptide is a reproducible physicochemical property influenced by its mass, charge, and gas-phase structure. Despite its importance, predicting CCS using both sequence data and physical attributes remains challenging. To address this, we introduce PEP2CCS, a deep learning model designed to predict CCS. This model integrates enhanced physical features of peptides, thereby improving the accuracy of CCS predictions. The analysis revealed that PEP2CCS had a Median Absolute Percent Error of 1.139% in predicting the synthetic proteomic peptide cross-section, which is 18.6% lower than state-of-the-art method. Furthermore, the results suggest that the integration of the charge state into the model is a significant contributor to the accurate prediction of CCS values. Code and pre-trained model are released at https://github.com/xfcui/PEP2CCS.

At present, as a research hotspot for time series data (TSD), the deep clustering analysis of TSD has huge research value and practical significance. However, there still exist the following three problems: (1) For deep clustering based on joint optimization, the inevitably mutual interference existing between deep feature representation learning progress and clustering progress leads to difficult model training especially in the initial stage, the possible feature space distortion, inaccurate and weak feature representation; (2) Existing deep clustering methods are difficult to intuitively define the similarity of time series and rely heavily on complex feature extraction networks and clustering algorithms. (3) Multidimensional time series have the characteristics of high dimensions, complex relationships between dimensions, and variable data forms, thus generating a huge feature space. It is difficult for existing methods to select discriminative features, resulting in generally low accuracy of methods. Accordingly, to address the above three problems, we proposed a novel general two-stage multi-dimensional spatial features based multi-view deep clustering method 1DCAE-TSSAMC (One-dimensional deep convolutional auto-encoder based two-stage stepwise amplification multi-clustering). We conducted verification and analysis based on real-world important multi-scenario, and compared with many other benchmarks ranging from the most classic approaches such as K-means and Hierarchical to the state-of-the-art approaches based on deep learning such as Deep Temporal Clustering (DTC) and Temporal Clustering Network (TCN). Experimental results show that the new method outperforms the other benchmarks, and provides more accurate, richer, and more reliable analysis results, more importantly, with significant improvement in accuracy and spatial linear separability.

Rearrangement sorting problems impact profoundly in measuring genome similarities and tracing historic scenarios of species. However, recent studies on genome rearrangement mechanisms disclosed a statistically significant evidence, repeats are situated at the ends of rearrangement relevant segments and stay unchanged before and after rearrangements.To reflect the principle behind this evidence, we propose flanked block-interchange, an operation on strings that exchanges two substrings flanked by identical left and right symbols in a string. The flanked block-interchange distance problem is formulated as finding a shortest sequence of flanked block-interchanges to transform a string into the other. We propose a sufficient and necessary condition for deciding whether two strings can be transformed into each other by flanked block-interchanges. This condition is linear time verifiable. Under this condition for two strings, we present a [Formula: see text]-approximation algorithm for the flanked block-interchange distance problem where each symbol occurs at most k times in a string and a polynomial algorithm for this problem where each symbol occurs at most twice in a string. We show that the problem of flanked block-interchange distance is NP-hard at last.

Mass spectrometry is a key technology for the identification of small molecules. However, traditional methods that rely on database comparisons have difficulty with newly discovered molecules that are not in the database. Recent advances in deep learning allow for direct analysis of mass spectra, which makes it possible to predict chemical structures without using a database. We have found that the accurate prediction of hydrogen atoms is a major challenge for the prediction of chemical structures, especially since they are not explicitly represented in SMILES. To address this challenge, we introduce MS2SMILES, a novel approach that treats hydrogen atoms as implicitly linked to heavy atoms. This method enables the model to predict both heavy atoms and hydrogen atoms accurately (instead of just focusing on heavy atoms) during the training phase. Additionally, MS2SMILES incorporates the SMILES grammatical rules when predicting chemical structures, increasing the reliability of the generated SMILES representations. We tested MS2SMILES using the GNPS and CASMI 2016 datasets, and it achieved SMILES prediction accuracies of 53.6% and 63.8%, respectively. These results demonstrate a significant improvement of 19.9% and 10.9% compared to the current leading method.

Comparing genomes in terms of gene order is a classical combinatorial optimization problem in computational biology, which asks for a least number of genome rearrangement operations to transform one genome into the other. The problems of sorting genomes by reversals have been extensively studied over the past decades. Computing the reversal distance are NP-hard when the input genomes are unsigned. A general method to devise an approximation algorithm involves computing a proper alternating cycle decomposition of its breakpoint graph, which becomes the bottleneck for computing the corresponding rearrangement distances and prohibits to obtain approximation factors better than 1.375 in polynomial time. In this paper, we devise FPT approximation algorithms for the problems of sorting genomes by reversals, the approximation factor are improved to 4/3 + ε. The algorithm exploits a new randomized algorithm to decompose the breakpoint graph, which succeeds with a high probability $1 - \frac{1}{{{e^{O(n)}}}}$ according to Chernoff Bound. The time complexity of the algorithm is $O\left( {{2^{{d^{\ast}}}} \cdot {n^{O\left( {\frac{1}{\varepsilon }} \right)}}} \right)$, where n is the length of each genome and d* represents the optimal reversal distance.

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.

Although conserved gene subsequences play a basically necessary part in researches such as biomedicine and bio-breeding, there is short of a practical tool to predict conserved gene subsequences in genomes. We propose a problem that is formalized to find a repetition-free longest common subsequence of given genomes with subsequences identical to indexed gene subsequences. We present an algorithm for this problem that is driven to run faster sufficiently by maintaining those gene families in confusion of their maintainability. The algorithm can be driven to run furthermore faster due to more indexed genes selected. The algorithm based software was examined to quest 23 human/gorilla chromosome summary pairs for solutions whose basic units are annotated as well as pseudo genes, namely consecutive DNA subsequences. The experimental result showed that our algorithm performed better than previous algorithms CMSA and Hyb-CMSA in both time complexity and result length.

General-purpose protein structure embedding can be used for many important protein biology tasks, such as protein design, drug design and binding affinity prediction. Recent researches have shown that attention-based encoder layers are more suitable to learn high-level features. Based on this key observation, we propose a two-level general-purpose protein structure embedding neural network, called ContactLib-ATT. On local embedding level, a biologically more meaningful contact context is introduced. On global embedding level, attention-based encoder layers are employed for better global representation learning. Our general-purpose protein structure embedding framework is trained and tested on the SCOP40 2.07 dataset. As a result, ContactLib-ATT achieves a SCOP superfamily classification accuracy of 82.4% (i.e., 6.7% higher than state-of-the-art method). On the same dataset, ContactLib-ATT is used to simulate a structure-based search engine for remote homologous proteins, and our top-10 candidate list contains at least one remote homolog with a probability of 91.9%.

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.

DNA sites can realize various biological functions and play an important role in many biological activities. However, due to the complexity of feature extraction, feature learning is difficult. It is not conducive to realize high-precision identification and prediction of some DNA sites. In order to achieve efficient learning of DNA site features, we propose a DNA site prediction algorithm WFMP based on weighted feature matrix and polymerization strategy. The prediction algorithm learns the correlation between features and results, and assigns different weight information to each feature, emphasizing attention to important features and reducing the interference of invalid features. At the same time, WFMP effectively avoids the defects of a single algorithm by aggregating four traditional algorithms. Here, we apply the algorithm to classification and regression tasks respectively, which show high universality. The experimental results show that WFMP obtained an accuracy of 0. S966 in the classification task, achieving higher prediction accuracy. In the regression task, it obtained a root mean square error of 0.0051, showing an ultra-low error rate. In general, the WFMP algorithm is superior to the existing algorithms in all evaluation indicators, and has better portability and higher prediction accuracy. Based on the above studies, WFMP can not only detect hidden DNA binding sites, but also provide ideas for the study of efficient recombination systems.

As a pivotal element in transcriptional regulation, the transcription factor is required to regulate and control gene expression. It is difficult for the predicting problem of transcription factor binding sites (TFBSs), and it is an important task in biology. In our study, we propose a new algorithm WMS_TF of weighted multi-granularity scanning strategy based on the deep forest method, we assign unique weight vectors to scan windows in multi-granularity scanning, and the algorithm pays more attention to the important features. In addition to single DNA base features, the paper also presents the method of multi-base feature encoding in feature representation. The algorithm WMS_TF uses DNA sequences for training, directly implements sequence-to-function prediction, and reduces the impact of noisy data for results. Experiments show that the algorithm WMS_TF can effectively predict TFBSs according to DNA sequences. Especially in the small data set, the corresponding index scores of the results are higher than similar algorithms, such as algorithm Adaboost, Deep Forest, and KNN. The accuracy of algorithm WMS_TF reaches 89.43%, the F1-Measure attains 89.20%, and the AUC achieves 92.19%. New ideas are provided by weighted multi-grained scanning and combined feature representations for predicting TFBSs.

The knowledge concerning antigen presentation by the main histocompatibility complex (MHC) to T-cell receptor (TCR) and TCR binding specificity can facilitate the application of T-cell immunity in modern medicine, such as tumor immunotherapy and drug and vaccine design cases. With the development of high-throughput sequencing technology and artificial intelligence, data-driven approaches can be employed to help understand the rules of TCR-pMHC binding. Simulating the biological binding process of TCRs and pMHCs, we propose a novel pipeline, pMTattn, using transfer learning based on an attention mechanism for TCR-pMHC binding prediction. During the pretraining stage, partner-specific training strategies can capture useful local binding features. In the fine-tuning stage, an attention block is employed to aggregate the TCR encoding and pMHC encoding information, forming a better global TCR-pMHC representation. Visualization experiments indicate that the pMTattn model focuses more on the voxels near the binding sites of pMHCs and TCRs. This key observation effectively supports our hypothesis that attention is critical for TCR-pMHC binding prediction. In addition, on an independent test set, the area under the precision-recall curve (AUPR) and the area under the receiver operating characteristic curve (AUC) are improved from 0.533 to 0.583 and from 0.830 to 0.866, respectively, by pMTattn compared to those of the state-of-the-art model. Simultaneously, we also explore the influences of different sequence lengths and dataset differences on the model effect, and pMTattn exhibits better robustness than other models. These results suggest that pMTattn has the ability to be used as an adjunct tool for screening and discovering neoantigens.

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.

MOTIVATION: Drawing peaks in a data window of an MS dataset happens at all time in MS data visualization applications. This asks to retrieve from an MS dataset some selected peaks in a data window whose image in a display window reflects the visual feature of all peaks in the data window. If an algorithm for this purpose is asked to output high-quality solutions in real time, then the most fundamental dependence of it is on the storage format of the MS dataset. RESULTS: We present mzMD, a new storage format of MS datasets and an algorithm to query this format of a storage system for a summary (a set of selected representative peaks) of a given data window. We propose a criterion Q-score to examine the quality of data window summaries. Experimental statistics on real MS datasets verified the high speed of mzMD in retrieving high-quality data window summaries. mzMD reported summaries of data windows whose Q-score outperforms those mzTree reported. The query speed of mzMD is the same as that of mzTree whereas its query speed stability is better than that of mzTree. AVAILABILITY AND IMPLEMENTATION: The source code is freely available at https://github.com/yrm9837/mzMD-java. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Scaffold filling is a critical step in DNA assembly. Its basic task is to fill the missing genes (fragments) into an incomplete genome (scaffold) to make it similar to the reference genome. There have been a lot of work under distinct measurements in the literature of genome comparison. For genomes with gene duplications, common string partition reveals the similarity more precisely, since it constructs a one-to-one correspondence between the same segments in the two genomes. In this paper, we adopt duo-preservation as the measurement, which is the complement of common string partition, i.e., the number of duo-preservations added to the number of common strings is exactly the length of a genome. Towards a proper scaffold filling, we just focus on the increased duo-preservations. This problem is called scaffold filling to maximize increased duo-preservations (abbr. SF-MIDP). We show that SF-MIDP is solvable in linear time for a simple version where all the genes of the scaffold are matched in a block-matching, but MAX SNP-complete for the general version, and cannot be approximated within [Formula: see text]. Moreover, we present a basic approximation algorithm of factor 2, by which the optimal solution can be described in a new way, and then, improve the approximation factor to [Formula: see text] via a greedy method.

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.

General-purpose protein structure embedding can be used for many important protein biology tasks, such as protein design, drug design and binding affinity prediction. Recent researches have shown that attention-based encoder layers are more suitable to learn high-level features. Based on this key observation, we treat low-level representation learning and high-level representation learning separately, and propose a two-level general-purpose protein structure embedding neural network, called ContactLib-ATT. On the local embedding level, a simple yet meaningful hydrogen-bond representation is learned. On the global embedding level, attention-based encoder layers are employed for global representation learning. In our experiments, ContactLib-ATT achieves a SCOP superfamily classification accuracy of 82.4% (i.e., 6.7% higher than state-of-the-art method) on the SCOP 40 2.07 dataset. Moreover, ContactLib-ATT is demonstrated to successfully simulate a structure-based search engine for remote homologous proteins, and our top-10 candidate list contains at least one remote homolog with a probability of 91.9%.

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

Computational algorithms are being successfully used to speed up drug development processes, primarily by way of turning biochemical problems into data problems. Recently, with increasing amounts of available biological data generated by biochemical methods measured affinity, some computational algorithms based deep learning for predicting drug-target affinity (DTA) become promising directions for accelerating the process of drug development. These deep learning models first attempts focus on representation learning of individual amino acids or atoms. Next global average pooling layers in those models are used to to combine such individual features to global features, and finally simple feed forward networks are adopted to yield affinity predictions. Notably, research which has been undertaken on global feature aggregations (e.g., the global pooling and the feed forward layers) for the drug-target affinity problem is still lacked currently. To address this issue, we propose a new rzMLP block featured newly designed global feature aggregations. This rzMLP block is based on two recent technologies in deep learning research: the gMLP model and the ReZero layer. We use gMLP model to aggregate input features with a constant size, while the ReZero layer is used to smooth the training process of this block. Our rzMLP is capable of learning complicated global features while overcoming the problems caused by the model being too deep. Importantly, when we compared a model contained rzMLP block to others, the mean squared error(MSE) decreases by 33%. Comparing to state-of-the-art methods for predicting affinity, rzMLP-DTA achieves the lowest MSE and highest CI on two benchmarks, Davis and KIBA datasets, respectively.

Although plenty of structural variant detecting approaches for human genomes can be looked up in the literatures, little has been acknowledged on the effectiveness of those structural variant softwares for plant genomes. Moreover, it has been demonstrated frequent occurrences for those structural variant detecting softwares to find too many false structural variants. In this paper, we devote to detect deletions, insertions, and inversions, in total of three kinds of structural variants occurring in Hedou12 genome in contrast to Williams82 genome. To find more potential structural variants, we try to develop new principles to detect discordant and split read map sets supporting structural variants. Aiming to enhance the precision of structural variant detections, we propose two new sequencing characteristic based probability models, which use the sequencing parameters of Hedou12 genome as well as the parameters for Hedou12 paired-end reads to be aligned onto Williams82, to evaluate the probability for a potential structural variant to occur in. To remove the false members from those potential structural variants, we propose a set cover problem model to describe formally on which potential structural variants it should accept to achieve as high as possible a probability summation. This will achieve a solution with more credible structural variants, which can be verified by comparing with DELLY version 0.5.8 and LUMPY version 0.2.2.3. Our algorithm has been verified to be able to find deletions, insertions, and inversions in Hedou12 in contrast to Williams82 DELLY as well as LUMPY fails to find.

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.

The Maximal Strip Recovery problem (MSR) and its complementary (CMSR) are well-studied NP-hard problems in computational genomics. The input of these dual problems are two signed permutations. The goal is to delete some gene markers from both permutations, such that, in the remaining permutations, each gene marker has at least one common neighbor. Equivalently, the resulting permutations could be partitioned into common strips of length at least two. Then MSR is to maximize the number of remaining genes, while the objective of CMSR is to delete the minimum number of gene markers. In this paper, we present a new approximation algorithm for the Complementary Maximal Strip Recovery (CMSR) problem. Our approximation factor is 2, improving the currently best 7/3-approximation algorithm. Although the improvement on the factor is not huge, the analysis is greatly simplified by a compensating method, commonly referred to as the non-oblivious local search technique. In such a method a substitution may not always increase the value of the current solution (it sometimes may even decrease the solution value), though it always improves the value of another function seemingly unrelated to the objective function.

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.

Copy number variation (CNV) is a prevalent kind of genetic structural variation which leads to an abnormal number of copies of large genomic regions, such as gain or loss of DNA segments larger than 1[Formula: see text]kb. CNV exists not only in human genome but also in plant genome. Current researches have testified that CNV is associated with many complex diseases. In this paper, guanine-cytosine (GC) bias, mappability and their effect on read depth signals in sequencing data are discussed first. Subsequently, a new correction method for GC bias and an improved combinatorial detection algorithm for CNV using high-throughput sequencing reads based on hidden Markov model (CNV-HMM) are proposed. The corrected read depth signals have lower correlation with GC content, mappability of reads and the width of analysis window. Then we create a hidden Markov model which maps the reads onto the reference genome and records the unmapped reads. The unmapped reads are counted and normalized. The CNV-HMM detects the abnormal signal of read count and gains the candidate CNVs using the expectation maximization (EM) algorithm. Finally, we filter the candidate CNVs using split reads to promote the performance of our algorithm. The experiment result indicates that the CNV-HMM algorithm has higher accuracy and sensitivity for CNVs detection than most current detection algorithms.

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.

The prediction of RNA structure with pseudoknots is a nondeterministic polynomial-time hard (NP-hard) problem; according to minimum free energy models and computational methods, we investigate the RNA-pseudoknotted structure. Our paper presents an efficient algorithm for predicting RNA structure with pseudoknots, and the algorithm takes O([Formula: see text]) time and O([Formula: see text]) space, the experimental tests in Rfam10.1 and PseudoBase indicate that the algorithm is more effective and precise. The predicting accuracy, the time complexity and space complexity outperform existing algorithms, such as Maximum Weight Matching (MWM) algorithm, PKNOTS algorithm and Inner Limiting Layer (ILM) algorithm, and the algorithm can predict arbitrary pseudoknots. And there exists a [Formula: see text] ([Formula: see text]) polynomial time approximation scheme in searching maximum number of stackings, and we give the proof of the approximation scheme in RNA-pseudoknotted structure. We have improved several types of pseudoknots considered in RNA folding structure, and analyze their possible transitions between types of pseudoknots.

Database search is the main approach for identifying proteoforms using top-down tandem mass spectra. However, it is extremely slow to align a query spectrum against all protein sequences in a large database when the target proteoform that produced the spectrum contains post-translational modifications and/or mutations. As a result, efficient and sensitive protein sequence filtering algorithms are essential for speeding up database search. In this paper, we propose a novel filtering algorithm, which generates spectrum graphs from subspectra of the query spectrum and searches them against the protein database to find good candidates. Compared with the sequence tag and gaped tag approaches, the proposed method circumvents the step of tag extraction, thus simplifying data processing. Experimental results on real data showed that the proposed method achieved both high speed and high sensitivity in protein sequence filtration.

In this paper, we devote to detect those deletions, insertions and inversions, in total of three kinds of structural variations in Heidou12 genome relative to Williams82 genome. We propose two sequencing characteristic based probability models, which use the paired-end reads of Hedou12 and their mapping distribution on Williams82 to evaluate on with what probability a potential structural variant can happen. To reduce the conflicts of those potential structural variants, we propose a set cover problem model to formalize on finding structural variants covering all those reads causing potential structural variants with as high as possible probabilities, and use a primal-dual based algorithm to solve it. The efficiency and feasibility of our algorithm are verified by comparing with DELLY(version0.5.5) and LUMPY (27.12.2014).

The genomic scaffold filling problem has attracted a lot of attention recently. The problem is on filling an incomplete sequence (scaffold) I into I', with respect to a complete reference genome G, such that the number of adjacencies between G and I' is maximized. The problem is NP-complete and APX-hard, and admits a 1.2-approximation. However, the sequence input I is not quite practical and does not fit most of the real datasets (where a scaffold is more often given as a list of contigs). In this paper, we revisit the genomic scaffold filling problem by considering this important case when, (1) a scaffold S is given, the missing genes X = c(G) - c(S) can only be inserted in between the contigs, and the objective is to maximize the number of adjacencies between G and the filled S' and (2) a scaffold S is given, a subset of the missing genes X' subset X = c(G) - c(S) can only be inserted in between the contigs, and the objective is still to maximize the number of adjacencies between G and the filled S''. For problem (1), we present a simple NP-completeness proof, we then present a factor-2 greedy approximation algorithm, and finally we show that the problem is FPT when each gene appears at most d times in G. For problem (2), we prove that the problem is W[1]-hard and then we present a factor-2 FPT-approximation for the case when each gene appears at most d times in G.

We consider the emerging problem of comparing the similarity between (unlabeled) pedigrees. More specifically, we focus on the simplest pedigrees, namely, the 2-generation pedigrees. We show that the isomorphism testing for two 2-generation pedigrees is GI-hard. If the 2-generation pedigrees are monogamous (i.e., each individual at level-1 can mate with exactly one partner) then the isomorphism testing problem can be solved in polynomial time. We then consider the problem by relaxing it into an NP-complete decomposition problem which can be formulated as the Minimum Common Integer Pair Partition (MCIPP) problem, which we show to be FPT by exploiting a property of the optimal solution. While there is still some difficulty to overcome, this lays down a solid foundation for this research.

The exemplar breakpoint distance problem is motivated by finding conserved sets of genes between two genomes. It asks to find respective exemplars in two genomes to minimize the breakpoint distance between them. If one genome has no repeated gene (called trivial genome) and the other has genes repeating at most twice, it is referred to as the (1,2)-exemplar breakpoint distance problem, EBD(1, 2) for short. Whether there exists a fixed parameter algorithm for this problem has been open for many years. In this paper, we propose the first fixed parameter algorithm for EBD(1,2). Using a dynamic programming approach, we design an algorithm to solve EBD(1,2) with running time O(4sn2) and space O(4sn), respectively, where n is the number of gene families, and s is the maximum number of genes (minus 1) located between two copies of a gene family in the second genome. Our algorithm can also be used to compute the maximum adjacencies between two genomes. Simulations on real data have verified the effectiveness of our algorithm. The algorithm has been implemented in C++. The software package is available upon request.

Scaffold filling is a new combinatorial optimization problem in genome sequencing. The one-sided scaffold filling problem can be described as given an incomplete genome I and a complete (reference) genome G, fill the missing genes into I such that the number of common (string) adjacencies between the resulting genome I' and G is maximized. This problem is NP-complete for genome with duplicated genes and the best known approximation factor is 1.33, which uses a greedy strategy. In this paper, we prove a better lower bound of the optimal solution, and devise a new algorithm by exploiting the maximum matching method and a local improvement technique, which improves the approximation factor to 1.25. For genome with gene repetitions, this is the only known NP-complete problem which admits an approximation with a small constant factor (less than 1.5).

The exemplar breakpoint distance problem is one of the most important problems in genome comparison and has been extensively studied in the literature. The exemplar breakpoint distance problem cannot be approximated within any factor even if each gene family occurs at most twice in a genome. This is due to the fact that its decision version, the zero exemplar breakpoint distance problem where each gene family occurs at most twice in a genome (ZEBD(2,2) for short) is NP-hard. Thus, the basic version ZEBD(2,2) has attracted the attention of many scientists. The best existing algorithm for ZEBD(2,2) runs in O(n2(n)) time. In this paper, we propose a new algorithm for ZEBD(2,2) with running time O(n(2)1.86121(n)). We have implemented the algorithm in Java. The software package is available upon request.

BACKGROUND: The ability to predict protein-protein binding sites has a wide range of applications, including signal transduction studies, de novo drug design, structure identification and comparison of functional sites. The interface in a complex involves two structurally matched protein subunits, and the binding sites can be predicted by identifying structural matches at protein surfaces. RESULTS: We propose a method which enumerates "all" the configurations (or poses) between two proteins (3D coordinates of the two subunits in a complex) and evaluates each configuration by the interaction between its components using the Atomic Contact Energy function. The enumeration is achieved efficiently by exploring a set of rigid transformations. Our approach incorporates a surface identification technique and a method for avoiding clashes of two subunits when computing rigid transformations. When the optimal transformations according to the Atomic Contact Energy function are identified, the corresponding binding sites are given as predictions. Our results show that this approach consistently performs better than other methods in binding site identification. CONCLUSIONS: Our method achieved a success rate higher than other methods, with the prediction quality improved in terms of both accuracy and coverage. Moreover, our method is being able to predict the configurations of two binding proteins, where most of other methods predict only the binding sites. The software package is available at http://sites.google.com/site/guofeics/dobi for non-commercial use.

MOTIVATION: The double cut and join operation (abbreviated as DCJ) has been extensively used for genomic rearrangement. Although the DCJ distance between signed genomes with both linear and circular (uni- and multi-) chromosomes is well studied, the only known result for the NP-complete unsigned DCJ distance problem is an approximation algorithm for unsigned linear unichromosomal genomes. In this article, we study the problem of computing the DCJ distance on two unsigned linear multichromosomal genomes (abbreviated as UDCJ). RESULTS: We devise a 1.5-approximation algorithm for UDCJ by exploiting the distance formula for signed genomes. In addition, we show that UDCJ admits a weak kernel of size 2k and hence an FPT algorithm running in O(2(2k)n) time.

Genome rearrangement is an important area in computational biology and bioinformatics. The translocation operation is one of the popular operations for genome rearrangement. It was proved that computing the unsigned translocation distance is NP-hard. In this paper, we present a (1.5 + epsilon)-approximation algorithm for computing unsigned translocation distance which improves upon the best known 1.75-ratio. The running time of our algorithm is O(n2 + (4/epsilon)1.5 square root log(4/epsilon )2(4/epsilon), where n is the total number of genes in the genome.

In this article, we present a new data structure, called the permutation tree, to improve the running time of sorting permutation by transpositions and sorting permutation by block interchanges. The existing 1.5-approximation algorithm for sorting permutation by transpositions has time complexity O ( n 3/2 √ logn ). By means of the permutation tree, we can improve this algorithm to achieve time complexity O ( nlogn ). We can also improve the algorithm for sorting permutation by block interchanges to take its time complexity from O ( n 2 ) down to O ( nlogn ).

We have devised a new DNA encoding method to represent numerical values and apply it to solve the Chinese postman problem, an instance of optimization problems on weighted graphs. For any a weighted, undirected graph G=(V, E), vi∈ V, 1≤ i≤ n, ej∈ E, 1≤ j≤ m, where exists a numerical value (weight) wjon edge ej, we convert it into its half-dual graph G′=(V′, E′), vi′∈ V′, 1≤ i≤ m, where vi′ is mapped from ei. Our DNA encoding method is based on the half-dual graph G′=(V′, E′). For any a vertex vi′, we use DNA strand siof length wito encode it. For any an edge vi′ vj′, we use reverse complementation of the second half of siand the first half of sjto encode it. Our work makes weight be easily dealt with and extends the capability of DNA computing to solve NP-hard problems.

Abstract Summary: CTRD is a software for computing translocation distance between genomes. It takes two genomes as its input and tests whether one genome can be transformed into the other. If possible, it computes the translocation distance between two genomes, and gives the translocation operation serial. We adopt the fastest known O(n2log n) algorithm. Our contributions include (1) give a necessary and sufficient condition to ensure that one genome can be transformed into the other for translocation operations, and (2) develop a software using the fastest known O(n2log n) algorithm. Availability: Free from http://www.cs.cityu.edu.hk/~lwang/software/Translocation/ subject to copyright restrictions.