Background: Peptides are chemicals built of 20 types of amino acids linked into long chain
called sequence. Determination of amino acid sequence (order) in peptide is a very important issue of
modern molecular biology. There is no direct chemical method that allows determining long peptide
sequences. The approach to do so is to cut long sequence into short pieces, sequence them and then to
figure out what was their order in the original long sequence (proper order determines long sequence).
This process is called assembly and requires applying computational methods. In this paper, we present
dedicated heuristic for strongly NP-hard variant of peptide assembly problem.
Objective: The objective of the research was to propose a new method for peptide assembly problem.
There are a few metaheuristic methods available in the literature, however their results (similarity of
computed sequence compare to original one) are not good enough to be considered for practical use.
The main goal was to design dedicated heuristic that takes into account problem properties and finally
leads to better results.
Method: The considered variant of the peptide assembly problem was formulated using graph theory.
For metaheuristic methods available in the literature, a special variant of Hamiltonian problem had to be
solved to find the final peptide sequence. For dedicated heuristic, instead of looking for the special
variant of Hamiltonian path in this graph, the family of its sub-graphs (called adjoints) is searched for
the Hamiltonian path. The space of acceptable solutions that need to be searched to find the optimal
solution was strongly decreased in comparison to metaheuristic methods.
Results: The computational experiment has been performed to test dedicated heuristic and the obtained
results strongly exceed results of methods (solving this problem) which are available in the literature.
The average result for the new dedicated heuristic is 96.07% compared to 59,7% for Tabu Search,
72,32% for GRASP and 88,74% for evolutionary algorithm.
Conclusion: The obtained results clearly show that the new dedicated heuristic is much more useful in
the process of peptide sequence determination.