The protein threading problem with profiles is known to be efficiently solvable using dynamic programming. In this paper, we consider a variant of the protein threading problem with profiles in which constraints on distances between residues are given. We prove that protein threading with profiles and constraints is NP-hard. Moreover, we show a strong hardness result on the approximation of an optimal threading satisfying all the constraints. On the other hand, we develop two practical algorithms: CLIQUETHREAD and BBDPTHREAD. CLIQUETHREAD reduces the threading problem to the maximum edge-weight clique problem, whereas BBDPTHREAD combines dynamic programming and branch-and-bound techniques. We perform computational experiments using protein structure data in PDB (Protein Data Bank) using simulated distance constraints. The results show that constraints are useful to improve the alignment accuracy of the target sequence and the template structure. Moreover, these results also show that BBDPTHREAD is in general faster than CLIQUETHREAD for larger size proteins whereas CLIQUETHREAD is useful if there does not exist a feasible threading.

Measuring the cross-track profiles of a microtrack created by DC erasing both sides of a recorded track, the linear recording density dependence of the written track fringe width and that of the read track fringe width were successfully separated, both of which are usually observed in combination. It was clarified that when a thin-film head is used for reading, the read track fringe width increases as the linear recording density decreases, whereas it remains almost constant when an MR head with wide shielding layers is used. It was also clarified that the record head fringe width for a thin-film inductive head is less dependent on the linear recording density. The effects of several heads with different pole shapes on track edge phenomena were also evaluated, by partially DC erasing a written track from the track edge and measuring the change in the residual track output. It was found that the fringe field width of a record head changes depending on the pole shape, and the trimming of record head poles is very effective in reducing head field fringe effects.