The fragment assembly method is currently one of the most successful methods for the de novo protein structure prediction, where conformational change by fragment replacement is repeated with the simulated annealing scheme. We point out here that the conventional fragment replacement algorithm violates the detailed balance condition. This precludes application of various generalized ensemble algorithms, which would have made conformational sampling more efficient. We develop here a reversible variant of the fragment assembly algorithm which satisfies the detailed balance and thus is applicable to the generalized ensemble techniques. We combine this method with the multicanonical ensemble Monte Carlo, one of the generalized ensemble approaches, and test its performance in the structure prediction of three proteins. We show that the new method can find low energy conformations more efficiently than the conventional simulated annealing method. Also importantly, the lowest energy structures found by the new method are closer to the native than those by the simulated annealing. It seems that conformations with more complex topology can be generated by the new algorithm. (C) 2003 American Institute of Physics.