DNA là phân tử mang thông tin di truyền quy định mọi hoạt động sống (sinh trưởng, phát triển và sinh sản) của các sinh vật và nhiều loài virus. Đây là từ viết tắt thuật ngữ tiếng Anh deoxyribonucleic acid, theo tiếng Việt gọi là acid deoxyribonucleic.

DNA là một loại acid nucleic, cùng với protein, lipid và carbohydrat cao phân tử (polysaccha-ride) đều là những đại phân tử sinh học chính có vai trò quan trọng thiết yếu đối với mọi dạng sống được biết đến. Phần lớn các phân tử DNA được cấu tạo từ hai mạch polymer sinh học xoắn đều quanh một trục tưởng tượng tạo thành chuỗi xoắn kép. Mỗi một mạch có hai đầu, một đầu kết thúc bởi nhóm phosphate được gọi là đầu 5’ và một đầu kết thúc bởi nhóm hydroxyl (OH) được gọi là đầu 3’. Hai mạch DNA có cấu trúc đối song song: giả sử như hai mạch DNA nằm ngang và một mạch DNA có đầu 5’ ở bên trái và đầu 3’ ở bên phải thì mạch DNA còn lại sẽ có đầu 3’ ở bên trái và đầu 5’ ở bên phải.

Hai mạch DNA này còn được gọi là các polynucleotide vì thành phần của chúng bao gồm các đơn phân nucleotide. Mỗi nucleotide được cấu tạo từ một trong bốn loại nucleobase chứa nitơ - hoặc là xi-tô-zin (C), gu-a-nin (G), a-đê-nin (A), hay ti-min (T) - liên kết với đường deoxyribose và một nhóm phosphat.

Trong bài toán này, ta biểu diễn mỗi mạch DNA bằng một xâu kí tự biểu diễn các nucleotide theo thứ tự từ đầu 5’ đến đầu 3’. Những nucleotide nằm đối xứng với nhau ở hai mạch DNA liên kết với nhau theo nguyên tắc bổ sung (A liên kết với T, và C liên kết với G) thông qua các mối liên kết hydro để tạo nên chuỗi DNA mạch kép.

Ví dụ: Nếu hai mạch DNA nằm ngang và một mạch có các nucleotide theo thứ tự từ trái sang phải là ATCGGCTA thì mạch DNA còn lại có các nucleotide theo thứ tự từ trái sang phải là TAGCCGAT.

Cho biết xâu kí tự biểu diễn một mạch DNA, hãy tìm xâu kí tự biểu diễn mạch còn lại của DNA

Gồm một dòng duy nhất chứa một xâu biểu diễn mạch DNA được cho gồm nhiều nhất ít nhất 1 và nhiều nhất 10^6 kí tự. Chỉ có các kí tự A, T, G, C được sử dụng

Gồm một dòng duy nhất chứa một xâu biểu diễn mạch DNA ứng với mạch DNA được cho.