COLT: Constrained Lineage Tree Generation from Sequence Data.
COLT: Constrained Lineage Tree Generation from Sequence Data.
复制标题
COLT：从序列数据生成约束谱系树。
DOI：
10.1109/bibm.2016.7822500
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ning,Jiang
中科院分区：
文献类型：
--
作者：
Chen,Keke;Gogu,VenkataSaiAbhishek;Wu,Di;Ning,Jiang
谱系分析已成为了解突变模式和基因多样性的重要方法，如抗体。突变谱系通常表示为树结构，描述可能的突变路径。从序列数据生成谱系树带来了两个独特的挑战：（1）约束类型可能在序列数据和树结构之上定义，这必须由算法适当地制定和维护。(2)枚举满足约束的所有可能的树通常在计算上是难以处理的。在本文中，我们提出了一个约束谱系树生成框架（COLT），建立谱系树序列，根据指定的领域专家和衍生的变异过程的遗传学的局部和全局约束。我们的形式化分析和实验结果表明，该框架可以有效地生成有效的谱系树，同时严格满足领域专家指定的约束。
Lineage analysis has been an important method for understanding the mutation patterns and the diversity of genes, such as antibodies. A mutation lineage is typically represented as a tree structure, describing the possible mutation paths. Generating lineage trees from sequence data imposes two unique challenges: (1) Types of constraints might be defined on top of sequence data and tree structures, which have to be appropriately formulated and maintained by the algorithms. (2) Enumerating all possible trees that satisfy constraints is typically computationally intractable. In this paper, we present a COnstrained Lineage Tree generation framework (COLT) that builds lineage trees from sequences, based on local and global constraints specified by domain experts and heuristics derived from the mutation processes. Our formal analysis and experimental results show that this framework can efficiently generate valid lineage trees, while strictly satisfying the constraints specified by domain experts.