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.

The turnover number (kcat) is a crucial measure for evaluating enzyme catalytic efficiency, significantly influencing studies of cellular metabolism and resource allocation. Due to the high costs associated with determining kcat, predictive machine learning models such as TurNuP have been developed to predict the turnover numbers of kinetically uncharacterized enzymes. Existing methods rely on binary Differential Reaction Fingerprints (DRFPs) to represent reactions. However, these binary reaction fingerprints have two main limitations. First, they only show changes between substrates and products, without specifying whether the change occurs in the substrates or products. Second, they omit information about similarities between substrates and products, missing crucial reaction details. To overcome these issues, we developed Quaternary Reaction Fingerprints (QRFPs) by incorporating quaternary structural features. Thus, QRFPs extend DRFPs, and DRFPs can be derived from QRFPs. We proposed a deep learning method based on QRFPs and pretrained protein language model ESM2, called TurNuP4. Experimental results show that TurNuP4outperforms TurNuP by 18% in R2to predict kcatvalues for natural reactions of wild-type enzymes. Code is available at https://github.com/xfcui/TurNuP4.

The protein-ligand affinity prediction task aims to predict the binding strength of small molecule ligands to specific proteins, which is crucial in the fields of drug design and molecular biology, and can accelerate the drug discovery. The structure complementarity between protein and ligand plays a critical role in determining binding strength , but most of current deep learning-based affinity prediction models usually extracted the features of protein and ligand by these two detached modules. which limits the exchange of information for capturing interactions and struggles to capture proteins’ important residues. To address these limitations. we introduce CIP. which takes the combination of GNN, Conditional Updating and Proximity Embedding for the first time. Compared to existing models, CIP has several significant advantages. First, Conditional updating modifies the ligand’s local features based on the protein’s global features, and vice versa , enhancing structural complementarity to capture intricate interactions. Second, encoding the relative distances between proximal residue-atom pairs highlights critical residues. Additionally, our model integrates covalent and noncovalent interactions to obtain more comprehensive graph representations. Experiments on the PDB-bind 2016 benchmark demonstrate that CIP outperforms the original method with improvements of 2.3%, 3.2%, 2.8%, 3.8%, and 3.2% across five baselines. Furthermore, visualization results reveal that CIP effectively captures intricate interactions and crucial residues.The implemented code and dataset are available online at https://github.com/xfcui/CIP.

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.

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.

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.

Molecule property prediction based on computational strategies plays a key role in the process of drug discovery and design processes, such as DFT. However, these traditional methods are time-consuming, labor-intensive, and cannot satisfy the need for biomedicine. Owning to the development of deep learning, there are many variants of Graph Neural Networks (GNN) for molecular representation learning. However, the existing well-performing graph-based methods that have a number of parameters or light models cannot achieve good grades on various tasks. To manage the trade-off between efficiency and performance, we propose a novel model architecture, CoAtGIN, using both Convolution and Attention. At the local level, k-hop convolution is designed to capture long-range neighbor information. At the global level, in addition to using the virtual node to pass identical messages, we utilize linear attention to the aggregate global graph representation according to the importance of each node and edge. In the recent Open Graph Benchmark (OGB) Large-Scale Benchmark, CoAtGIN achieves the 0.0901 Mean Absolute Error (MAE) on the large-scale dataset PCQM4Mv2 with only 6.4 M model parameters. Moreover, using the linear attention block improves the performance, which helps to capture the global representation.

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.

Computing the genome rearrangement distance is an important subject in computational biology. The double cut and join operation(abbreviated as DCJ) has been extensively used for genome rearrangement over the last few years. When the genomes contain duplicate genes or segments, computing the DCJ distance becomes NP-hard, and there are scarcely positive results besides exploiting the algorithms for solving the minimum common string partition problem. As a twist, the DCJ adjacency distance, defined as the minimum number of DCJs to unify all the adjacencies between two genomes with duplicate genes or segments, reveals the similarity of the two genomes to a large extent. In this paper, we formally show that computing the DCJ adjacency distance is NP-hard, and present an approximation algorithm, which guarantees an approximation factor of $\frac{13}{9}+\varepsilon(\approx 1.44+\varepsilon)$ and runs in $O\left(\left(n \cdot 8^{\operatorname{logn}}\right)^{24 \cdot 7} \frac{1}{\varepsilon}\right)$ time, where n is the length of each genome. We also design an integer linear programming for computing the exact DCJ adjacency distance. Then, we apply our algorithm to simulated genomic data with bounded duplicate number, the solution of our algorithm is even better than the isochronal solution from the integer linear programming. Moreover, our algorithm approximates the DCJ adjacency distance between the genomes of Human and Gorilla with a real ratio of less than 1.12.

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.

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 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.

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).

Motivated by the trend of genome sequencing without completing the sequence of the whole genomes, a problem on filling an incomplete multichromosomal genome (or scaffold) I with respect to a complete target genome G was studied. The objective is to minimize the resulting genomic distance between I' and G, where I' is the corresponding filled scaffold. We call this problem the onesided scaffold filling problem. In this paper, we conduct a systematic study for the scaffold filling problem under the breakpoint distance and its variants, for both unichromosomal and multichromosomal genomes (with and without gene repetitions). When the input genome contains no gene repetition (i.e., is a fragment of a permutation), we show that the two-sided scaffold filling problem (i.e., G is also incomplete) is polynomially solvable for unichromosomal genomes under the breakpoint distance and for multichromosomal genomes under the genomic (or DCJ--Double-Cut-and-Join) distance. However, when the input genome contains some repeated genes, even the one-sided scaffold filling problem becomes NP-complete when the similarity measure is the maximum number of adjacencies between two sequences. For this problem, we also present efficient constant-factor approximation algorithms: factor-2 for the general case and factor 1.33 for the one-sided case.

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.

Describes the design and implementation of the WVTDB (Web-based VideoText DataBase) system that demonstrates our research on video data modeling, semantic content-based video querying and video database system architectures. The video data model of WVTDB is based on multi-level video data abstractions and annotation layering, thus allowing dynamic and incremental video annotation and indexing, multi-user view sharing and video data reuse. Users can query, retrieve and browse video data based on their semantic content descriptions and temporal constraints on the video segments. WVTDB employs a modular system architecture that supports distributed video query processing and subquery caching. Several techniques, such as video wrappers and lazy delivery, are also proposed specifically to address the network bandwidth limitations for this kind of Web-based system. We also address adaptivity, data access control and user profile issues.