In a fast-paced and ever-changing world with evolution of technology, the researchers are more interested in developing solutions in the challenging field of bioinformatics for modern precise medicine, health care and therapy. Therefore, the need of many tools in analyzing biological data such DNA/RNA and proteins in the objective to understand and cure many diseases and pathologies. Among the important bioinformatics problems, the phylogenetic tree reconstruction that contribute in the comprehension of the different specie’s evolution. This evolutionary tree construction is a computational problem that can be solved in non-deterministic polynomial-time, called NP-hard due to the computational complexity necessary to obtain the optimal phylogenetic trees in the space of all the possible patterns. Hence many approximation techniques such as heuristics and metaheuristics were developed as solution strategies to solve this problem. These algorithms tend to offer high quality solutions within a reasonable amount of time. This paper study phylogenetic reconstruction methods for the establishment of ancestral relationships from amino acid sequences which help seeking the origin and spread of epidemics infections or to infer the evolutionary history of diseases such as cancer progression. The aim of this paper is to propose and analyze scientific literature review of existing work. Specific information from papers published between the years 2010 and 2024 are extracted, it illustrates and discusses the recent most used metaheuristics and methods, their limitations and challenges. This study highlights the constant interest in this subject for continued research to develop and refine metaheuristics techniques due to the various recent research publications to solve the problem.