Parameterized algorithm for the haplotype assembly MEC/GI model Academic Article

abstract

• Based on the characters of DNA fragments, the paper introduces a parameterized algorithm for the minimum error correction with genotype information (MEC/GI) model of the haplotype assembly problem. Its time complexity is O(nk22k2+ mlogm + mk1), where m is the number of fragments, n is the number of SNP sites, k1is the maximum number of SNP sites that a fragment covers (usually less than 10), and k2is the maximum number of the fragments covering a SNP site (usually not greater than 10). For the practical fragment data, the algorithm can solve the MEC/GI problem efficiently even if m and n are rather great, and it is scalable and applicable in practice.

authors

• Chen, Jianer

published proceedings

• Gaojishu Tongxin/Chinese High Technology Letters

author list (cited authors)

• Xie, M., Wang, J., & Chen, J.

complete list of authors

• Xie, M||Wang, J||Chen, J

publication date

• April 2008

published in

• Gaojishu tongxun  Journal

start page

• 422

end page

• 428

volume

• 18

issue

• 4