Differentially mutated subnetworks discovery.
Abstract Problem: We study the problem of identifying differentially mutated subnetworks of a large gene-gene interaction network, that is, subnetworks that display a significant difference in mutation frequency in two sets of cancer samples. We formally define the associated computational problem and show that the problem is NP-hard. Algorithm: We propose a novel and efficient algorithm, called DAMOKLE, to identify differentially mutated subnetworks given genome-wide mutation data for two sets of cancer samples. We prove that DAMOKLE identifies subnetworks with statistically significant difference in mutatio...
Source: Algorithms for Molecular Biology : AMB - April 14, 2019 Category: Molecular Biology Authors: Hajkarim MC, Upfal E, Vandin F Tags: Algorithms Mol Biol Source Type: research

Repairing Boolean logical models from time-series data using Answer Set Programming.
Conclusions: The method was validated using known biological models from different species, as well as synthetic models obtained from randomly generated networks. We discuss the method's limitations regarding each of the updating schemes and the considered minimization algorithm. PMID: 30962813 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - April 10, 2019 Category: Molecular Biology Authors: Lemos A, Lynce I, Monteiro PT Tags: Algorithms Mol Biol Source Type: research

Connectivity problems on heterogeneous graphs.
Conclusion: Our results demonstrate that in contrast to most connectivity problems studied in computational biology, accounting for multiplicity of biological conditions adds considerable complexity, which we propose to address with a new solver. Importantly, our results extend to several network connectivity problems that are commonly used in computational biology, such as Prize-Collecting Steiner Tree, and provide insight into the theoretical guarantees for their applications in a multiple condition setting. PMID: 30899321 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 24, 2019 Category: Molecular Biology Authors: Wu J, Khodaverdian A, Weitz B, Yosef N Tags: Algorithms Mol Biol Source Type: research

External memory BWT and LCP computation for sequence collections with applications.
Conclusions: We prove that our algorithm performs O ( n maxlcp ) sequential I/Os, where n is the total length of the collection and maxlcp is the maximum LCP value. The experimental results show that our algorithm is only slightly slower than the state of the art for short sequences but it is up to 40 times faster for longer sequences or when the available RAM is at least equal to the size of the input. PMID: 30899322 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 24, 2019 Category: Molecular Biology Authors: Egidi L, Louza FA, Manzini G, Telles GP Tags: Algorithms Mol Biol Source Type: research

Semi-nonparametric modeling of topological domain formation from epigenetic data.
Conclusions: Our approach, nTDP, can form the basis of a unified, explanatory model of the relationship between epigenetic marks and topological domain structures. It can be used to predict domain boundaries for cell types, species, and conditions for which no Hi-C data is available. The model may also be of use for improving Hi-C-based domain finders. PMID: 30867673 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 15, 2019 Category: Molecular Biology Authors: Sefer E, Kingsford C Tags: Algorithms Mol Biol Source Type: research

SNPs detection by eBWT positional clustering.
Conclusions: Based on the results of the experiments on synthetic and real data, we conclude that the positional clustering framework can be effectively used for the problem of identifying SNPs, and it appears to be a promising approach for calling other type of variants directly on raw sequencing data. Availability: The software ebwt2snp is freely available for academic use at: https://github.com/nicolaprezza/ebwt2snp. PMID: 30839919 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 8, 2019 Category: Molecular Biology Authors: Prezza N, Pisanti N, Sciortino M, Rosone G Tags: Algorithms Mol Biol Source Type: research

Constrained incremental tree building: new absolute fast converging phylogeny estimation methods with improved scalability and accuracy.
In this study we present a new approach to large-scale phylogeny estimation that shares some of the features of DCM NJ but bypasses the use of supertree methods. We prove that this new approach is AFC and uses polynomial time and space. Furthermore, we describe variations on this basic approach that can be used with leaf-disjoint constraint trees (computed using methods such as maximum likelihood) to produce other methods that are likely to provide even better accuracy. Thus, we present a new generalizable technique for large-scale tree estimation that is designed to improve scalability for phylogeny estimation methods to...
Source: Algorithms for Molecular Biology : AMB - March 8, 2019 Category: Molecular Biology Authors: Zhang Q, Rao S, Warnow T Tags: Algorithms Mol Biol Source Type: research

