This paper advances the self-attention mechanism in the standard transformer network specific to the modeling of the protein sequences. We introduce a novel context-window based scaled self-attention mechanism for processing protein sequences that is based on the notion of (i) local context and (ii) large contextual pattern. Both notions are essential to building a good representation for protein sequences. The proposed context-window based scaled self-attention mechanism is further used to build the multi context-window based scaled (MCWS) transformer network for the protein function prediction task at the protein sub-sequence level. Overall, the proposed MCWS transformer network produced improved predictive performances, outperforming existing state-of-the-art approaches by substantial margins. With respect to the standard transformer network, the proposed network produced improvements in F1-score of +2.30% and +2.08% on the biological process (BP) and molecular function (MF) datasets, respectively. The corresponding improvements over the state-of-the-art ProtVecGen-Plus+ProtVecGen-Ensemble approach are +3.38% (BP) and +2.86% (MF). Equally important, robust performances were obtained across protein sequences of different lengths.

Suppose we aim to build a phylogeny for a set of taxa X using information from a collection of loci, where each locus offers information for only a fraction of the taxa. The question is whether the pattern of data availability, called a taxon coverage pattern, suffices to construct a reliable phylogeny. The problem can be expressed combinatorially as follows. We call a taxon coverage pattern decisive if for any binary phylogenetic tree$T$for X, the collection of phylogenetic trees obtained by restricting$T$to the subset of X covered by each locus uniquely determines$T$. We relate the problem of checking whether a taxon coverage pattern is decisive to a hypergraph coloring problem. Using this connection, we (1) show that checking decisiveness is co-NP complete; (2) obtain lower bounds on the amount of coverage needed to achieve decisiveness; (3) devise an exact algorithm for decisiveness; (4) develop problem reduction rules, and use them to obtain efficient algorithms for inputs with few loci; and (5) devise Boolean satisfiability and integer linear programming formulations that allow us to analyze real data sets. For data sets that are not decisive, we use these formulations to obtain decisive subsets of the data.

This paper explores the use of variants of tf-idf-based descriptors, namely length-normalized-tf-idf and log-normalized-tf-idf, combined with a segmentation technique, for efficient modeling of variable-length protein sequences. The proposed solution, ProtVecGen-Ensemble, is an ensemble of three models trained on differently segmented datasets constructed from an input dataset containing complete protein sequences. Evaluations using biological process (BP) and molecular function (MF) datasets demonstrate that the proposed feature set is not only superior to its contemporaries but also produces more consistent results with respect to variation in sequence lengths. Improvements of +6.07% (BP) and +7.56% (MF) over state-of-the-art tf-idf-based MLDA feature set were obtained. The best results were achieved when ProtVecGen-Ensemble was combined with ProtVecGen-Plus - the state-of-the-art method for protein function prediction - resulting in improvements of +8.90% (BP) and +11.28% (MF) over MLDA and +1.49% (BP) and +2.07% (MF) over ProtVecGen-Plus+MLDA. To capture the performance consistency with respect to sequence lengths, we have defined a variance-based metric, with lower values indicating better performance. On this metric, the proposed ProtVecGen-Ensemble+ProtVecGen-Plus framework resulted in reductions of 56.85 percent (BP) and 56.08 percent (MF) over MLDA and 10.37 percent (BP) and 26.48 percent (MF) over ProtVecGenPlus+MLDA.

The order of amino acids in a protein sequence enables the protein to acquire a conformation suitable for performing functions, thereby motivating the need to analyze these sequences for predicting functions. Although machine learning based approaches are fast compared to methods using BLAST, FASTA, etc., they fail to perform well for long protein sequences (with more than 300 amino acids). In this paper, we introduce a novel method for construction of two separate feature sets for protein using bi-directional long short-term memory network based on the analysis of fixed 1) single-sized segments and 2) multi-sized segments. The model trained on the proposed feature set based on multi-sized segments is combined with the model trained using state-of-the-art Multi-label Linear Discriminant Analysis (MLDA) features to further improve the accuracy. Extensive evaluations using separate datasets for biological processes and molecular functions demonstrate not only improved results for long sequences, but also significantly improve the overall accuracy over state-of-the-art method. The single-sized approach produces an improvement of +3.37 percent for biological processes and +5.48 percent for molecular functions over the MLDA based classifier. The corresponding numbers for multi-sized approach are +5.38 and +8.00 percent. Combining the two models, the accuracy further improves to +7.41 and +9.21 percent, respectively.

We consider the following basic problem in phylogenetic tree construction. Let $\mathcal P = {T_1, ..., T_k} be a collection of rooted phylogenetic trees over various subsets of a set of species. The tree compatibility problem asks whether there is a tree T with the following property: for each i in {1, ..., k}, T_i can be obtained from the restriction of T to the species set of T_i by contracting zero or more edges. If such a tree T exists, we say that P is compatible. We give a ~O(M_P) algorithm for the tree compatibility problem, where M_P is the total number of nodes and edges in P. Unlike previous algorithms for this problem, the running time of our method does not depend on the degrees of the nodes in the input trees. Thus, it is equally fast on highly resolved and highly unresolved trees.

