Summary: Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The {\sc Longest} {\sc Arc}-{\sc Preserving} {\sc Common} {\sc Subsequence}(LAPCS) problem has recently been introduced in [{\it P. A. Evans}, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria (1999), {\it P. A. Evans}, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM’99), in: Lect. Notes Comput. Sci. 1645, 270‒280 (1999; Zbl 1063.68616)] as a framework for studying the similarity of arc-annotated sequences. In this paper, we consider arc-annotated sequences with various arc structures and present some new algorithmic and complexity results on the LAPCS problem. Some of our results answer an open question in [P.A. Evans, loc. cit.] and some others improve the hardness results in [P. A. Evans, loc. cit]. An extended abstract of this work appears in Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000), Lect. Notes Comput. Sci. 1848, 154‒165 (2000; Zbl 0964.92031)]