Automated partial atomic charge assignment for drug-like molecules: a fast knapsack approach.
Abstract A key factor in computational drug design is the consistency and reliability with which intermolecular interactions between a wide variety of molecules can be described. Here we present a procedure to efficiently, reliably and automatically assign partial atomic charges to atoms based on known distributions. We formally introduce the molecular charge assignment problem, where the task is to select a charge from a set of candidate charges for every atom of a given query molecule. Charges are accompanied by a score that depends on their observed frequency in similar neighbourhoods (chemical environments) in...
Source: Algorithms for Molecular Biology : AMB - March 8, 2019 Category: Molecular Biology Authors: Engler MS, Caron B, Veen L, Geerke DP, Mark AE, Klau GW Tags: Algorithms Mol Biol Source Type: research

Regmex: a statistical tool for exploring motifs in ranked sequence lists from genomics experiments.
Conclusions: Regmex is a useful and flexible tool to analyze motif hypotheses that relates to large data sets in functional genomics. The method is available as an R package (https://github.com/muhligs/regmex). PMID: 30555524 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - December 19, 2018 Category: Molecular Biology Authors: Nielsen MM, Tataru P, Madsen T, Hobolth A, Pedersen JS Tags: Algorithms Mol Biol Source Type: research

Superbubbles revisited.
We present a reference implementation of the algorithm that accepts many commonly used formats for the input graph and provides convenient access to the improved algorithm. https://github.com/Fabianexe/Superbubble. PMID: 30519278 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - December 7, 2018 Category: Molecular Biology Authors: Gärtner F, Müller L, Stadler PF Tags: Algorithms Mol Biol Source Type: research

Coordinate systems for supergenomes.
Conclusion: Benchmarks on real-life data ranging from bacterial to fly genomes demonstrate the feasibility of computing good common coordinate systems. PMID: 30258487 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - September 29, 2018 Category: Molecular Biology Authors: Gärtner F, Höner Zu Siederdissen C, Müller L, Stadler PF Tags: Algorithms Mol Biol Source Type: research

Improved de novo peptide sequencing using LC retention time information.
Conclusions: Based on an evaluation for two prediction models on experimental data from synthesized peptides we conclude that the identification rates are improved by exploiting the chromatographic information. In our evaluation, we compare our algorithms using the retention time information with algorithms using the same scoring model, but not the retention time. PMID: 30181767 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - September 7, 2018 Category: Molecular Biology Authors: Frank Y, Hruz T, Tschager T, Venzin V Tags: Algorithms Mol Biol Source Type: research

Sorting signed circular permutations by super short operations.
Abstract Background: One way to estimate the evolutionary distance between two given genomes is to determine the minimum number of large-scale mutations, or genome rearrangements, that are necessary to transform one into the other. In this context, genomes can be represented as ordered sequences of genes, each gene being represented by a signed integer. If no gene is repeated, genomes are thus modeled as signed permutations of the form π=(π1π2…πn) , and in that case we can consider without loss of generality that one of them is the identity permutation ιn=(12…n) , and that we just ne...
Source: Algorithms for Molecular Biology : AMB - August 2, 2018 Category: Molecular Biology Authors: Oliveira AR, Fertin G, Dias U, Dias Z Tags: Algorithms Mol Biol Source Type: research

Split-inducing indels in phylogenomic analysis.
Conclusions: Suitably processed gap patterns extracted from genome-wide alignment provide a surprisingly clear phylogenetic signal and an allow the inference of accurate phylogenetic trees. PMID: 30026791 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - July 22, 2018 Category: Molecular Biology Authors: Donath A, Stadler PF Tags: Algorithms Mol Biol Source Type: research

A fast and accurate enumeration-based algorithm for haplotyping a triploid individual.
Conclusion: Extensive experimental comparisons were performed between the EHTLD algorithm and the well known HapCompass and HapTree. Compared with algorithms HapCompass and HapTree, the EHTLD algorithm can reconstruct more accurate haplotypes, which were proven by a number of experiments. PMID: 29881444 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - June 9, 2018 Category: Molecular Biology Authors: Wu J, Zhang Q Tags: Algorithms Mol Biol Source Type: research

Locus-aware decomposition of gene trees with respect to polytomous species trees.
Conclusions: Our approach allows for faster comparisons of gene and species trees and improves known algorithms for duplication inference in the presence of polytomies in the species trees. We have implemented our algorithms in a software tool available at https://github.com/mciach/LocusTreeInference. PMID: 29881445 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - June 9, 2018 Category: Molecular Biology Authors: Ciach MA, Muszewska A, Górecki P Tags: Algorithms Mol Biol Source Type: research

Finding local genome rearrangements.
Conclusions: A new variant of the weighted DCJ distance problem is addressed that ignores scenario length in its objective function. A solution to this problem provides a lower bound on the number of unlikely moves necessary when transforming one gene order into another. This lower bound aids in the study of rearrangement scenarios with respect to chromatin structure, and could eventually be used in the design of a fixed parameter algorithm with a more general objective function. PMID: 29755580 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - May 16, 2018 Category: Molecular Biology Authors: Simonaitis P, Swenson KM Tags: Algorithms Mol Biol Source Type: research

Outlier detection in BLAST hits.
Conclusion: Our experiments make a good case for using a two-step approach for accurate taxonomic assignment. We show that our method can be used as a filtering step before using phylogenetic methods and provides a way to interpret BLAST results using more information than provided by E-values and bit-scores alone. PMID: 29588650 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 30, 2018 Category: Molecular Biology Authors: Shah N, Altschul SF, Pop M Tags: Algorithms Mol Biol Source Type: research

FSH: fast spaced seed hashing exploiting adjacent hashes.
Conclusions: Spaced seed hashing is a routine task for several bioinformatics application. FSH allows to perform this task efficiently and raise the question of whether other hashing can be exploited to further improve the speed up. This has the potential of major impact in the field, making spaced seed applications not only accurate, but also faster and more efficient. Availability: The software FSH is freely available for academic use at: https://bitbucket.org/samu661/fsh/overview. PMID: 29588651 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 30, 2018 Category: Molecular Biology Authors: Girotto S, Comin M, Pizzi C Tags: Algorithms Mol Biol Source Type: research

OCTAL: Optimal Completion of gene trees in polynomial time.
Conclusions: OCTAL is a useful technique for adding missing taxa to incomplete gene trees and provides good accuracy under a wide range of model conditions. However, results show that OCTAL's accuracy can be reduced when incomplete lineage sorting is high, as the reference tree can be far from the true gene tree. Hence, this study suggests that OCTAL would benefit from using other types of reference trees instead of species trees when there are large topological distances between true gene trees and species trees. PMID: 29568323 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 24, 2018 Category: Molecular Biology Authors: Christensen S, Molloy EK, Vachaspati P, Warnow T Tags: Algorithms Mol Biol Source Type: research

Fast phylogenetic inference from typing data.
This article includes both a theoretical analysis and extensive experimental results concerning the proposed algorithm. We further show how this algorithm can be successfully integrated into a well known phylogenetic inference method, and how it can be used to speedup querying local phylogenetic patterns over large typing databases. PMID: 29467814 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - February 24, 2018 Category: Molecular Biology Authors: Carriço JA, Crochemore M, Francisco AP, Pissis SP, Ribeiro-Gonçalves B, Vaz C Tags: Algorithms Mol Biol Source Type: research

Derivative-free neural network for optimizing the scoring functions associated with dynamic programming of pairwise-profile alignment.
Conclusions: We developed and implemented a novel derivative-free neural network and aligner (Nepal) for optimizing sequence alignments. Nepal improved alignment quality by adapting to remote sequence alignments and increasing the expressiveness of similarity scores. Additionally, this novel scoring function can be realized using a simple matrix operation and easily incorporated into other aligners. Moreover our scoring function could potentially improve the performance of homology detection and/or multiple-sequence alignment of remote homologous sequences. The goal of the study was to provide a novel scoring function for ...
Source: Algorithms for Molecular Biology : AMB - February 24, 2018 Category: Molecular Biology Authors: Yamada KD Tags: Algorithms Mol Biol Source Type: research

A safe and complete algorithm for metagenomic assembly.
AI Abstract Background: Reconstructing the genome of a species from short fragments is one of the oldest bioinformatics problems. Metagenomic assembly is a variant of the problem asking to reconstruct the circular genomes of all bacterial species present in a sequencing sample. This problem can be naturally formulated as finding a collection of circular walks of a directed graph G that together cover all nodes, or edges, of G. Approach: We address this problem with the "safe and complete" framework of Tomescu and Medvedev (Research in computational Molecular biology-20th annual conference, RECOMB 9...
Source: Algorithms for Molecular Biology : AMB - February 17, 2018 Category: Molecular Biology Authors: Obscura Acosta N, Mäkinen V, Tomescu AI Tags: Algorithms Mol Biol Source Type: research

Time-consistent reconciliation maps and forbidden time travel.
Hellmuth M Abstract Background: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to event-labeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of...
Source: Algorithms for Molecular Biology : AMB - February 15, 2018 Category: Molecular Biology Authors: Nøjgaard N, Geiß M, Merkle D, Stadler PF, Wieseke N, Hellmuth M Tags: Algorithms Mol Biol Source Type: research

Gene tree parsimony for incomplete gene trees: addressing true biological loss.
We present new theory for GTP considering whether the incompleteness is due to gene birth and death (i.e., true biological loss) or taxon sampling, and present dynamic programming algorithms that can be used for an exact but exponential time solution for small numbers of taxa, or as a heuristic for larger numbers of taxa. We also prove that the "standard" calculations for duplications and losses exactly solve GTP when incompleteness results from taxon sampling, although they can be incorrect when incompleteness results from true biological loss. The software for the DP algorithm is freely available as open source...
Source: Algorithms for Molecular Biology : AMB - February 2, 2018 Category: Molecular Biology Authors: Bayzid MS, Warnow T Tags: Algorithms Mol Biol Source Type: research

Phylogeny reconstruction based on the length distribution of k-mismatch common substrings.
CA Abstract Background: Various approaches to alignment-free sequence comparison are based on the length of exact or inexact word matches between pairs of input sequences. Haubold et al. (J Comput Biol 16:1487-1500, 2009) showed how the average number of substitutions per position between two DNA sequences can be estimated based on the average length of exact common substrings. Results: In this paper, we study the length distribution of k-mismatch common substrings between two sequences. We show that the number of substitutions per position can be accurately estimated from the position of a local maximum in ...
Source: Algorithms for Molecular Biology : AMB - December 16, 2017 Category: Molecular Biology Authors: Morgenstern B, Schöbel S, Leimeister CA Tags: Algorithms Mol Biol Source Type: research

Generalized enhanced suffix array construction in external memory.
Conclusions: The proposed algorithm was validated through performance tests using real datasets from different domains, in various combinations, and showed a competitive performance. Our algorithm can also construct the generalized Burrows-Wheeler transform of a string collection with no additional cost except by the output time. PMID: 29234460 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - December 14, 2017 Category: Molecular Biology Authors: Louza FA, Telles GP, Hoffmann S, Ciferri CDA Tags: Algorithms Mol Biol Source Type: research

HAlign-II: efficient ultra-large multiple sequence alignment and phylogenetic tree reconstruction with distributed and parallel computing.
CONCLUSIONS: THAlign-II provides a user-friendly web server based on our distributed computing infrastructure. HAlign-II with open-source codes and datasets was established at http://lab.malab.cn/soft/halign. PMID: 29026435 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - October 15, 2017 Category: Molecular Biology Authors: Wan S, Zou Q Tags: Algorithms Mol Biol Source Type: research

Algorithms for matching partially labelled sequence graphs.
CONCLUSIONS: The methods develop here still need refinement and augmentation from constraints other than the sequence data alone, such as known interactions from annotation and databases, or non-trivial relationships in genome location. With the ever growing numbers of eukaryotic genomes, it is hoped that the methods described here will open a route to the use of these data equal to the current success attained with bacterial sequences. PMID: 29021818 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - October 14, 2017 Category: Molecular Biology Authors: Taylor WR Tags: Algorithms Mol Biol Source Type: research

Biologically feasible gene trees, reconciliation maps and informative triples.
Abstract BACKGROUND: The history of gene families-which are equivalent to event-labeled gene trees-can be reconstructed from empirically estimated evolutionary event-relations containing pairs of orthologous, paralogous or xenologous genes. The question then arises as whether inferred event-labeled gene trees are biologically feasible, that is, if there is a possible true history that would explain a given gene tree. In practice, this problem is boiled down to finding a reconciliation map-also known as DTL-scenario-between the event-labeled gene trees and a (possibly unknown) species tree. RESULTS: In this co...
Source: Algorithms for Molecular Biology : AMB - September 3, 2017 Category: Molecular Biology Authors: Hellmuth M Tags: Algorithms Mol Biol Source Type: research

Partially local three-way alignments and the sequence signatures of mitochondrial genome rearrangements.
CONCLUSIONS: The partially local sequence alignment method is an effective way to investigate the mechanism of genomic rearrangement events. While applied here only to mitogenomes there is no reason why the method could not be used to also consider rearrangements in nuclear genomes. PMID: 28852417 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - September 1, 2017 Category: Molecular Biology Authors: Al Arab M, Bernt M, Höner Zu Siederdissen C, Tout K, Stadler PF Tags: Algorithms Mol Biol Source Type: research

A hybrid parameter estimation algorithm for beta mixtures and applications to methylation state classification.
CONCLUSIONS: The hybrid algorithm between likelihood-based component un-mixing and moment-based parameter estimation is a robust and efficient method for beta mixture estimation. We provide an implementation of the method ("betamix") as open source software under the MIT license. PMID: 28828033 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - August 24, 2017 Category: Molecular Biology Authors: Schröder C, Rahmann S Tags: Algorithms Mol Biol Source Type: research

ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks.
CONCLUSION: The originality of our approach lies on the exhaustive enumeration of all possible (sets of) states verifying the properties of an attractor thanks to the use of ASP. Our method is applied to non-deterministic semantics in two different schemes (asynchronous and synchronous). The merits of our methods are illustrated by applying them to biological examples of various sizes and comparing the results with some existing approaches. It turns out that our approach succeeds to exhaustively enumerate on a desktop computer, in a large model (100 components), all existing attractors up to a given size (20 states). This ...
Source: Algorithms for Molecular Biology : AMB - August 19, 2017 Category: Molecular Biology Authors: Ben Abdallah E, Folschette M, Roux O, Magnin M Tags: Algorithms Mol Biol Source Type: research

Identification of bifurcation transitions in biological regulatory networks using Answer-Set Programming.
CONCLUSIONS: Our method allows a formal and scalable identification of transitions which are responsible for the lost of capability to reach a given state. It can be applied to any asynchronous automata networks, which encompass Boolean and multi-valued models. An implementation is provided as part of the Pint software, available at http://loicpauleve.name/pint. PMID: 28736575 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - July 26, 2017 Category: Molecular Biology Authors: Fitime LF, Roux O, Guziolowski C, Paulevé L Tags: Algorithms Mol Biol Source Type: research

A graph extension of the positional Burrows-Wheeler transform and its applications.
We present a generalization of the positional Burrows-Wheeler transform, or PBWT, to genome graphs, which we call the gPBWT. A genome graph is a collapsed representation of a set of genomes described as a graph. In a genome graph, a haplotype corresponds to a restricted form of walk. The gPBWT is a compressible representation of a set of these graph-encoded haplotypes that allows for efficient subhaplotype match queries. We give efficient algorithms for gPBWT construction and query operations. As a demonstration, we use the gPBWT to quickly count the number of haplotypes consistent with random walks in a genome graph, and ...
Source: Algorithms for Molecular Biology : AMB - July 15, 2017 Category: Molecular Biology Authors: Novak AM, Garrison E, Paten B Tags: Algorithms Mol Biol Source Type: research

Isometric gene tree reconciliation revisited.
CONCLUSIONS: We provide several new algorithms for isometric reconciliation of trees. Some questions in this area remain open; most importantly extensions of the problem allowing for imprecise estimates of branch lengths. PMID: 28630644 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - June 22, 2017 Category: Molecular Biology Authors: Brejová B, Gafurov A, Pardubská D, Sabo M, Vinař T Tags: Algorithms Mol Biol Source Type: research

A better scoring model for de novo peptide sequencing: the symmetric difference between explained and measured masses.
CONCLUSIONS: We conclude that considering the symmetric difference as optimization goal can improve the identification rates for de novo peptide sequencing. A preliminary version of this work has been presented at WABI 2016. PMID: 28603547 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - June 13, 2017 Category: Molecular Biology Authors: Tschager T, Rösch S, Gillet L, Widmayer P Tags: Algorithms Mol Biol Source Type: research

Algorithms for computing the double cut and join distance on both gene order and intergenic sizes.
CONCLUSIONS: We provide theoretical and empirical bounds on the expected growth of the parameter at the center of our FPT and ILP algorithms, assuming a probabilistic model of evolution under wDCJ, which shows that both these algorithms should run reasonably fast in practice. PMID: 28592988 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - June 10, 2017 Category: Molecular Biology Authors: Fertin G, Jean G, Tannier E Tags: Algorithms Mol Biol Source Type: research

StreAM-[Formula: see text]: algorithms for analyzing coarse grained RNA dynamics based on Markov models of connectivity-graphs.
CONCLUSIONS: The proposed algorithm performs well on large simulated as well as real world dynamic graphs. Additionally, StreAM-[Formula: see text] provides insights into nucleotide based RNA dynamics in comparison to conventional metrics like the root-mean square fluctuation. In the light of experimental data our results show important design opportunities for the riboswitch. PMID: 28572834 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - June 3, 2017 Category: Molecular Biology Authors: Jager S, Schiller B, Babel P, Blumenroth M, Strufe T, Hamacher K Tags: Algorithms Mol Biol Source Type: research

The gene family-free median of three.
CONCLUSIONS: We study the computational complexity of a new family-free model and present algorithms for its solution. With FFAdj-AM, we propose an appealing alternative to established tools for identifying higher confidence positional orthologs. PMID: 28559921 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - June 2, 2017 Category: Molecular Biology Authors: Doerr D, Balaban M, Feijão P, Chauve C Tags: Algorithms Mol Biol Source Type: research

Complexity and algorithms for copy-number evolution problems.
CONCLUSIONS: For the former problem we give a pseudo-polynomial dynamic programming algorithm that is linear in the profile length, and an integer linear program formulation. For the latter problem we show it is NP-hard and give an integer linear program formulation that scales to practical problem instance sizes. We assess the efficiency and quality of our algorithms on simulated instances. AVAILABILITY: https://github.com/raphael-group/CNT-ILP. PMID: 28515774 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - May 20, 2017 Category: Molecular Biology Authors: El-Kebir M, Raphael BJ, Shamir R, Sharan R, Zaccaria S, Zehavi M, Zeira R Tags: Algorithms Mol Biol Source Type: research

Core column prediction for protein multiple sequence alignments.
Abstract BACKGROUND: In a computed protein multiple sequence alignment, the coreness of a column is the fraction of its substitutions that are in so-called core columns of the gold-standard reference alignment of its proteins. In benchmark suites of protein reference alignments, the core columns of the reference alignment are those that can be confidently labeled as correct, usually due to all residues in the column being sufficiently close in the spatial superposition of the known three-dimensional structures of the proteins. Typically the accuracy of a protein multiple sequence alignment that has been computed f...
Source: Algorithms for Molecular Biology : AMB - April 26, 2017 Category: Molecular Biology Authors: DeBlasio D, Kececioglu J Tags: Algorithms Mol Biol Source Type: research

Gerbil: a fast and memory-efficient  k-mer counter with GPU-support.
Gerbil: a fast and memory-efficient k-mer counter with GPU-support. Algorithms Mol Biol. 2017;12:9 Authors: Erbert M, Rechner S, Müller-Hannemann M Abstract BACKGROUND: A basic task in bioinformatics is the counting of k-mers in genome sequences. Existing k-mer counting tools are most often optimized for small k
Source: Algorithms for Molecular Biology : AMB - April 6, 2017 Category: Molecular Biology Authors: Erbert M, Rechner S, Müller-Hannemann M Tags: Algorithms Mol Biol Source Type: research

Aligning coding sequences with frameshift extension penalties.
CONCLUSIONS: We compare the method to other CDS alignment methods based on an application to the comparison of pairs of CDS from homologous human, mouse and cow genes of ten mammalian gene families from the Ensembl-Compara database. The results show that our method is particularly robust to parameter changes as compared to existing methods. It also appears to be a good compromise, performing well both in the presence and absence of frameshift translations. An implementation of the method is available at https://github.com/UdeS-CoBIUS/FsePSA. PMID: 28373895 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - April 6, 2017 Category: Molecular Biology Authors: Jammali S, Kuitche E, Rachati A, Bélanger F, Scott M, Ouangraoua A Tags: Algorithms Mol Biol Source Type: research

The feasibility of genome-scale biological network inference using Graphics Processing Units.
Abstract Systems research spanning fields from biology to finance involves the identification of models to represent the underpinnings of complex systems. Formal approaches for data-driven identification of network interactions include statistical inference-based approaches and methods to identify dynamical systems models that are capable of fitting multivariate data. Availability of large data sets and so-called 'big data' applications in biology present great opportunities as well as major challenges for systems identification/reverse engineering applications. For example, both inverse identification and forward...
Source: Algorithms for Molecular Biology : AMB - March 29, 2017 Category: Molecular Biology Authors: Thiagarajan R, Alavi A, Podichetty JT, Bazil JN, Beard DA Tags: Algorithms Mol Biol Source Type: research

An efficient algorithm for testing the compatibility of phylogenies with nested taxa.
CONCLUSIONS: Taxonomies enable researchers to expand greatly the taxonomic coverage of their phylogenetic analyses. The running time of our method does not depend on the degrees of the nodes in the trees in [Formula: see text]. This characteristic is important when taxonomies-which can have nodes of high degree-are used. PMID: 28331536 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 25, 2017 Category: Molecular Biology Authors: Deng Y, Fernández-Baca D Tags: Algorithms Mol Biol Source Type: research

On the computational complexity of the maximum parsimony reconciliation problem in the duplication-loss-coalescence model.
CONCLUSIONS: These intractability results are likely to guide future research on algorithmic aspects of the DLC-reconciliation problem. PMID: 28316640 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 21, 2017 Category: Molecular Biology Authors: Bork D, Cheng R, Wang J, Sung J, Libeskind-Hadas R Tags: Algorithms Mol Biol Source Type: research

Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds.
te; L Abstract BACKGROUND: Spaced seeds, also named gapped q-grams, gapped k-mers, spaced q-grams, have been proven to be more sensitive than contiguous seeds (contiguous q-grams, contiguous k-mers) in nucleic and amino-acid sequences analysis. Initially proposed to detect sequence similarities and to anchor sequence alignments, spaced seeds have more recently been applied in several alignment-free related methods. Unfortunately, spaced seeds need to be initially designed. This task is known to be time-consuming due to the number of spaced seed candidates. Moreover, it can be altered by a set of arbitrary chosen p...
Source: Algorithms for Molecular Biology : AMB - March 17, 2017 Category: Molecular Biology Authors: Noé L Tags: Algorithms Mol Biol Source Type: research

Approximating the DCJ distance of balanced genomes in linear time.
CONCLUSIONS: Experiments on simulated data sets show that our approximation algorithm is very competitive both in efficiency and in quality of the solutions. PMID: 28293275 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 17, 2017 Category: Molecular Biology Authors: Rubert DP, Feijão P, Braga MD, Stoye J, Martinez FH Tags: Algorithms Mol Biol Source Type: research

Approximating the correction of weighted and unweighted orthology and paralogy relations.
CONCLUSIONS: We provided complexity and algorithmic results for variants of the problem of correcting a relation graph for satisfiability and consistency. For the maximization variants we were able to design polynomial time approximation schemes, while for the weighted minimization variants we were able to provide the first inapproximability results. PMID: 28293276 [PubMed] (Source: Algorithms for Molecular Biology : AMB)
Source: Algorithms for Molecular Biology : AMB - March 17, 2017 Category: Molecular Biology Authors: Dondi R, Lafond M, El-Mabrouk N Tags: Algorithms Mol Biol Source Type: research