SUMMARY: MulRF is a platform-independent software package for phylogenetic analysis using multi-copy gene trees. It seeks the species tree that minimizes the Robinson-Foulds (RF) distance to the input trees using a generalization of the RF distance to multi-labeled trees. The underlying generic tree distance measure and fast running time make MulRF useful for inferring phylogenies from large collections of gene trees, in which multiple evolutionary processes as well as phylogenetic error may contribute to gene tree discord. MulRF implements several features for customizing the species tree search and assessing the results, and it provides a user-friendly graphical user interface (GUI) with tree visualization. The species tree search is implemented in C++ and the GUI in Java Swing. AVAILABILITY: MulRF's executable as well as sample datasets and manual are available at http://genome.cs.iastate.edu/CBL/MulRF/, and the source code is available at https://github.com/ruchiherself/MulRFRepo. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We study the agreement supertree approach for combining rooted phylogenetic trees when the input trees do not fully agree on the relative positions of the taxa. We consider two ways to deal with such conflict. The first is to contract a set of edges in the input trees so that the resulting trees have an agreement supertree. We show that this problem is NP-complete and give a fixed-parameter tractable (FPT) algorithm for the problem parameterized by the number of input trees and the number of edges contracted. The second approach is to remove a set of taxa from the input trees so that the resulting trees have an agreement supertree. Guillemot and Berry (2010) gave an FPT algorithm for this problem when the input trees are all binary. We give an FPT algorithm for the more general case where the input trees are allowed to have arbitrary degree.

A Robinson-Foulds (RF) supertree for a collection of input trees is a tree containing all the species in the input trees that is at minimum total RF distance to the input trees. Thus, an RF supertree is consistent with the maximum number of splits in the input trees. Constructing RF supertrees for rooted and unrooted data is NP-hard. Nevertheless, effective local search heuristics have been developed for the restricted case where the input trees and the supertree are rooted. We describe new heuristics, based on the Edge Contract and Refine (ECR) operation, that remove this restriction, thereby expanding the utility of RF supertrees. Our experimental results on simulated and empirical data sets show that our unrooted local search algorithms yield better supertrees than those obtained from MRP and rooted RF heuristics in terms of total RF distance to the input trees and, for simulated data, in terms of RF distance to the true tree.

BACKGROUND: The gene duplication (GD) problem seeks a species tree that implies the fewest gene duplication events across a given collection of gene trees. Solving this problem makes it possible to use large gene families with complex histories of duplication and loss to infer phylogenetic trees. However, the GD problem is NP-hard, and therefore, most analyses use heuristics that lack any performance guarantee. RESULTS: We describe the first integer linear programming (ILP) formulation to solve instances of the gene duplication problem exactly. With simulations, we demonstrate that the ILP solution can solve problem instances with up to 14 taxa. Furthermore, we apply the new ILP solution to solve the gene duplication problem for the seed plant phylogeny using a 12-taxon, 6,084-gene data set. The unique, optimal solution, which places Gnetales sister to the conifers, represents a new, large-scale genomic perspective on one of the most puzzling questions in plant systematics. CONCLUSIONS: Although the GD problem is NP-hard, our novel ILP solution for it can solve instances with data sets consisting of as many as 14 taxa and 1,000 genes in a few hours. These are the largest instances that have been solved to optimally to date. Thus, this work can provide large-scale genomic perspectives on phylogenetic questions that previously could only be addressed by heuristic estimates.

BACKGROUND: The ever-increasing wealth of genomic sequence information provides an unprecedented opportunity for large-scale phylogenetic analysis. However, species phylogeny inference is obfuscated by incongruence among gene trees due to evolutionary events such as gene duplication and loss, incomplete lineage sorting (deep coalescence), and horizontal gene transfer. Gene tree parsimony (GTP) addresses this issue by seeking a species tree that requires the minimum number of evolutionary events to reconcile a given set of incongruent gene trees. Despite its promise, the use of gene tree parsimony has been limited by the fact that existing software is either not fast enough to tackle large data sets or is restricted in the range of evolutionary events it can handle. RESULTS: We introduce iGTP, a platform-independent software program that implements state-of-the-art algorithms that greatly speed up species tree inference under the duplication, duplication-loss, and deep coalescence reconciliation costs. iGTP significantly extends and improves the functionality and performance of existing gene tree parsimony software and offers advanced features such as building effective initial trees using stepwise leaf addition and the ability to have unrooted gene trees in the input. Moreover, iGTP provides a user-friendly graphical interface with integrated tree visualization software to facilitate analysis of the results. CONCLUSIONS: iGTP enables, for the first time, gene tree parsimony analyses of thousands of genes from hundreds of taxa using the duplication, duplication-loss, and deep coalescence reconciliation costs, all from within a convenient graphical user interface.

