PLEACH: a new heuristic algorithm for pure parsimony haplotyping problem

Haplotype inference is an important issue in computational biology due to its various applications in diagnosing and treating genetic diseases such as diabetes, Alzheimer, and heart defects. There are different criteria to choose the solution from the alternatives. Parsimony is one of the most impor...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of supercomputing 2024-04, Vol.80 (6), p.8236-8258
Main Authors: Feizabadi, Reza, Bagherian, Mehri, Vaziri, Hamidreza, Salahi, Maziar
Format: Article
Language:English
Subjects:
Algorithms
Compilers
Computer Science
Criteria
Heuristic methods
Integer programming
Interpreters
Linear programming
Mixed integer
Processor Architectures
Programming Languages
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Haplotype inference is an important issue in computational biology due to its various applications in diagnosing and treating genetic diseases such as diabetes, Alzheimer, and heart defects. There are different criteria to choose the solution from the alternatives. Parsimony is one of the most important criteria according to which the problem is known as Pure Parsimony Haplotyping (PPH) problem. The approaches to solve PPH are classified to two groups: exact and non-exact. The exact approaches often model the problem as a Mixed Integer Linear Programming (MILP) problem. Although in solving the small instances, these models generate the optimal solution in a reasonable time, because of the NP-hardness characteristic of PPH problem, they are ineffective in solving very large instances. This deficiency is compensated by non-exact algorithms. In this paper, we present a non-exact algorithm for large instances of PPH problem based on the divide-and-conquer technique. This algorithm, first, divides the problem into small sub-problems, which are solved by one of the previous exact approaches, and finally the solutions of the sub-problems are combined through solving an MILP. The appeared MILPs for solving the sub-problems and those for combining the solutions are so small that are solved rapidly. The performance of this algorithm has been evaluated by implementing it on real and simulated instances and in comparison with two well-known methods of PHASE and WinHap2.
ISSN:0920-8542
1573-0484
DOI:10.1007/s11227-023-05746-7