Sequencing by hybridization is an attractive alternative for DNA sequencing. This novel method can be less time and cost consuming than the techniques applied nowadays. A very important step of this method is to solve a combinatorial problem formulated as a special case of the prize-collecting traveling salesman problem. In this work, we propose a new multistart construtive heuristic to solve this problem. A learning strategy based on adaptive memory and a vocabulary building procedure are used to improve the performance of the multistart heuristic. The adaptive memory is used to intensify the construction of new solutions with the elements that appear frequently in the best solutions previously found by the multistart heuristic. The objective of the vocabulary building procedure is to construct new solutions combining parts of good solutions. Computational experiments have shown that these two methods significantly improves the performance of the multistart heuristic and are particularly suitable for scheduling problems whose best solutions are in most cases built by blocks of elements that appear together very often. The proposed heuristic obtains systematically better solutions and is less time consuming than the best algorithms found in the literature.