Efficient sensitivity analysis algorithms are presented for two problems arising in the study of Markov models of sequence evolution: ancestral reconstruction in evolutionary trees and local ungapped alignment under log-odds scoring. The algorithms generate complete descriptions of the optimum solutions for all possible values of the evolutionary distance. The running time for the parametric ancestral reconstruction problem under the Kimura 2-parameter model is O ( kn + kn 2/3 log k ), where n is the number of sequences and k is their length, assuming all edges have the same length. For the parametric gapless alignment problem under the Jukes-Cantor model, the running time is O ( mn + mn 2/3 log m ), where m and n are the sequence lengths and n ≤ m .

The input to a supertree problem is a collection of phylogenetic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in the input. This task is complicated by inconsistencies due to errors. We consider the case where the input trees are rooted and are represented by the clusters they exhibit. The problem is to find the minimum number of flips needed to resolve all inconsistencies, where each flip moves a taxon into or out of a cluster. We prove that the minimum-flip problem is NP-complete, but show that it is fixed-parameter tractable and give approximation algorithms for special cases.

UNLABELLED: Rainbow is a program that provides a graphic user interface to construct supertrees using different methods. It also provides tools to analyze the quality of the supertrees produced. Rainbow is available for Mac OS X, Windows and Linux. AVAILABILITY: Rainbow is a free open-source software. Its binary files, source code, and manual can be downloaded from the Rainbow web page: http://genome.cs.iastate.edu/Rainbow/

A parameterized version of the Steiner tree problem in phylogeny is defined, where the parameter measures the amount by which a phylogeny differs from "perfection." This problem is shown to be solvable in polynomial time for any fixed value of the parameter.

We present a weighted version of Megiddo’s multidimensional search technique and use it to obtain faster algorithms for certain convex optimization problems in ${\bf R}^d $, for fixed d. This leads to speed-ups by a factor of $\log ^d n$ for applications such as solving the Lagrangian duals of matroidal knapsack problems and of constrained optimum subgraph problems on graphs of bounded tree-width.

This paper presents a polynomial-time algorithm for determining whether a set of species, described by the characters they exhibit, has a perfect phylogeny, assuming the maximum number of possible states for a character is fixed. This solves a longstanding open problem. This result should be contrasted with the proof by Steel [J. Classification, 9(1992), pp. 91–1161 and Bodlaender, Fellows, and Warnow [Proceedings of the 19th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, 1992, pp. 273–2831 that the perfect phylogeny problem is NP complete in general.

We present a polynomial-time algorithm for determining whether a set of species, described by the characters they exhibit, has a perfect phylogeny, assuming the maximum number of possible states for a character is fixed. This solves a longstanding open problem. Our result should be contrasted with the proof by Steel and Bodlaender, Fellows, and Warnow that the perfect phylogeny problem is NP-complete in general.>

The problem of allocating modules to processors in a distributed system to minimize total costs when the underlying communication graph is a partial k-tree and all costs are linear functions of a real parameter t is considered. It is shown that if the number of processors is fixed, the sequence of optimum assignments that are obtained as t varies from zero to infinity can be constructed in polynomial time. As an auxiliary result, a linear time separator algorithm for k-trees is developed. The implications of the results for parametric versions of the weighted vertex cover, independent set, and 0-1 quadratic programming problems on partial k-trees are discussed.>

The author studies the complexity of the problem of allocating modules to processes in a distributed system to minimize total communication and execution costs. He shows that unless P=NP, there can be no polynomial-time epsilon -approximate algorithm for the problem, nor can there exist a local search algorithm that requires polynomial time per iteration and yields an optimum assignment. Both results hold even if the communication graph is planar and bipartite. On the positive side, it is shown that if the communication graph is a partial k-tree or an almost-tree with parameter k, the module allocation problem can be solved in polynomial time.>

We discuss network flow in a bipartite graph G with node sets S and T. We show that Karzanov’s algorithm runs in time $O(|S|^2 |T|)$ on G, and that the MPM algorithm can be modified to run in the same bound. For the common case that the degree of each node in T is bounded by a constant, we show that a modified version of the MPM algorithm runs in time $O(|S|^3 + |S||T|)$ on G. The importance of these results comes from the common occurrence of problems that can be modeled and solved using network flow on bipartite graphs where $|S| \ll |T|$. In many applications involving bounded degree on the nodes in T, $|T| = \theta (|S|^2 )$, and our results reduce the best bounds on bipartite flow from $O(|S|^6 )$ to $O(|S|^3 )$. We use our results on bipartite flow to obtain the fastest known bounds on several combinatorial problems, and mention several additional problems involving bipartite flow where $|S|$ is much smaller than $|T|$.