SNPs Problems, Complexity, and Algorithms
SNPs Problems, Complexity, and Algorithms
复制标题
DOI：
10.1007/3-540-44676-1_15
复制
发表时间：
2001-08
期刊：
影响因子：
--
通讯作者：
G. Lancia;V. Bafna;S. Istrail;R. Lippert;R. Schwartz
中科院分区：
文献类型：
--
作者：
G. Lancia;V. Bafna;S. Istrail;R. Lippert;R. Schwartz
单核苷酸多态性（SNP）是人类遗传变异的最常见形式。它们对于包括医学诊断和药物设计在内的各种应用具有根本的重要性。它们还为追踪疾病基因提供了最高分辨率的基因组指纹。本文研究了基于二倍体生物基因组组装的计算SNPs验证的算法问题。在二倍体基因组中，每条染色体有两个拷贝。来自两条染色体之一的SNPs序列信息的描述称为SNPs单倍型。这里解决的基本问题是单倍型，即，给定从染色体的基因组区域的组装比对推断的一组SNP前景，通过去除与DNA测序错误、重复和旁系同源补充相关的数据“错误”来找到最大一致的SNP单倍型对。在本文中，我们介绍了几个版本的问题，从计算的角度来看。我们证明了对于配对组装数据来说，一般的SNP单倍型问题是NP难的，并设计了片段组装数据的多项式时间算法。我们给出了一个基于网络流的多项式算法的最小片段删除问题，我们表明，最小SNPs删除问题相当于找到最大的独立集在一个弱三角图。
Single nucleotide polymorphisms (SNPs) are the most frequent form of human genetic variation. They are of fundamental importance for a variety of applications including medical diagnostic and drug design. They also provide the highest-resolution genomic fingerprint for tracking disease genes. This paper is devoted to algorithmic problems related to computational SNPs validation based on genome assembly of diploid organisms. In diploid genomes, there are two copies of each chromosome. A description of the SNPs sequence information from one of the two chromosomes is called SNPs haplotype. The basic problem addressed here is the Haplotyping, i.e., given a set of SNPs prospects inferred from the assembly alignment of a genomic region of a chromosome, find the maximally consistent pair of SNPs haplotypes by removing data “errors” related to DNA sequencing errors, repeats, and paralogous recruitment. In this paper, we introduce several versions of the problem from a computational point of view. We show that the general SNPs Haplotyping Problem is NP-hard for mate-pairs assembly data, and design polynomial time algorithms for fragment assembly data. We give a network-flow based polynomial algorithm for the Minimum Fragment Removal Problem, and we show that the Minimum SNPs Removal problem amounts to finding the largest independent set in a weakly triangulated graph.