Volume 18, Issue 3 (9-2021)                   2021, 18(3): 1-13 | Back to browse issues page

XML Persian Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Etemadi M, Bagherian M, Vaziri H. Two Binary Linear Programming Models for Haplotype Assembly Problem in Triploid Case. Journal of Operational Research and Its Applications. 2021; 18 (3) :1-13
URL: http://jamlu.liau.ac.ir/article-1-1609-en.html
Department of Applied Mathematics, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran
Abstract:   (210 Views)
The haplotype assembly problem aims at finding originate haplotypes of some fragments that obtained from sequencing methods. In diploid case in which organisms have pair chromosomes, like humans, the aim is to reconstruct two haplotypes such that each of reads is originated from one of the two reconstructed haplotypes. In diploid case, the problem is well studied and since it is NP-hard due to unavoidable errors of sequencing machines, exact approaches are of exponential order. So, many fast, but approximate approaches have been proposed. In triploid case, the aim is finding three haplotypes such that each read originates from one of the three haplotypes. The triploid case is much harder than the diploid case and faces with more computational difficulties. For this reason, a few researchers studied the triploid case of haplotype assembly problem. In this paper, two binary linear programming models are proposed for two cases of availability and non-availability of genotype data for triploid haplotype assembly and the computational efficiency of the models is tested on simulated datasets using AIMMS. The proposed models could be generalized to higher ploidy.
Full-Text [PDF 852 kb]   (102 Downloads)    
Type of Study: Research | Subject: Special
Received: 2017/12/13 | Accepted: 2018/06/18

Add your comments about this article : Your username or Email:
CAPTCHA

Send email to the article author


Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.