In recent years, with the emergence of big-data and high-throughput biological analyses, massive biological data have been generated and accessed, and many heuristic and metaheuristic algorithms have been proposed for further analysis and extraction of the potential knowledge of those data. Biological network alignment (BNA) aligns proteins between species to maximally conserve biological and topological structures of proteins. The studies of BNAs are essential for uncovering conserved protein interactions of biological networks with functional homology and understanding the evolutionary process across species. In this paper, we give a comprehensive review for the works in BNAs from a novel taxonomy: heuristic and metaheuristic BNAs. Moreover, we give some comparative analyses of the alignment models, real data sets, evaluation metrics and experimental results in these works. Finally, we provide some conclusions and give some possible future directions for BNAs.