• 主题
高级搜索  >
历史搜索 清空历史

您现在的位置：首页>美国卫生研究院文献>Algorithms for Molecular Biology : AMB

期刊信息

  • 期刊名称：

    -

  • 刊频：
  • NLM标题：
  • iso缩写： -
  • ISSN： -

年度选择

更多>>

  • 排序：
  • 显示：
  • 每页：
全选（0）
<1/19>
共370条结果
  • 1.

    【2hr】Automated partial atomic charge assignment for drug-like molecules: a fast knapsack approach

    包量

    机译 药物分子的自动部分原子电荷分配：快速背包法
    摘要：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 a database of previously parameterised molecules. The aim is to assign the charges such that the total charge equals a known target charge within a margin of error while maximizing the sum of the charge scores. We show that the problem is a variant of the well-studied multiple-choice knapsack problem and thus weakly NP-complete. We propose solutions based on Integer Linear Programming and a pseudo-polynomial time Dynamic Programming algorithm. We demonstrate that the results obtained for novel molecules not included in the database are comparable to the ones obtained performing explicit charge calculations while decreasing the time to determine partial charges for a molecule from hours or even days to below a second. Our software is openly available.
  • 2.

    【2hr】Constrained incremental tree building: new absolute fast converging phylogeny estimation methods with improved scalability and accuracy

    包量

    机译 约束增量树构建：具有改进的可扩展性和准确性的新的绝对快速收敛系统发育估计方法
    摘要：BackgroundAbsolute fast converging (AFC) phylogeny estimation methods are ones that have been proven to recover the true tree with high probability given sequences whose lengths are polynomial in the number of number of leaves in the tree (once the shortest and longest branch weights are fixed). While there has been a large literature on AFC methods, the best in terms of empirical performance was DCMNJ, published in SODA 2001. The main empirical advantage of DCMNJ over other AFC methods is its use of neighbor joining (NJ) to construct trees on smaller taxon subsets, which are then combined into a tree on the full set of species using a supertree method; in contrast, the other AFC methods in essence depend on quartet trees that are computed independently of each other, which reduces accuracy compared to neighbor joining. However, DCMNJ is unlikely to scale to large datasets due to its reliance on supertree methods, as no current supertree methods are able to scale to large datasets with high accuracy.
  • 3.

    【2hr】SNPs detection by eBWT positional clustering

    包量

    机译 通过eBWT位置聚类检测SNP
    摘要：BackgroundSequencing technologies keep on turning cheaper and faster, thus putting a growing pressure for data structures designed to efficiently store raw data, and possibly perform analysis therein. In this view, there is a growing interest in alignment-free and reference-free variants calling methods that only make use of (suitably indexed) raw reads data.
  • 4.

    【2hr】Semi-nonparametric modeling of topological domain formation from epigenetic data

    包量

    机译 基于表观遗传数据的拓扑域形成的半非参数建模
    摘要：BackgroundHi-C experiments capturing the 3D genome architecture have led to the discovery of topologically-associated domains (TADs) that form an important part of the 3D genome organization and appear to play a role in gene regulation and other functions. Several histone modifications have been independently associated with TAD formation, but their combinatorial effects on domain formation remain poorly understood at a global scale.
  • 5.

    【2hr】Connectivity problems on heterogeneous graphs

    包量

    机译 异构图上的连通性问题
    摘要：BackgroundNetwork connectivity problems are abundant in computational biology research, where graphs are used to represent a range of phenomena: from physical interactions between molecules to more abstract relationships such as gene co-expression. One common challenge in studying biological networks is the need to extract meaningful, small subgraphs out of large databases of potential interactions. A useful abstraction for this task turned out to be the Steiner Network problems: given a reference “database” graph, find a parsimonious subgraph that satisfies a given set of connectivity demands. While this formulation proved useful in a number of instances, the next challenge is to account for the fact that the reference graph may not be static. This can happen for instance, when studying protein measurements in single cells or at different time points, whereby different subsets of conditions can have different protein milieu.
  • 6.

    【2hr】External memory BWT and LCP computation for sequence collections with applications

    包量

    机译 外部存储器BWT和LCP计算，用于与应用程序进行序列收集
    摘要：BackgroundSequencing technologies produce larger and larger collections of biosequences that have to be stored in compressed indices supporting fast search operations. Many compressed indices are based on the Burrows–Wheeler Transform (BWT) and the longest common prefix (LCP) array. Because of the sheer size of the input it is important to build these data structures in external memory and time using in the best possible way the available RAM.
  • 7.

    【2hr】Reconciling multiple genes trees via segmental duplications and losses

    包量

    机译 通过片段重复和丢失来协调多个基因树
    摘要：Reconciling gene trees with a species tree is a fundamental problem to understand the evolution of gene families. Many existing approaches reconcile each gene tree independently. However, it is well-known that the evolution of gene families is interconnected. In this paper, we extend a previous approach to reconcile a set of gene trees with a species tree based on segmental macro-evolutionary events, where segmental duplication events and losses are associated with cost δ and λ, respectively. We show that the problem is polynomial-time solvable when δ≤λ (via LCA-mapping), while if δ>λ the problem is NP-hard, even when λ=0 and a single gene tree is given, solving a long standing open problem on the complexity of multi-gene reconciliation. On the positive side, we give a fixed-parameter algorithm for the problem, where the parameters are δ/λ and the number d of segmental duplications, of time complexity O⌈δλ⌉d·n·δλ. Finally, we demonstrate the usefulness of this algorithm on two previously studied real datasets: we first show that our method can be used to confirm or raise doubt on hypothetical segmental duplications on a set of 16 eukaryotes, then show how we can detect whole genome duplications in yeast genomes.
  • 8.

    【2hr】Kermit: linkage map guided long read assembly

    包量

    机译 柯米特（Kermit）：链接图指导的长读汇编
    摘要：Background With long reads getting even longer and cheaper, large scale sequencing projects can be accomplished without short reads at an affordable cost. Due to the high error rates and less mature tools, de novo assembly of long reads is still challenging and often results in a large collection of contigs. Dense linkage maps are collections of markers whose location on the genome is approximately known. Therefore they provide long range information that has the potential to greatly aid in de novo assembly. Previously linkage maps have been used to detect misassemblies and to manually order contigs. However, no fully automated tools exist to incorporate linkage maps in assembly but instead large amounts of manual labour is needed to order the contigs into chromosomes.
  • 9.

    【2hr】Repairing Boolean logical models from time-series data using Answer Set Programming

    包量

    机译 使用答案集编程从时间序列数据修复布尔逻辑模型
    摘要：BackgroundBoolean models of biological signalling-regulatory networks are increasingly used to formally describe and understand complex biological processes. These models may become inconsistent as new data become available and need to be repaired. In the past, the focus has been shed on the inference of (classes of) models given an interaction network and time-series data sets. However, repair of existing models against new data is still in its infancy, where the process is still manually performed and therefore slow and prone to errors.
  • 10.

    【2hr】Differentially mutated subnetworks discovery

    包量

    机译 差分变异的子网发现
    摘要：ProblemWe 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.
  • 11.

    【2hr】An average-case sublinear forward algorithm for the haploid Li and Stephens model

    包量

    机译 单倍Li和Stephens模型的平均情况亚线性正演算法
    摘要：BackgroundHidden Markov models of haplotype inheritance such as the Li and Stephens model allow for computationally tractable probability calculations using the forward algorithm as long as the representative reference panel used in the model is sufficiently small. Specifically, the monoploid Li and Stephens model and its variants are linear in reference panel size unless heuristic approximations are used. However, sequencing projects numbering in the thousands to hundreds of thousands of individuals are underway, and others numbering in the millions are anticipated.
  • 12.

    【2hr】Linear time minimum segmentation enables scalable founder reconstruction

    包量

    机译 线性时间最小分割可实现可扩展的创始人重建
    摘要：Background We study a preprocessing routine relevant in pan-genomic analyses: consider a set of aligned haplotype sequences of complete human chromosomes. Due to the enormous size of such data, one would like to represent this input set with a few founder sequences that retain as well as possible the contiguities of the original sequences. Such a smaller set gives a scalable way to exploit pan-genomic information in further analyses (e.g. read alignment and variant calling). Optimizing the founder set is an NP-hard problem, but there is a segmentation formulation that can be solved in polynomial time, defined as follows. Given a threshold L and a set R={R1,…,Rm} of m strings (haplotype sequences), each having length n, the minimum segmentation problem for founder reconstruction is to partition [1, n] into set P of disjoint segments such that each segment [a,b]∈P has length at least L and the number d(a,b)=|{Ri[a,b]:1≤i≤m}| of distinct substrings at segment [a, b] is minimized over [a,b]∈P. The distinct substrings in the segments represent founder blocks that can be concatenated to form max{d(a,b):[a,b]∈P} founder sequences representing the original R such that crossovers happen only at segment boundaries.
  • 13.

    【2hr】Prefix-free parsing for building big BWTs

    包量

    机译 用于构建大型BWT的无前缀解析
    摘要：High-throughput sequencing technologies have led to explosive growth of genomic databases; one of which will soon reach hundreds of terabytes. For many applications we want to build and store indexes of these databases but constructing such indexes is a challenge. Fortunately, many of these genomic databases are highly-repetitive—a characteristic that can be exploited to ease the computation of the Burrows-Wheeler Transform (BWT), which underlies many popular indexes. In this paper, we introduce a preprocessing algorithm, referred to as prefix-free parsing, that takes a text T as input, and in one-pass generates a dictionary D and a parse P of T with the property that the BWT of T can be constructed from D and P using workspace proportional to their total size and O(|T|)-time. Our experiments show that D and P are significantly smaller than T in practice, and thus, can fit in a reasonable internal memory even when T is very large. In particular, we show that with prefix-free parsing we can build an 131-MB run-length compressed FM-index (restricted to support only counting and not locating) for 1000 copies of human chromosome 19 in 2 h using 21  GB of memory, suggesting that we can build a 6.73 GB index for 1000 complete human-genome haplotypes in approximately 102 h using about 1 TB of memory.
  • 14.

    【2hr】Statistically consistent divide-and-conquer pipelines for phylogeny estimation using NJMerge

    包量

    机译 使用NJMerge进行统计上一致的分治管道以进行系统发育评估
    摘要：BackgroundDivide-and-conquer methods, which divide the species set into overlapping subsets, construct a tree on each subset, and then combine the subset trees using a supertree method, provide a key algorithmic framework for boosting the scalability of phylogeny estimation methods to large datasets. Yet the use of supertree methods, which typically attempt to solve NP-hard optimization problems, limits the scalability of such approaches.
  • 15.

    【2hr】A general framework for genome rearrangement with biological constraints

    包量

    机译 具有生物学限制的基因组重排的一般框架
    摘要：This paper generalizes previous studies on genome rearrangement under biological constraints, using double cut and join (DCJ). We propose a model for weighted DCJ, along with a family of optimization problems called φ-MCPS (Minimum Cost Parsimonious Scenario), that are based on labeled graphs. We show how to compute solutions to general instances of φ-MCPS, given an algorithm to compute φ-MCPS on a circular genome with exactly one occurrence of each gene. These general instances can have an arbitrary number of circular and linear chromosomes, and arbitrary gene content. The practicality of the framework is displayed by presenting polynomial-time algorithms that generalize the results of Bulteau, Fertin, and Tannier on the Sorting by wDCJs and indels in intergenes problem, and that generalize previous results on the Minimum Local Parsimonious Scenario problem.
  • 16.

    【2hr】A multi-labeled tree dissimilarity measure for comparing “clonal trees” of tumor progression

    包量

    机译 用于比较肿瘤进展的“克隆树”的多标签树差异度量
    摘要：We introduce a new dissimilarity measure between a pair of “clonal trees”, each representing the progression and mutational heterogeneity of a tumor sample, constructed by the use of single cell or bulk high throughput sequencing data. In a clonal tree, each vertex represents a specific tumor clone, and is labeled with one or more mutations in a way that each mutation is assigned to the oldest clone that harbors it. Given two clonal trees, our multi-labeled tree dissimilarity (MLTD) measure is defined as the minimum number of mutation/label deletions, (empty) leaf deletions, and vertex (clonal) expansions, applied in any order, to convert each of the two trees to the maximum common tree. We show that the MLTD measure can be computed efficiently in polynomial time and it captures the similarity between trees of different clonal granularity well.
  • 17.

    【2hr】A branching process for homology distribution-based inference of polyploidy, speciation and loss

    包量

    机译 基于同源分布的多倍性，物种形成和损失的分支过程
    摘要：BackgroundThe statistical distribution of the similarity or difference between pairs of paralogous genes, created by whole genome doubling, or between pairs of orthologous genes in two related species is an important source of information about genomic evolution, especially in plants.
  • 18.

    【2hr】Implications of non-uniqueness in phylogenetic deconvolution of bulk DNA samples of tumors

    包量

    机译 非唯一性在肿瘤大分子DNA样品系统发生去卷积中的意义
    摘要：BackgroundTumors exhibit extensive intra-tumor heterogeneity, the presence of groups of cellular populations with distinct sets of somatic mutations. This heterogeneity is the result of an evolutionary process, described by a phylogenetic tree. In addition to enabling clinicians to devise patient-specific treatment plans, phylogenetic trees of tumors enable researchers to decipher the mechanisms of tumorigenesis and metastasis. However, the problem of reconstructing a phylogenetic tree T given bulk sequencing data from a tumor is more complicated than the classic phylogeny inference problem. Rather than observing the leaves of T directly, we are given mutation frequencies that are the result of mixtures of the leaves of T. The majority of current tumor phylogeny inference methods employ the perfect phylogeny evolutionary model. The underlying Perfect Phylogeny Mixture (PPM) combinatorial problem typically has multiple solutions.
  • 19.

    【2hr】Bayesian localization of CNV candidates in WGS data within minutes

    包量

    机译 在几分钟之内即可在WGS数据中对CNV候选对象进行贝叶斯定位
    摘要：BackgroundFull Bayesian inference for detecting copy number variants (CNV) from whole-genome sequencing (WGS) data is still largely infeasible due to computational demands. A recently introduced approach to perform Forward–Backward Gibbs sampling using dynamic Haar wavelet compression has alleviated issues of convergence and, to some extent, speed. Yet, the problem remains challenging in practice.
  • 20.

    【2hr】Gene tree parsimony for incomplete gene trees: addressing true biological loss

    包量

    机译 不完整基因树的基因树简约：解决真正的生物损失
    摘要：Motivation Species tree estimation from gene trees can be complicated by gene duplication and loss, and “gene tree parsimony” (GTP) is one approach for estimating species trees from multiple gene trees. In its standard formulation, the objective is to find a species tree that minimizes the total number of gene duplications and losses with respect to the input set of gene trees. Although much is known about GTP, little is known about how to treat inputs containing some incomplete gene trees (i.e., gene trees lacking one or more of the species).
题名 作者 来源 发表时间

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号