# A Multi-Agent Conversational Recommender System

Jiabao Fang<EMAIL_ADDRESS>Shandong UniversityChina ,  Shen Gao
<EMAIL_ADDRESS>Shandong UniversityChina ,  Pengjie Ren
<EMAIL_ADDRESS>Shandong UniversityChina ,  Xiuying Chen
<EMAIL_ADDRESS>KAUSTKingdom of Saudi Arabia ,  Suzan Verberne
<EMAIL_ADDRESS>Leiden UniversityNetherland and  Zhaochun Ren
<EMAIL_ADDRESS>Leiden UniversityNetherland

(2024)

###### Abstract.

Due to strong capabilities in conducting fluent, multi-turn conversations with
users, Large Language Models (LLMs) have the potential to further improve the
performance of Conversational Recommender System (CRS). Unlike the aimless
chit-chat that LLM excels at, CRS has a clear target. So it is imperative to
control the dialogue flow in the LLM to successfully recommend appropriate
items to the users. Furthermore, user feedback in CRS can assist the system in
better modeling user preferences, which has been ignored by existing studies.
However, simply prompting LLM to conduct conversational recommendation cannot
address the above two key challenges.

In this paper, we propose Multi-Agent Conversational Recommender System
(MACRS) which contains two essential modules. First, we design a multi-agent
act planning framework, which can control the dialogue flow based on four LLM-
based agents. This cooperative multi-agent framework will generate various
candidate responses based on different dialogue acts and then choose the most
appropriate response as the system response, which can help MACRS plan
suitable dialogue acts. Second, we propose a user feedback-aware reflection
mechanism which leverages user feedback to reason errors made in previous
turns to adjust the dialogue act planning, and higher-level user information
from implicit semantics. We conduct extensive experiments based on user
simulator to demonstrate the effectiveness of MACRS in recommendation and user
preferences collection. Experimental results illustrate that MACRS
demonstrates an improvement in user interaction experience compared to
directly using LLMs.

Conversational recommendation, Large language models, Multi-agent, In-context
learning

††journalyear: 2024††copyright: rightsretained††conference: Proceedings of the
47th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 14–18, 2024; Washington D.C., USA††booktitle:
Proceedings of the 47th International ACM SIGIR Conference on Research and
Development in Information Retrieval (SIGIR ’24), July 14–18, 2024, Washington
D.C., USA††ccs: Information systems Recommender system††ccs: Information
systems Users and interactive retrieval

##  1\. Introduction

Unlike traditional recommender systems which solely rely on users’ historical
behaviors, conversational recommender system (CRS) engages in natural language
interactions with the users, allowing the users to better express their needs
(Jannach et al., 2021). Existing CRS frameworks are generally categorized into
two streams:  (1) The attribute-based CRS learns about user preferences by
asking questions about the item attributes and generate responses based on the
template. And the users only need to reply “yes/no” to the questions (Lei et
al., 2020; Xu et al., 2021). This approach lacks flexibility as users cannot
actively pose questions to the system, while the system can only reply through
human-annotated templates.  (2) The generation-based CRS focuses on generating
human-like responses, where users can express their intention without
limitation (Zhou et al., 2020a; Wang et al., 2022b; Ren et al., 2022; Zhang et
al., 2023). Most previous generation-based methods are based on either pre-
defined knowledge-graphs or smaller-scale generative models, which result in
poor generalizability and infeasibility in real-world scenarios.

Due to powerful language generation ability and the extensive parameterized
knowledge embedded in Large Language Models (LLMs), CRS with an LLM base has
recently received more and more attention (Friedman et al., 2023). Existing
CRS with LLMs generally follows two paradigms: (1) LLM with external RecSys:
In these methods, the LLM is only used for response generation while an
external recommender system is employed to recommend as an individual module
(Gao et al., 2023; Feng et al., 2023; Liu et al., 2023). (2) LLM-only: The LLM
in these methods not only facilitates conversations but also directly
generates recommendation results given user preferences (He et al., 2023; Wang
et al., 2023b). However, in recommendation and dialogue tasks, the LLM
integrated with an external RecSys CRS relies on distinct modules (_a.k.a.,_
recommendation module and dialogue module). Unfortunately, a majority of
current approaches overlook the exchange of user information between these
modules, consequently having an information gap between them. (Wang et al.,
2022b, a). In contrast, LLM-only CRS can share useful information between the
recommendation task and the dialogue task.

LLM-only CRS needs to fulfill both the recommendation task and the dialogue
task, thus it typically contains various dialogue acts: (1) An asking act that
can actively elicit user preferences; (2) A recommending act that can provide
items to users in natural language form; (3) A chit-chatting act that can
attract user interest and guide the topic of the conversation. Since a
conversational recommendation generally has a clearly defined target – the
goal is to recommend a specific item to a user – an engaging CRS with LLM
should be able to control the dialogue flow, meaning choose the proper
dialogue act at each turn. For example, when user preferences are ambiguous,
the CRS can elicit user preferences through the asking act. And the CRS can
utilize the chit-chatting act to explore various topics and maintain an
engaging conversation. However, previous work shows that the ability of the
LLM to control the target-directed dialogue flow remains limited (Hong et al.,
2023a). For that reason, simply prompting an LLM as a CRS can lead to
unreasonable dialogue flows. For some complex tasks that a single LLM-based
agent may struggle to accomplish, researchers propose breaking them down into
multiple simpler sub-tasks (Qian et al., 2023; Qiao et al., 2024) and then
having multiple LLM-based agents collaborate to jointly complete the complex
task. Similarly, CRS is also a type of complex task involving various
intricate dialogue acts. Inspired by these multi-agent approaches (Qian et
al., 2023; Qiao et al., 2024; Hong et al., 2023b), we propose to employ a
multi-agent framework on the CRS. However, designing the architecture of these
agents, defining their interactions, and collaborative methods to enhance the
performance of the CRS remains challenging.

Moreover, the characteristic of CRS is that users and the system can engage in
multi-turn interactions. During this process, users can provide their feedback
according to the system responses. Users can actively clarify their
preferences in their feedback. And this feedback also encompasses their
satisfaction towards the recommended items. Therefore, this informative
feedback not only allows the system to obtain more user information but also
reflects the reason why the recommendation failed before. We believe this
feedback can be used to dynamically optimize the system during the
interaction, but this aspect has been overlooked in previous research.

Figure 1. Example of modeling a Conversational Recommendation System (CRS)
using a multi-agent framework. The right side shows a dialogue between CRS and
user, while the left side depicts the internal framework of MACRS. The
responder agent and planner agent collaboratively generate appropriate
responses, while the reflection mechanism provides feedback and refined
guidance to these agents, optimizing their responses to better satisfy user
needs.

To address the above issues, we propose Multi-Agent Conversational Recommender
System (MACRS), an LLM-only CRS that can efficiently plan and dynamically
refine its dialogue and recommendations. MACRS comprises two essential modules
(Figure 1). The first is multi-agent act planning, a cooperative LLM-based
multi-agent framework which includes three responder agents and one planner
agent. In order to build an engaging dialogue flow, this framework will plan
the dialogue acts for each turn. Each responder agent in the framework is
responsible for performing a dialogue act and generating a candidate response
based on its dialogue act. After collecting various candidate responses, the
planner agent will comprehensively consider and select the most appropriate
response as the system response. The second module is user feedback-aware
reflection, a dynamic optimization mechanism based on the LLM. This mechanism
leverages the user utterances as feedback to adjust the responder agents and
the planner agent. The user feedback-aware reflection contains two levels. As
user feedback in each interaction holds significant information about user
preferences, including browsing history and current demand, information-level
reflection becomes an essential aspect to consider. And the information-level
reflection will refine the user feedback to create higher-level information,
referred to as user profiles. These user profiles will help the responder
agents generate more personalized responses in subsequent interactions. On the
other hand, when the recommendation fails, the act plan of MACRS needs to be
adjusted in time according to the user feedback. Therefore, reflection will
also operate on the strategy-level, which will deduce the reasons for the
recommend failure and then provide suggestions and experiences to the agents.
Extensive experiments conducted on Movielens demonstrate the effectiveness of
MACRS in recommendation and user preferences collection.

Our contributions of this work are as follows:  (i) We propose MACRS, an LLM-
only CRS that focuses on controlling the dialogue flow for multi-turn
interactions.  (ii) We design a multi-agent act planning framework, including
three responder agents and one planner agent. MACRS completes dialogue act
planning by guiding these agents to collaborate.  (iii) We design a user
feedback-aware reflection mechanism that leverages the user feedback to
dynamically optimize the agent’s response from the information-level and
strategy-level.  (iv) Experimental results based on user simulator illustrate
the advantage of MACRS in recommendation accuracy and efficiency of user
preferences collection.

##  2\. Related Work

###  2.1. LLM-based Autonomous Agents

Autonomous agents are considered to be a promising step towards artificial
general intelligence (AGI), which can complete tasks through self-directed
planning and actions (Zhou et al., 2023; Xi et al., 2023). Meanwhile, LLMs
have become powerful and fluent chatbots with convincing results in many topic
domains (Zhao et al., 2023; Min et al., 2023; Hadi et al., 2023). Therefore,
there are many attempts to use the LLM as central controllers to construct
autonomous agents and thus obtain human-like decision-making capabilities
(Wang et al., 2023a; Park et al., 2023), which are also called LLM-based
agents. For example, Gur et al. (2023) propose an LLM-based agent that can
complete user instructions on real websites by combining canonical web actions
in a program space. Schick et al. (2023) propose an LLM-based agent that can
teach itself to use external tools via simple APIs.

Recently, a number of researchers have started to explore LLM-based multi-
agent systems, which enable the solution of more complex problems. For
example, Hong et al. (2023b) propose to incorporate efficient human workflows
as a meta programming approach into LLM-based multi-agent collaboration. In
the task of multi-robot cooperation, Mandi et al. (2023) design multiple LLM-
based agents to perform high-level communication and low-level path planning
for different robots. To the best of our knowledge, our study is the first to
propose an LLM-based multi-agent system for conversation recommendation.

###  2.2. Conversational Recommender Systems

Conversational Recommender Systems (CRS) aim to recommend personalized items
to users through interactive conversations (Zhou et al., 2020b). Conventional
CRS can be broadly divided into two categories: The first category is
attribute-based methods, in which the system clarifies user preferences by
asking attribute-related questions, and users respond with “yes/no” to the
questions. These methods focus on when and what to ask before deciding about
the item(s) to be recommended (Lei et al., 2020; Ren et al., 2021). For
example, (Lei et al., 2020) model conversational recommendation as a path
reasoning problem on a user-item-attribute graph. However, due to the
restricted communication between the system and the user, the attribute-based
methods lack flexibility. The second category is generation-based methods, in
which both users and the system can communicate using free-form natural
language. Most existing generation-based CRS rely on a knowledge graph for
reasoning (Zhou et al., 2020a; Chen et al., 2019). Furthermore, in order to
generate more human-like responses, some prior work uses smaller-scale
generative language models (e.g. DialoGPT based on GPT-2) as generators (Wang
et al., 2022a, b). But due to the limited generalization ability of knowledge
graphs and these smaller language models, previous generation-based CRS lack
practicality in real-world scenarios.

Due to the success of LLMs, many researchers have started incorporating it
into CRS. With its powerful natural language generation capabilities and an
implicit knowledge base, LLMs have significant potential in conversational
recommendation. Existing LLM-based CRS can be broadly divided into two
categories: (1) Liu et al. (2023); Gao et al. (2023); Feng et al. (2023)
incorporate the LLM with additional recommendation models. (2) He et al.
(2023); Wang et al. (2023b) use the LLM itself as the CRS. Although directly
using LLM for CRS can share useful knowledge between different tasks, it’s
difficult for the LLM to control the goal-directed dialogue flow. To the best
of our knowledge, our study is the first to propose a controlling dialogue
flow for the CRS completely constructed on LLM.

##  3\. Methodology

###  3.1. Overview

Following previous CRS work (Wang et al., 2022b), the user initiates the
dialogue with the CRS by a natural language utterance to describe their
demand. Then the CRS will respond to the user with an utterance that may ask
the user for more details or chit-chat with the user. After several turns of
dialogue to elicit clear user preferences, the CRS tries to recommend an item
to the user. When the user accepts the recommended item given by our CRS, we
call this dialogue session a successful sample, and then the user will
terminate the dialogue. In our task setting, we also define a maximum turn
threshold. When the dialogue reaches the maximum turn threshold, but the CRS
still does not provide product suggestions that the user is satisfied with, we
have a fallback strategy in which the CRS will give a recommendation list
containing 10 items before terminating the dialogue. Thus, if the CRS cannot
recommend an item that satisfies the user demand before reaching the maximum
turn threshold and going to the fallback strategy, this dialogue session is
referred to as an unsuccessful sample.

In this paper, to tackle this task, we introduce Multi-Agent Conversational
Recommender System (MACRS), an LLM-only CRS that can flexibly control the
dialogue flow and dynamically optimize the system action with user feedback.
MACRS consists of two modules. The first is the multi-agent act planning, a
cooperative multi-agent framework that integrates four LLM-based agents for
planning the multiple dialogue acts, as shown in § 3.2. Secondly, we propose a
user feedback-aware reflection mechanism, which can leverage the user feedback
to adjust the agents in MACRS, as shown in § 3.3. Figure 2 shows an overview
of MACRS.

###  3.2. Multi-Agent Act Planning

Figure 2. The overview of MACRS, which contains two modules: multi-agent act
planning and user feedback-aware reflection. The multi-agent act planning
module generates the response according to the user feedback. The user
feedback-aware reflection module summarizes the high-level user profile and
dialogue strategy suggestions which helps the responder agents to optimize
their response.

In order to achieve an engaging interaction, a CRS generally can use various
dialogue acts. Therefore, it is essential for the CRS to effectively plan the
dialogue flow by selecting suitable dialogue acts for each turn. The dialogue
flow planning plays a crucial role in enhancing the efficiency and
attractiveness of the CRS. To accomplish this complex planning task, we design
a multi-agent act planning framework that contains multiple responder agents
and one planner agent. The responder agents are responsible for generating
various candidate responses based on different dialogue acts. The planner
agent is responsible for devising a dialogue act plan that can develop an
appropriate and fluent dialogue flow.

####  3.2.1. Responder Agent

An engaging CRS should incorporate a variety of dialogue acts during multi-
turn interactions. Therefore, we designed three types of responder agents to
implement various dialogue acts including asking, chit-chatting, and
recommending. The asking responder agent $\pi^{r}_{ask}$ aims at asking user
questions to elicit their preferences. The recommending responder agent
$\pi^{r}_{rec}$ shows an item to the user that it predicts the user may be
interested in. In order to improve the user experience when interacting with
CRS, we cannot repeatedly recommend and ask questions but need to have timely
chit-chats with users about the items using the chit-chatting responder agent
$\pi^{r}_{chat}$. These chit-chats can enhance the user’s interest in
interacting with CRS, and can also better understand user preferences, like a
real salesperson. These responder agents share the same agent architecture
which is composed of three modules: memory module, profiling module, and
action module. All these modules are defined through in-context learning with
instructions in the LLM prompt.

The Memory module contains the dialogue history $D_{h}$, the user profile
$U_{p}$ (as mentioned in § 3.3.1) and strategy-level suggestions $S$ (as
mentioned in § 3.3.2). The dialogue history $D_{h}$ comprises the user
utterances and system responses from previous turns. The user profile $U_{p}$
contains the user’s current demand and browsing history. The strategy-level
suggestions $S$ are the guidance for the responder agents in the current turn
and are learned from user feedback in previous turns.

The Profiling module refers to the instructions and indicates the role of the
responder agent. Obviously, responder agents for different dialogue acts need
to complete different task objectives, we separately design the instructions
for each of the agents:

(1) Instruction $I_{ask}$ for asking responder agent $\pi^{r}_{ask}$:

You should elicit user preferences by asking questions.

(2) Instruction $I_{chat}$ for chit-chatting agent $\pi^{r}_{chat}$:

You should chit-chat with the user to learn about their preferences. You can
express your admiration for certain item elements to guide the conversation
towards them, thereby gaining insights into the user preferences regarding
those elements.

(3) Instruction $I_{rec}$ for recommending agent $\pi^{r}_{rec}$:

You should recommend an item to user and generate an engaging description
about the item.

The Action module generates three candidate responses $R_{ask}$, $R_{chat}$
and $R_{rec}$ based on the memory and profile:

(1)
$\begin{gathered}R_{*}=\pi_{r}^{*}(I_{*},D_{h},U_{p},S_{*}),\end{gathered}$

where $*$ indicates“ask”, “rec” or “chat” respectively.

####  3.2.2. Planner Agent

In order to control the dialogue flow, it is important to select the most
suitable response from the candidate responses $R_{ask},R_{chat},$ and
$R_{rec}$ as the system response $R_{s}$. To tackle this task, the planner
agent $\pi_{p}$ utilizes multi-step reasoning to select responses across
multiple dimensions, such as informativeness and engagement. For example, when
the available user preferences are insufficient, the planner agent reasons
which candidate response can potentially yield a higher user information gain.
Then the planner agent will select the candidate response $R_{ask}$ of the ask
responder agent as the final response to the user to gather more user
preferences. To achieve this goal, we propose a novel architecture of planner
agent $\pi_{p}$ which is composed of a memory module, a profiling module, and
a planning module:

The Memory module contains the dialogue history $D_{h}$, the dialogue act
history $A_{h}$, and corrective experiences $E$ (introduced in § 3.3.2). The
dialogue act history $A_{h}$ records the dialogue act selected by the planner
agent in previous dialogue turns. The corrective experiences $E$ are learned
from user feedback in past turns.

The Profiling module indicates both its role and the background knowledge.
Instruction $I_{plan}$ for the planner agent $\pi_{p}$:

Choose one of the candidate responses based on three different dialogue acts.
These three dialogue acts are: recommending, asking, and chit-chatting.

The Planning module performs multi-step reasoning based on its memory and its
profile to make an appropriate dialogue act selection.

$\bullet$ Step 1: Review past acts in the dialogue act history $A_{h}$ and
avoid the repetition of the same act across multiple turns.

$\bullet$ Step 2: Determine whether the available user preferences are
sufficient based on the dialogue history $D_{h}$. If so, the recommending act
is a suitable choice.

$\bullet$ Step 3: If the available user preferences are insufficient,
determine which candidate response is more appropriate or can yield greater
user information gain.

After multi-step reasoning, the planner agent $\pi_{p}$ will output a
selection, which in turn determines the final system response $R_{s}$:

(2)
$\begin{gathered}R_{s}=\pi_{p}(I_{plan},R_{ask},R_{rec},R_{chat},D_{h},A_{h},E).\end{gathered}$

###  3.3. User Feedback-aware Reflection

Figure 3. Overview of user feedback-aware reflection mechanism.

During the interactions with the CRS, the user provides the feedback utterance
$U_{f}$ to the system response. On the one hand, users will actively express
their preferences in the feedback by providing more detailed descriptions or
responding to questions. On the other hand, users will also implicitly convey
their satisfaction with the recommendations and occasionally clarify the
reasons behind their satisfaction. In order to leverage this valuable feedback
$U_{f}$ to dynamically optimize our agents, we propose a user feedback-aware
reflection mechanism that operates at two levels. Figure 3 provides a
illustration for the proposed mechanism. The first information-level
reflection $\pi_{\text{info\\_reflect}}$ infers user preferences from user
feedback and summarizes them as user profiles $U_{p}$. The second strategy-
level reflection $\pi_{\text{stra\\_reflect}}$ adjusts the dialogue act plan
by generating suggestions $S$ and corrective experiences $E$ based on the
user’s clarifications to the recommendations. Again, all strategies are
implemented through in-context learning.

####  3.3.1. Information-level Reflection

We propose the information-level reflection mechanism
$\pi_{\text{info\\_reflect}}$ which summarizes user feedback to higher-level
information, referred as to user profiles $U_{p}$. The user profiles $U_{p}$
contain current user demand and browsing history: (1) The current user demand
is stored in a dictionary format, comprising multiple key-value pairs. Each
key-value pair represents an item attribute that the user is interested in.
And these key-value pairs are extracted from the user feedback by using this
mechanism $\pi_{\text{info\\_reflect}}$. (2) The browsing history includes
multiple items mentioned by the user, which are extracted from the user
feedback $U_{f}$. It helps the responder agents effectively capture user
preferences and also reminds them to avoid generating duplicate content.

In dialogue turn $t$, the information-level reflection mechanism
$\pi_{\text{info\\_reflect}}$ generates the user profile $U^{t}_{p}$ based on
the user profile $U^{t-1}_{p}$ from the previous turn $t-1$, system response
$R_{s}^{t-1}$ and user feedback $U^{t-1}_{f}$:

(3) $\displaystyle
U^{t}_{p}=\pi_{\text{info\\_reflect}}(U^{t-1}_{p},R_{s}^{t-1},U^{t-1}_{f}),$

where the information-level reflection mechanism $\pi_{\text{info\\_reflect}}$
is implemented by prompting an LLM-based agent using the following
instructions:

Please infer user preferences based on the conversation. And combine them with
the past preferences to summarize a more complete user preferences.

After information-level reflection, the user profiles $U_{p}$ will be
transmitted to the memory module of each responder agent.

####  3.3.2. Strategy-level Reflection

User feedback implicitly indicates their satisfaction with the
recommendations. When a user is dissatisfied, it indicates that MACRS has
issues in controlling the dialogue flow in the past few turns. So we propose
the strategy-level reflection mechanism $\pi_{\text{stra\\_reflect}}$ which
mainly focuses on dynamically adjusting the dialogue act plan when
recommendation fails. This mechanism $\pi_{\text{stra\\_reflect}}$ is
implemented by prompting an LLM-based agent.

Our proposed strategy-level reflection mechanism $\pi_{\text{stra\\_reflect}}$
will first collect multi-turn trajectory $M$, which consists of three parts:
user profile $U_{p}$ (as mentioned in § 3.3.1), system response $R_{s}$ and
user feedback $U_{f}$. Then the trajectory $M$ from turn $i$ to turn $t$ can
be represented as:

(4) $\displaystyle
M^{i}_{t}=\left((U_{p}^{i},R_{s}^{i},U_{f}^{i}),\dots,(U_{p}^{t},R_{s}^{t},U_{f}^{t})\right).$

When the system provide a failed recommendation in turn $t$, this mechanism
$\pi_{\text{stra\\_reflect}}$ reflects on the trajectory from turn $i$ to turn
$t$, where turn $i$ refers to the turn immediately following the last
recommendation failure. If turn $t$ is the first recommendation failure, then
$i=1$. To reflect the mistakes the system has made in the trajectory
$M^{i}_{t}$, strategy-level reflection generates an error summary $E_{s}$:

(5) $\displaystyle E_{s}=\pi_{\text{stra\\_reflect}}(M^{i}_{t}),$

where the error summary $E_{s}$ is a descriptive natural language
representation that encompasses errors made by both the responder agents and
the planner agent. The instruction of error summary $E_{s}$ generation is as
follow:

Based on your past action trajectory, your goal is to write a few sentences to
explain why your recommendation failed as indicated by the user utterance.

To avoid repeating the same mistake, the strategy-level reflection mechanism
$\pi_{\text{stra\\_reflect}}$ adjusts the agents by generating an error
summary $E_{s}$. There are two main parts in the error summary $E_{s}$: the
strategy-level suggestions $S$ and the corrective experiences $E$. The
strategy-level suggestions $S$ indicate the dialogue strategies that each
agent needs to complete in the next dialogue turn and will be used in the
memory module of each responder agent (_e.g.,_ ask, rec and chat). For
example, a user rejects the recommendation and responds with “I want to watch
more classic films”, which is vague. The mechanism can suggest the asking
responder agent $\pi^{r}_{ask}$ to elicit specific preferences regarding the
release time of films. Secondly, the strategy-level reflection summarizes the
suggestions $S$ into corrective experiences $E$ and stores them in the memory
module of the planner agent. These experiences will influence its subsequent
planning process. The instruction of strategy-level suggestions $S$ and
corrective experiences $E$ is as follow:

You need to generate several suggestions to “Recommending Agent”, “Asking
Agent” and “Chit-chatting Agent”. Then you should report the suggestions to
the “Planning Agent” as experiences.

Table 1. Conversational recommendation performance comparison. $\ddagger$ indicates significant improvement over ChatGPT with $p\leq 0.01$ according to a Student’s t test. Method | Success Rate ($\uparrow$) | Average Turns ($\downarrow$) | Hit Ratio@5 ($\uparrow$) | Hit Ratio@10 ($\uparrow$)
---|---|---|---|---
_Traditional CRS Baselines_ |
KBRD (Chen et al., 2019) | 0.00 | 6.0 | 0.00 | 0.01
BARCOR (Wang et al., 2022a) | 0.03 | 5.9 | 0.03 | 0.07
_LLM-based CRS Baselines_ |
Llama2 | 0.42 | 4.34 | 0.47 | 0.51
ChatGPT | 0.39 | 4.24 | 0.44 | 0.51
_Our Proposed Method_ |
MACRS-L | 0.48 | 4.49 | 0.55 | 0.60
MACRS-C | 0.61‡ | 4.19† | 0.77‡ | 0.80‡
MACRS-C w/o IR | 0.53 | 4.42 | 0.72 | 0.77
MACRS-C w/o SR | 0.52 | 4.42 | 0.67 | 0.73
MACRS-C w/o SR+IR | 0.51 | 4.40 | 0.64 | 0.66

##  4\. Experimental Setup

We evaluate the effectiveness of MACRS in both user preferences collection and
recommendation.

###  4.1. User Simulator

To evaluate the performance of MACRS in multi-turn interactions, we develop a
LLM-based user simulator inspired by (Wang et al., 2023b). We construct the
user simulator based on ChatGPT and define the preference of the user
simulator using the browsing history and target item information. In prior
work (Wang et al., 2023b), the target item is directly given to the user
simulator, which leads to the simulator describing the target item in
excessive detail. We argue that this setting does not align with real-life
scenarios, in which users usually have fuzzy preferences (Li et al., 2023). In
order to create a more realistic and natural user simulator, we use ChatGPT to
summarize the information of the target item into multiple keywords, referred
to as target item profiles. Then we replace the name of target items with the
target item profiles and request the user simulator to avoid overly direct
descriptions. The instruction prompt of the user simulator is:

You are a user chatting with an assistant for movie recommendation in turn.
Your browsing history can reflect your past preferences. And you will seek
recommendations from the assistant based on the [target movie information].

where the [target movie information] represents the target item profiles.

###  4.2. Implementation Details

In our experiments, all MACRS-C variants and the ChatGPT baseline use the
gpt-3.5-turbo-0613 version, and the MACRS-L variant and Llama2 baseline use
the Llama-2-70b-chat-hf version which is open-sourced. We use the temperature
0.0 in our experiments. And we update the memory modules of agents in MACRS
after each turn, meaning that only the suggestions and experiences from the
previous turn are retained. For a fair comparison, we maintain consistency in
the item summary and user utterance of the first turn across all experiments.
We set the maximum threshold of turns as 5. And when the CRS is still
unsuccessful in the 5th turn, it will directly generate a recommendation list
in the 6th turn.

###  4.3. Evaluation Metrics

To quantitatively measure the performance of MACRS, we design three automatic
metrics:

(1) Success Rate: To evaluate the overall efficiency of CRSs, we calculate the
rate of successful samples (definition can be found at § 3.1) over all the
test sets:

(6) $\displaystyle\text{Success\\_Rate}=\frac{N_{su}}{N},$

where $N$ is the number of test set samples, and $N_{su}$ is the number of
successful samples.

(2) Hit Ratio@K: Since our method has a fallback strategy of recommending an
item list at the end of the conversation, we also include this part of the
recommendation results in the final recommendation effect evaluation. This
allows us to evaluate the efficiency of information gathering. We calculate
the number of top-$K$ hits in recommendation lists, where $K=5,10$. We also
add the number of successful samples in the final calculation:

(7)
$\displaystyle\text{Hit\\_Ratio}=\frac{\sum_{i=1}^{N_{un}}hit(i)+N_{su}}{N},$

where $N_{un}$ is the number of unsuccessful samples (definition can be found
at § 3.1). And when the target item appears in the recommendation list,
$hit(i)=1$. Otherwise, $hit(i)=0$.

(3) Average Turns: To evaluate the recommendation efficiency of the CRS, we
calculate the average number of turns in the conversation:

(8) $\displaystyle\text{Average\\_Turns}=\frac{\sum_{i=1}^{N}NT_{i}}{N},$

where $NT_{i}$ is the number of turns in sample $i$.

###  4.4. Dataset

We conduct our experiments on the MovieLens (Harper and Konstan, 2015) which
is a benchmark dataset for movie recommendation. It contains 162,541 users,
62,423 movies and 25,000,095 ratings. To construct the user simulator, we
truncate the interaction sequence to 20 items, utilizing them to create the
browsing history. The 21st item is then used as the prediction target item.
Then we filter the browsing history and only retain the items that belong to
the same category as the target item. We randomly select 100 samples and
ensured that the length of their browsing history is not less than 5.

###  4.5. Comparison Methods

To evaluate the effectiveness of MACRS, we compare it to four strong CRS
baseline methods:

(1) KBRD (Chen et al., 2019) contains a recommendation module and a
Transformer-based dialogue module. It leverages an external knowledge graph to
enhance the semantics of entities mentioned in the dialogue history.

(2) BARCOR (Wang et al., 2022a) uses the bidirectional encoder of BART (Lewis
et al., 2020) as the recommendation module and its auto-regressive decoder as
the dialogue module.

(3) ChatGPT 111https://chat.openai.com/ is a closed-source LLM from OpenAI. We
use the version gpt-3.5-turbo-0613. We construct a powerful single-agent CRS
based on it using the same prompt as our model.

(4) Llama2 222https://huggingface.co/meta-llama/Llama-2-70b-chat-hf is an
open-source LLM that has been trained using both supervised fine-tuning and
reinforcement learning with human feedback (Touvron et al., 2023). We use the
Llama2 model with 70 billion parameters. We construct it as a single-agent
method to plan the dialogue flow and compare it with our multi-agent
framework.

We propose two variants of MACRS: MACRS-C and MACRS-L, which use the ChatGPT
and Llama2 as the backbone respectively. To demonstrate the effectiveness of
each module in our proposed MACRS framework, we employ several ablation models
in our experiments:

(1) MACRS w/o SR: We remove the strategy reflection (SR) module in MACRS,
which can verify the effectiveness of the reflection on the dialogue strategy.

(2) MACRS w/o IR: We remove the information reflection (IR) module in our user
feedback-aware reflection which generates the user profile, which verifies the
effectiveness of high-level user preference information.

(3) MACRS w/o SR+IR: We remove both of the strategy reflection and information
reflection (SR+IR) to verify the effectiveness of the reflection mechanism in
MACRS.

All the ablation studies are conducted on MACRS-C.

Figure 4. The ratio of different dialogue acts chosen in each turn of
dialogue. The diversity in dialogue act selection of our proposed MACRS is
remarkably enhanced compared to the corresponding backbone model, and it
enhances the user experience.

##  5\. Experimental results

###  5.1. Main Results

Table 1 shows the performance of our proposed MACRS and baselines in terms of
four metrics. We see that the LLM-only CRSs (_e.g.,_ ChatGPT and Llama2)
demonstrate superior performance compared to traditional CRS methods (_e.g.,_
BARCOR and KBRD). On the one hand, this is because BARCOR and KBRD rely on
knowledge graphs and face limitations in successfully recommending items that
are not present in the knowledge graph. On the other hand, they rely on
smaller-scale generative models that exhibit weaker reasoning and natural
language understanding capabilities than LLMs.

We also find that MACRS-C outperforms its backbone LLM ChatGPT in terms of all
metrics. This suggests that with the help of our proposed MACRS framework, the
LLM-only CRS can improve in both user preference gathering and recommendation
accuracy. Although the MACRS-L outperforms the Llama2 in terms of all the
recommendation accuracy metrics (_e.g.,_ Success Rate and Hit Ratio), we
observe that MACRS-L has a slightly higher average number of turns compared to
the Llama2. We suspect that this is because MACRS method recommends more
cautiously, which gives it an advantage in both success rate and
recommendation accuracy. In contrast, the single-agent methods (_e.g.,_
ChatGPT and Llama2) tend to directly and frequently recommend items to the
user, and this behavior will lead to higher efficiency. However, it is obvious
that such frequent recommendations not only risk user dissatisfaction but are
also inefficient for capturing user preferences. A more detailed analysis can
be found in § 5.3.1.

Moreover, while Llama2 exhibits enhanced performance compared to ChatGPT as a
single agent, MACRS-L lags behind MACRS-C across all metrics. We speculate the
reason for this phenomenon is the Llama2’s weaker ability to follow the
complex instructions than ChatGPT, which results in suboptimal outcomes within
our proposed multi-agent framework.

Figure 5. Cumulative number of successful samples for each dialogue turn.

###  5.2. Ablation Study

To evaluate the effectiveness of each module in MACRS, we conduct ablation
studies with three variant models: (1) only using the multi-agent act planning
without both levels of reflection (_a.k.a.,_ MACRS w/o SR+IR); (2) only using
the information-level user feedback-aware reflection (_a.k.a.,_ MACRS w/o SR);
(3) only using the strategy-level user feedback-aware reflection (_a.k.a.,_
MACRS w/o IR). The performance of ablation models is shown in Table 1, and we
can find that all of the ablation models perform less promising than the best
model MACRS-C, which demonstrates the preeminence of each module in MACRS. We
can also find that the MACRS w/o SR performs worse than the MACRS w/o IR,
which demonstrates that strategy-level suggestion and corrective experience
are more important of the CRS.

Figure 6. Performance of different models with respect to the popularity level
of item.

###  5.3. Discussion

####  5.3.1. Analysis of different dialogue acts ratio

In order to compare the differences in dialogue act planning between MACRS and
single-agent CRS, we conduct a statistical analysis comparing the dialogue act
selection in each turn. As shown in Figure 4, our method has better diversity
in choosing dialogue acts than other baseline models. Other baseline methods
(_e.g.,_ ChatGPT) tend to directly recommend or ask the user’s preference in
each round of dialogue. This will lead to a poor user experience with the CRS,
as users are often impatient with being constantly recommended boring items.
In addition, Figure 4 shows that our method tends to ask the user’s preference
in the first round of dialogue, make a trial recommendation in the second
round, and then adjust the dialogue act based on the previous interaction in
the subsequent turns. MACRS also inserts a small amount of chit-chat acts at
appropriate times during the dialogue to enhance the user experience and
increase the appeal of the CRS to users. We expect this conversational
behavior of the CRS to be more natural and human-like and will therefore be
preferred by users.

We also conduct a statistical analysis on the number of cumulative successful
samples at each turn $T$, where $T=\\{1,2,3,4,5\\}$. As shown in Figure 5,
since MACRS tends to ask about user preferences in the initial turns, while
ChatGPT tends to directly make recommendations, ChatGPT has more accumulative
successful examples when $T=\\{1,2\\}$. However, as ChatGPT lacks explicit
modeling of user preferences, the cumulative count of successfully recommended
samples gradually decreases in later interaction turns. This experiment also
demonstrates the importance of actively obtaining user preference information.

####  5.3.2. Analysis of the influence of item popularity

Popularity bias, a well-known phenomenon in recommendation systems
(Abdollahpouri et al., 2020; Wei et al., 2021; Lin et al., 2022), can lead to
reduced user satisfaction when the target item is unpopular. We conducted a
statistical analysis to examine the performance differences of MACRS under
varying levels of target item popularity and we compared it with the LLM-based
CRS baseline ChatGPT. In the experiments, we quantify the popularity of an
item based on the number of interactions and categorize it into five levels:
top 10%, top 10%-20%, top 20%-30%, top 30%-50%, and bottom 50%. For each
level, we randomly selected 20 samples.

The results are shown in Figure 6. The experimental results indicate that
MACRS outperforms the baseline in all popularity levels of items. Moreover,
MACRS demonstrates remarkable recommendation accuracy when dealing with
challenging samples characterized by lower item popularity. This can be
attributed to the effective dialogue act planning in MACRS, which enables it
to gather more comprehensive user preference information.

On the contrary, the single-agent method ChatGPT tends to make more frequent
recommending acts, which can help improve the overall efficiency and reduce
the number of average number of dialogue turns on the test set. However, this
approach has a negative effect on low-popularity items, which can make it
difficult for these CRS methods to recommend low-popularity items to users, as
they lack a detailed understanding of user preferences.

Table 2. The influence of strategy-level suggestions. Response w/ Suggestions Wins | Tie |  Response w/o Suggestions Wins
---|---|---
$45.4\%$ | $33.0\%$ | $21.6\%$

####  5.3.3. The influence of strategy-level suggestions

In order to evaluate the strategy-level suggestions generated by the strategy-
level reflection mechanism, we compared the responses with suggestions and the
responses without suggestions. We use ChatGPT 333https://chat.openai.com/ as
the evaluator. We instruct the evaluator to compare the responses according to
multiple criteria including (1) recommendation accuracy, (2) user information
gain, (3) conciseness, and (4) engagement. Then the evaluator selects the
superior response based on these criteria. The result shown in Table 2
indicates that the strategy-level suggestions can enhance the quality of the
responses.

###  5.4. Case Study

In Figure 7, we show an example of the dialogue between the user and MACRS and
between the user and the baseline method. The text in green indicates whether
the user accepts the CRS recommended item, the text in red represents dialogue
acts that are beneficial for recommendation. From this case, we can find that
the ChatGPT fails to recommend the proper item to the user since it does not
further explore user preferences in the 2nd turn. When the user chats with
MACRS, MACRS accurately identifies user implicit preferences for directors
when the user replies with “the director of it did not meet my expectations”.
It is essential for the CRS to detect implicit preferences from user feedback
and further explore them to uncover more explicit preferences. This
observation demonstrates that our proposed user feedback-aware reflection
module can help the CRS adjust the dialogue act plan based on user feedback.

Figure 7. Case study for a conversational recommendation.

##  6\. Conclusion

In this paper, we introduced Multi-Agent Conversational Recommender System
(MACRS), an LLM-only multi-agent Conversational Recommender System (CRS) that
leverages several different agents to tackle the dialogue flow planning and
integrate the user feedback to optimize the dialogue planning dynamically. We
first propose a novel multi-agent dialogue planning module to separately model
each dialogue act using LLM-based responder agents and schedule these
responder agents according to the dialogue strategy and user feedback by using
the planner agent. Then we propose a user feedback-aware reflection module
that conducts the reflection on both information-level and strategy-level to
produce high-level user preference descriptions and dialogue strategy
suggestions for the subsequent dialogue. These two modules can collaborate to
optimize the dialogue flow and increase the user experience and recommendation
accuracy. Experiments conducted on a benchmark CRS dataset demonstrate that
our proposed MACRS can boost the performance of recommendations significantly
and have a better and more engaging user experience than with the existing CRS
methods.

## References

  * (1)
  * Abdollahpouri et al. (2020) Himan Abdollahpouri, Masoud Mansoury, Robin Burke, and Bamshad Mobasher. 2020.  The connection between popularity bias, calibration, and fairness in recommendation. In _Proceedings of the 14th ACM Conference on Recommender Systems_. 726–731.
  * Chen et al. (2019) Qibin Chen, Junyang Lin, Yichang Zhang, Ming Ding, Yukuo Cen, Hongxia Yang, and Jie Tang. 2019.  Towards knowledge-based recommender dialog system.  _arXiv preprint arXiv:1908.05391_ (2019).
  * Feng et al. (2023) Yue Feng, Shuchang Liu, Zhenghai Xue, Qingpeng Cai, Lantao Hu, Peng Jiang, Kun Gai, and Fei Sun. 2023.  A Large Language Model Enhanced Conversational Recommender System.  _arXiv preprint arXiv:2308.06212_ (2023).
  * Friedman et al. (2023) Luke Friedman, Sameer Ahuja, David Allen, Terry Tan, Hakim Sidahmed, Changbo Long, Jun Xie, Gabriel Schubiner, Ajay Patel, Harsh Lara, et al. 2023\.  Leveraging Large Language Models in Conversational Recommender Systems.  _arXiv preprint arXiv:2305.07961_ (2023).
  * Gao et al. (2023) Yunfan Gao, Tao Sheng, Youlin Xiang, Yun Xiong, Haofen Wang, and Jiawei Zhang. 2023.  Chat-rec: Towards interactive and explainable llms-augmented recommender system.  _arXiv preprint arXiv:2303.14524_ (2023).
  * Gur et al. (2023) Izzeddin Gur, Hiroki Furuta, Austin Huang, Mustafa Safdari, Yutaka Matsuo, Douglas Eck, and Aleksandra Faust. 2023.  A real-world webagent with planning, long context understanding, and program synthesis.  _arXiv preprint arXiv:2307.12856_ (2023).
  * Hadi et al. (2023) Muhammad Usman Hadi, Rizwan Qureshi, Abbas Shah, Muhammad Irfan, Anas Zafar, Muhammad Bilal Shaikh, Naveed Akhtar, Jia Wu, Seyedali Mirjalili, et al. 2023\.  Large language models: a comprehensive survey of its applications, challenges, limitations, and future prospects.  _Authorea Preprints_ (2023).
  * Harper and Konstan (2015) F. Maxwell Harper and Joseph A. Konstan. 2015.  The MovieLens Datasets: History and Context.  _ACM Trans. Interact. Intell. Syst._ 5, 4, Article 19 (dec 2015), 19 pages.  https://doi.org/10.1145/2827872
  * He et al. (2023) Zhankui He, Zhouhang Xie, Rahul Jha, Harald Steck, Dawen Liang, Yesu Feng, Bodhisattwa Prasad Majumder, Nathan Kallus, and Julian McAuley. 2023.  Large language models as zero-shot conversational recommenders. In _Proceedings of the 32nd ACM international conference on information and knowledge management_. 720–730.
  * Hong et al. (2023a) Joey Hong, Sergey Levine, and Anca Dragan. 2023a.  Zero-Shot Goal-Directed Dialogue via RL on Imagined Conversations.  _arXiv preprint arXiv:2311.05584_ (2023).
  * Hong et al. (2023b) Sirui Hong, Xiawu Zheng, Jonathan Chen, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, et al. 2023b.  Metagpt: Meta programming for multi-agent collaborative framework.  _arXiv preprint arXiv:2308.00352_ (2023).
  * Jannach et al. (2021) Dietmar Jannach, Ahtsham Manzoor, Wanling Cai, and Li Chen. 2021.  A survey on conversational recommender systems.  _ACM Computing Surveys (CSUR)_ 54, 5 (2021), 1–36.
  * Lei et al. (2020) Wenqiang Lei, Gangyi Zhang, Xiangnan He, Yisong Miao, Xiang Wang, Liang Chen, and Tat-Seng Chua. 2020.  Interactive path reasoning on graph for conversational recommendation. In _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_. 2073–2083.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. 7871–7880.
  * Li et al. (2023) Belinda Z Li, Alex Tamkin, Noah Goodman, and Jacob Andreas. 2023.  Eliciting human preferences with language models.  _arXiv preprint arXiv:2310.11589_ (2023).
  * Lin et al. (2022) Allen Lin, Jianling Wang, Ziwei Zhu, and James Caverlee. 2022.  Quantifying and mitigating popularity bias in conversational recommender systems. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_. 1238–1247.
  * Liu et al. (2023) Yuanxing Liu, Wei-Nan Zhang, Yifan Chen, Yuchi Zhang, Haopeng Bai, Fan Feng, Hengbin Cui, Yongbin Li, and Wanxiang Che. 2023.  Conversational Recommender System and Large Language Model Are Made for Each Other in E-commerce Pre-sales Dialogue.  _arXiv preprint arXiv:2310.14626_ (2023).
  * Mandi et al. (2023) Zhao Mandi, Shreeya Jain, and Shuran Song. 2023.  Roco: Dialectic multi-robot collaboration with large language models.  _arXiv preprint arXiv:2307.04738_ (2023).
  * Min et al. (2023) Bonan Min, Hayley Ross, Elior Sulem, Amir Pouran Ben Veyseh, Thien Huu Nguyen, Oscar Sainz, Eneko Agirre, Ilana Heintz, and Dan Roth. 2023.  Recent advances in natural language processing via large pre-trained language models: A survey.  _Comput. Surveys_ 56, 2 (2023), 1–40.
  * Park et al. (2023) Joon Sung Park, Joseph O’Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein. 2023.  Generative agents: Interactive simulacra of human behavior. In _Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology_. 1–22.
  * Qian et al. (2023) Chen Qian, Xin Cong, Cheng Yang, Weize Chen, Yusheng Su, Juyuan Xu, Zhiyuan Liu, and Maosong Sun. 2023.  Communicative agents for software development.  _arXiv preprint arXiv:2307.07924_ (2023).
  * Qiao et al. (2024) Shuofei Qiao, Ningyu Zhang, Runnan Fang, Yujie Luo, Wangchunshu Zhou, Yuchen Eleanor Jiang, Chengfei Lv, and Huajun Chen. 2024.  AUTOACT: Automatic Agent Learning from Scratch via Self-Planning.  _arXiv preprint arXiv:2401.05268_ (2024).
  * Ren et al. (2021) Xuhui Ren, Hongzhi Yin, Tong Chen, Hao Wang, Zi Huang, and Kai Zheng. 2021.  Learning to ask appropriate questions in conversational recommendation. In _Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval_. 808–817.
  * Ren et al. (2022) Zhaochun Ren, Zhi Tian, Dongdong Li, Pengjie Ren, Liu Yang, Xin Xin, Huasheng Liang, Maarten de Rijke, and Zhumin Chen. 2022.  Variational Reasoning about User Preferences for Conversational Recommendation. In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 165–175.
  * Schick et al. (2023) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023.  Toolformer: Language models can teach themselves to use tools.  _arXiv preprint arXiv:2302.04761_ (2023).
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023\.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ (2023).
  * Wang et al. (2023a) Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. 2023a.  A survey on large language model based autonomous agents.  _arXiv preprint arXiv:2308.11432_ (2023).
  * Wang et al. (2022a) Ting-Chun Wang, Shang-Yu Su, and Yun-Nung Chen. 2022a.  BARCOR: Towards A Unified Framework for Conversational Recommendation Systems.  _arXiv preprint arXiv:2203.14257_ (2022).
  * Wang et al. (2023b) Xiaolei Wang, Xinyu Tang, Wayne Xin Zhao, Jingyuan Wang, and Ji-Rong Wen. 2023b.  Rethinking the Evaluation for Conversational Recommendation in the Era of Large Language Models.  _arXiv preprint arXiv:2305.13112_ (2023).
  * Wang et al. (2022b) Xiaolei Wang, Kun Zhou, Ji-Rong Wen, and Wayne Xin Zhao. 2022b.  Towards unified conversational recommender systems via knowledge-enhanced prompt learning. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 1929–1937.
  * Wei et al. (2021) Tianxin Wei, Fuli Feng, Jiawei Chen, Ziwei Wu, Jinfeng Yi, and Xiangnan He. 2021.  Model-agnostic counterfactual reasoning for eliminating popularity bias in recommender system. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 1791–1800.
  * Xi et al. (2023) Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al. 2023\.  The rise and potential of large language model based agents: A survey.  _arXiv preprint arXiv:2309.07864_ (2023).
  * Xu et al. (2021) Kerui Xu, Jingxuan Yang, Jun Xu, Sheng Gao, Jun Guo, and Ji-Rong Wen. 2021.  Adapting user preference to online feedback in multi-round conversational recommendation. In _Proceedings of the 14th ACM international conference on web search and data mining_. 364–372.
  * Zhang et al. (2023) Xiaoyu Zhang, Xin Xin, Dongdong Li, Wenxuan Liu, Pengjie Ren, Zhumin Chen, Jun Ma, and Zhaochun Ren. 2023.  Variational Reasoning over Incomplete Knowledge Graphs for Conversational Recommendation. In _Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining_. 231–239.
  * Zhao et al. (2023) Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. 2023\.  A survey of large language models.  _arXiv preprint arXiv:2303.18223_ (2023).
  * Zhou et al. (2020a) Kun Zhou, Wayne Xin Zhao, Shuqing Bian, Yuanhang Zhou, Ji-Rong Wen, and Jingsong Yu. 2020a.  Improving conversational recommender systems via knowledge graph based semantic fusion. In _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_. 1006–1014.
  * Zhou et al. (2020b) Kun Zhou, Yuanhang Zhou, Wayne Xin Zhao, Xiaoke Wang, and Ji-Rong Wen. 2020b.  Towards topic-guided conversational recommender system.  _arXiv preprint arXiv:2010.04125_ (2020).
  * Zhou et al. (2023) Wangchunshu Zhou, Yuchen Eleanor Jiang, Long Li, Jialong Wu, Tiannan Wang, Shi Qiu, Jintian Zhang, Jing Chen, Ruipu Wu, Shuai Wang, et al. 2023\.  Agents: An open-source framework for autonomous language agents.  _arXiv preprint arXiv:2309.07870_ (2023).


# Construction of Multiple Constrained DNA Codes

###### Abstract

DNA sequences are prone to creating secondary structures by folding back on
themselves by non-specific hybridization among its nucleotides. The formation
of secondary structures makes the sequences chemically inactive towards
synthesis and sequencing processes. In this letter, our goal is to tackle the
problems due to the creation of secondary structures in DNA sequences along
with constraints such as not having a large homopolymer run length. In this
paper, we have presented families of DNA codes with secondary structures of
stem length at most two and homopolymer run length at most four. By mapping
the error correcting codes over $\mathbb{Z}_{11}$ to DNA nucleotides, we
obtained DNA codes with rates $0.5765$ times the rate of corresponding code
over $\mathbb{Z}_{11}$, which include some new secondary structure free and
better-performing codes for DNA based data storage and DNA computing purposes.

Siddhartha Siddhiprada Bhoi111Department of Mathematics & Computing, Indian
Institute of Technology (ISM), Dhanbad, India<EMAIL_ADDRESS>P.
Udaya222School of Computing and Information Systems, The University of
Melbourne, Parkville, Australia<EMAIL_ADDRESS>Abhay Kumar
Singh333Department of Mathematics & Computing, Indian Institute of Technology
(ISM), Dhanbad, India<EMAIL_ADDRESS>
##  1 Introduction

Deoxyribose Nucleic Acid(DNA) is nature’s way of storing genetic data and has
been the central concept in DNA computing[10]. DNA based data storage is
important due to its high storage density, capacity, and longevity [2], [3].
These advantages motivated researchers to explore the development of the
subject.
Let $S_{DNA}=\\{A,T,G,C\\}$, a set of four DNA nucleotides named Adenine (A),
Guanine (G), Cytosine(C), and Thymine (T). DNA is made from DNA strands, which
are sequences over $S_{DNA}$ and for any positive integer $n$, a DNA code
$S^{n}_{DNA}$ is a collection of DNA sequences of length $n$. For each
$X=x_{1}\cdots x_{n}\in S^{n}_{DNA}$, then the reverse of the DNA sequence
denoted by $X^{r}$ is $x_{n}x_{n-1}\cdots x_{1}$, the complement of the DNA
sequence denoted by $X^{c}$ is $x_{1}^{c}x_{2}^{c}\cdots x_{n}^{c}$, and the
reverse complement of the DNA sequence denoted by $X^{rc}$ is
$x_{n}^{c}x_{n-1}^{c}\cdots x_{1}^{c}$. The complements of the DNA nucleotides
are $T^{c}=A$, $A^{c}=T$, $G^{c}=C$, and $C^{c}=G$. DNA sequences are
synthesized physically and read by the methods of DNA synthesis and DNA
sequencing, respectively [4]. During the synthesis and sequencing, various
types of errors can occur, which bring in the importance of the study of the
minimum distance of DNA code, the property that enables the suppression of
those errors.

The purpose of DNA sequencing is to read the DNA content, i.e., to determine
the exact DNA nucleotides along with their order. This is accomplished using
the specific hybridization between the DNA sequence and its complement [5].
Hybridization is the process of complementary base pairs binding to form a
double helix. The main source of errors at the time of the sequencing process
is due to non-specific hybridization. If in a DNA code some of the DNA
sequences are similar enough among themselves or their reverse or reverse-
complement versions, then non-specific hybridization will take place. This
situation motivates authors [[5], [6], [7], [14], [15]] to design DNA codes
whose sequences are sufficiently different among themselves as well as from
their reverse and reverse complement versions. The reverse-complement
constraint is the constraint in which DNA sequences and their reverse
complement versions are far apart by at least the minimum Hamming distance of
the code.

GC content is the percentage of nitrogenous bases in a DNA molecule that are
either guanine ($G$) or cytosine ($C$). The average GC-content in human genes
ranges from $35-60$ percent across $100$-Kb fragments [8]. The variation in GC
content can lead to variation in melting temperature and stability of the DNA
strand. DNA strands with $50$ percent GC content have the highest stability,
thus GC content is kept to nearly $50$ percent for the DNA based data storage.

At the time of synthesis and sequencing of DNA sequences with a high
repetition of nucleotides, insertion, deletion, and substitution errors can
occur [3]. This high consecutive repetition of nucleotides in DNA sequences is
called a homopolymer run. A DNA sequence is free from a homopolymer of run
length $l$ if all nucleotides in any subsequence of length $l$ are not the
same. For example, the DNA sequence $ACGCCCCCGTG$ has a homopolymer of run
length $6$. In [15], the authors have discussed enumerating methods and bounds
over DNA sequences with GC constraints, homopolymer run length at most 3, and
specific Hamming distances.

In a DNA strand, the nucleic acids can have primary, secondary and tertiary
structures. The primary structure consists of a linear sequence of
nucleotides, the secondary structure is due to the base-pairing interaction of
nucleotides within an active single-stranded DNA sequence [10], and tertiary
structure is due to the position of atoms in 3D space and its steric and
geometric constraints. A DNA strand can fold back upon itself and form a loop-
like structure with itself. Because of this structure, DNA becomes slow to
react to chemical reagents in the sequencing process[13]. Therefore, to read
such DNA sequences with a secondary structure, the DNA needs to be unfolded,
which can require extra resources and energy, leading to storage inefficiency.
The authors [10] reports new DNA codes avoiding secondary structure. For some
particular cases, some constraints such as reverse and reverse-complement
constraints and fixed GC-content constraints are also discussed in [10], [6].

Benerjee et.al.[1] took an interesting approach to the code construction by
considering a certain set of DNA sequences of length two as the base alphabet
and mapping it to the field $\mathbb{Z}_{5}$. This method enabled them to
define DNA codes as an image of codes over $\mathrm{\mathbb{Z}_{5}}$. It is a
natural question to find if other algebraic structures can provide a map to
DNA codes with better parameters for DNA based data storage such that the
resulting DNA sequences avoid secondary structure and satisfy the other
necessary constraints.

After providing the required notations and preliminaries in Section II, the
rest of the letter is organised as follows. Homopolymers and Secondary
structure avoiding maps, and their properties are discussed in the next
section. Further, in Section IV, families of DNA codes are constructed, and
other families of codes like Hamming codes and Reed Solomon codes are studied.
In Section V, a comparative analysis is established, and a comparative table
of code rates and code attributes is provided.

##  2 PRELIMINARIES AND NOTATION

Let $F_{q}$ denote an alphabet of size $q$ symbols. For any positive integer
$n$, a code $C$ over the alphabet $F_{q}$ is a subset $C\subset F_{q}^{n}$ of
size $M$ and minimum distance $d$. The Hamming distance for any two sequences
of equal length $x$ and $y$ is denoted by $d_{H}(x,y)$ and defined as the
number of positions at which the corresponding symbols are different. The
Hamming distance for a code $C$ is defined as
$d_{H}(C)=\mathrm{min}\\{d_{H}(x,y):x\neq y$ $\forall$ $x,y\in C\\}$. A DNA
code $C_{DNA}$ is any code defined over the alphabet $S_{DNA}$. For any DNA
code $C_{\mathrm{DNA}}$ with minimum Hamming distance $d_{H}$, the reverse
minimum distance $d^{r}_{H}=\mathrm{min}\\{d_{H}(x,y^{r}):x\neq y^{r}$ and
$x,y^{r}\in C_{\mathrm{DNA}}\\}$. Let $X=x_{1}\cdots x_{n}\in
S_{\mathrm{DNA}}^{n}$ be a DNA sequence of length $n$, then for any integer
$i,j$ such that $1\leq i\leq j\leq n$ the continuous sequence
$x_{i},x_{i+1}\cdots x_{j}$ is called a subsequence of $X$.

We have defined free energy and interaction energy and also provided the
relation between them. We have also discussed how the free energy affect the
secondary structure. A chemically active DNA sequence $x_{1}x_{2}\cdots
x_{n}$, to gain stability forms secondary structure and it releases energy
known as free energy [13], denoted by $E_{1,n}$. The free energy of a DNA
sequence can be used to predict the secondary structure of the DNA sequence.
The free energy depends on the energy released by pairing $(x_{i},x_{j})$,
where $1\leq i<j\leq n$. This released energy is called interaction energy.
The Nussinov-Jackson folding algorithm (NJ algorithm) is used to approximately
predict the secondary structure in a given DNA sequence [12]. In the NJ
algorithm, it is assumed that the interaction energy $\mu(x_{i},x_{j})$ is
independent of all other nucleotide pairs. They only depend on the chosen
nucleotide base pair $(x_{i},x_{j})$. Commonly used values of
$\mu(x_{i},x_{j})$ are

$\mu(x_{i},x_{j})=\left\\{\begin{array}[]{ll}-5&if(x_{i},x_{j})\in\\{(C,G),(G,C)\\},\\\
-4&if(x_{i},x_{j})\in\\{(T,A),(A,T)\\},\\\
-1&if(x_{i},x_{j})\in\\{(T,G),(G,T)\\},\\\ \ \ 0&otherwise\\\
\end{array}\right.$

As NJ algorithm consider interaction energy ,$\mu(x_{i},x_{j})$, to be
independent of other nucleotides except $x_{i}$ and $x_{j}$, we can calculate
minimum free energy of a DNA sequence through a recursion. The minimum free
energy for a subsequence $x_{i}x_{i+1}\cdots x_{j}$ of a DNA sequence
$x_{1}x_{2}\cdots x_{n}$ is given as
$E_{i,j}=\mathrm{min}\\{E_{i+1,j-1}+\mu(x_{i},x_{j}),E_{i,k-1}+E_{k,j}:k=1,2,\cdots,j\\}$
with initial conditions $E_{l,l}=E_{l-1,l}=0$ for $l=1,2,\cdots,n$ [10]. A
larger negative value for free energy means a higher probability of secondary
structure in the DNA sequence. The difference in the values of the free
energies is due to the relative strength of the bonds between DNA nucleotides,
i.e., Guanine(G) and Cytosine(C) have a triple bond between them whereas
Adenine(A) and Thymine(T) have a double bond between them. So, the relative
strength of the bond between Guanine(G) and Cytosine(C) is higher than that of
Adenine(A) and Thymine(T). For a DNA sequence $x=x_{1}x_{2}\cdots x_{n}$, we
define secondary-complement sequence as $x^{sc}=x_{n}^{sc}x_{n-1}^{sc}\cdots
x_{1}^{sc}$ with $A^{sc}$ is $T$, $C^{sc}$ is $G$, $T^{sc}$ can either $A$ or
$G$ and $G^{sc}$ can either be $C$ or $T$. Note that the reverse complements
of a DNA sequence are secondary complements, but the converse is not true in
general. A DNA subsequence can have multiple secondary complements i.e.,
$(ATCA)^{sc}=TGAT$ and $(ATCA)^{sc}=TGGT$. If we take two disjoint
subsequences of a given DNA code such that one is a secondary complement of
the other, then the subsequences are called disjoint secondary-complement
subsequences of the DNA sequence. The goal of the paper is to find such DNA
sequences which are stable without secondary structure.

Let the nucleotides in a DNA sequence $x=x_{1}x_{2}\cdots x_{n}\in
S_{\mathrm{DNA}}^{n}$ be indexed from 1 to n and for any $1\leq i,j\leq n$,
$(x_{i},x_{j})$ denote the pairs contributing to the secondary structure.
These are the pairs of nucleotides that have negative interaction energy as
per NJ algorithm. For any $1\leq i_{1},j_{1},i_{2},j_{2}\leq n$, the pairs of
nucleotide $(x_{i_{1}},x_{j_{1}})$ and $(x_{i_{2}},x_{j_{2}})$ are said to be
a consecutive set of pairs of nucleotide if both $i_{1}$ and $i_{2}$ are
consecutive and $j_{1}$ and $j_{2}$ are consecutive. We define the stem length
of a DNA sequence as the number of a consecutive set of pairs of nucleotides
contributing to secondary structure and stem is defined as the consecutive set
of pairs contributing to secondary structure. We consider these since many
pairs are not possible due to chemical and stereo-chemical constraints [11].

For example, in a DNA sequence $ATTCAAAATGGATCCGTAATGGAT$,
$\\{(x_{i},x_{25-i})$, $(x_{j},x_{5+j})|i=1,2,3,4,5;j=8,9,10,11,12)\\}$ are
two disjointed secondary structures of length $5$ as shown in Fig 1. As
$(ATTCA)^{sc}=TGGAT$ and $(ATGGA)^{sc}=TCCGT$.
Lemma 1 For a given positive integer $l$, if the DNA sequence is free from a
disjoint secondary complement of length $l+1$, then there cannot exist any
secondary structure of stem length more than $l$.
Proof. It is observed from the free energy of a DNA sequence that if there
exist two disjoint secondary-complement sub-sequences $\alpha$ and $\beta$ of
length $l+1$ in the DNA sequence such that $\alpha$ = $\beta^{sc}$ then there
exists a secondary structure of stem length $l+1$. It is also observed that if
the DNA sequence is free from secondary-complement sub-sequence of length $l$,
it is also free from secondary-complement sub-sequence of length $l+k$ where
$k$ is a non-negative integer. The lemma follows from the contrapositive of
the above observations. $\square$

For example, consider the DNA sequence $X=ATTCAAAATGGATCCGTAATGGAT$ as shown
in Fig 1. The sequence $X$ have two disjointed secondary structures of length
$5$ and hence it is free from a disjoint secondary complement of length $6$.
So according to Lemma 1, $X$ can not have a secondary structure of stem length
more than $5$.

##  3 DNA Alphabets and Their Properties

The presence of secondary structure in a DNA sequence depends upon the value
of free energy of the DNA sequence and the value of free energy depends upon
the relative bond strength and bonding between some of the DNA subsequences.
By avoiding such subsequences, we can control the free energy of DNA sequence
and hence have control upon the presence of secondary structure in the DNA
sequence.

The structure of the base alphabet is extremely important to control the free
energy, which depends on the interaction between the nucleotides. If the base
alphabet is $S_{\mathrm{DNA}}$, then in the pseudo-random sequence method, it
is impossible to control the secondary structures as interactions are ensured
between every possible combination due to the nature of the sequence
generation mechanism. In [1], the authors choose a base alphabet as
$\\{AA,AC,CA,CC,TC\\}$, a subset of length two nucleotides. In this letter, we
consider the base alphabet of length $3$. We are interested in a set S to be
the set of possible base alphabets of length $3$ nucleotides which can avoid
secondary structure when DNA sequences are constructed as concatenations of
the elements in the base alphabet. The set
$S=\\{CCC,CCA,CAC,CAA,ACC,ACA,AAC,AAA,TCC,$ $CTC,TCA\\}$ with 11 elements is
considered for this letter. For any DNA code $C_{\mathrm{DNA}}\subseteq S^{n}$
of length $3n$ constructed using a bijective map $\mathbb{Z}_{11}$ to $S$. We
use $\mathbb{Z}_{11}=(0,1,2,3,4,5,6,7,8,9,\text{\@slowromancap x@})$ in our
code construction, where $\text{\@slowromancap x@}=10\mathrm{\mod}11$.
The bound on free energy on DNA codes over $S^{n}$ is obtained through
mathematical induction on the parameter $n$ for the free energy presented
below in proposition 1.
Proposition 1. For any DNA sequence in $S^{n}$, $E_{1,3n}\geq-4n$.
Proof of the above Proposition is provided in the appendices.

It should be noted that for any arbitrary DNA sequence of length $3n$, we have
$E_{1,3n}\geq-5\left\lfloor 3n/2\right\rfloor$. From Proposition 1, it is
clear that the free energy for any DNA sequences over $S$ is restricted thus
avoiding secondary structures as explained in [1].
Lemma 2 For positive integers $n$, $m$, and $l$, such that $n\geq 6$ and
$2\leq l\leq\left\lfloor m/2\right\rfloor$. The set $U_{n}=\\{a_{1}a_{2}\cdots
a_{n}:a_{i}\in U\subset S^{m}_{\mathrm{DNA}},i=1,2,\cdots,n\\}$. If each DNA
sequence in $U_{6}$ is free from l length secondary-complement sub-sequences,
then each DNA sequence in $U_{n}$ is also free from disjoint secondary-
complement sub-sequences of length more than l. Any 3n-length DNA sequence in
$S^{n}$ is free from a secondary structure of stem length more than one.
Proof. By the way of construction of $U_{6}$, DNA sequences of $U_{6}$ ensure
that concatenation of any six DNA sequences from $U$ is free from $l$ length
secondary-complement sub-sequences. So, the same stands true for n DNA
sequences from $U$. For m = 3; l = 2, the results follow. $\square$
Note that Pairing between G and C, and between G and T is not possible, thus
preventing many secondary structures. Again, if any secondary structure
exists, then it cannot have a stem length of more than one, and thus less
energy is required to break it. From Lemma 2 and Remark, it is clear that any
DNA sequences in $S^{n}$ are free from a secondary structure of stem length of
more than one.

###  3.1 Secondary Structure Avoiding Map

Define a bijective map $\phi:\mathbb{Z}_{11}\to S$ such that:

x | $\boldmath{\phi(x)}$ | x | $\boldmath{\phi(x)}$ | x | $\boldmath{\phi(x)}$
---|---|---|---|---|---
0 | CCC | 4 | ACC | 8 | TCC
1 | CCA | 5 | ACA | 9 | CTC
2 | CAC | 6 | AAC |  x@ | TCA
3 | CAA | 7 | AAA |  |

where $x\in\mathbb{Z}_{11}$ and $\phi(x)\in S$. For any sequence
$x=x_{1}x_{2}\cdots x_{n}\in\mathbb{Z}_{11}^{n}$, we have
$\phi(x)=\phi(x_{1})\phi(x_{2})\cdots\phi(x_{n})$. For any $x$ and $y$
$\in\mathbb{Z}_{11}$, we define distance function as
$d:\mathbb{Z}_{11}\times\mathbb{Z}_{11}\to R$ such that
$d(x,y)=d_{H}(\phi(x),\phi(y))$. For any $x$ and $y$ $\in\mathbb{Z}_{11}^{n}$,
we define $d(x,y)=\sum_{i=1}^{n}d(x_{i},y_{i})$. For any code $C$ over
$\mathbb{Z}_{11}$, $d=\mathrm{min}\\{d(x,y):x\neq y\ and\ x,y\in C\\}$.
Proposition 2. $(\mathbb{Z}_{11}^{n},d)$ and $(S^{n},d_{H})$ are isometric.
Proof. The function $\phi:(\mathbb{Z}_{11}^{n},d)\rightarrow(S^{n},d_{H})$ is
an isometric function as it preserves the distance functions $d$ and $d_{H}$
by its definition $d(x,y)=d_{H}(\phi(x),\phi(y))$ for all
$x,y\in\mathbb{Z}_{11}^{n}$. $\square$
Theorem 1. For every code $C$ with parameters $(n,M,d)$ over
$\mathbb{Z}_{11}$, there exists a DNA code $\phi(C)$ with parameters
$(3n,M,d_{H})$ such that each DNA sequence in $\phi(C)$ is free from secondary
structure of stem length more than one and the minimum Hamming distance
$d_{H}=d$.
Proof. From Proposition 2, $\phi$ is an isometric from
$(\mathbb{Z}_{11}^{n},d)$ to $(S^{n},d_{H})$. Thus, they have the same size
and Hamming distance. The proof follows from Lemma 2. $\square$
Lemma 3. $d_{H}(x,y^{c})\geq n$ for any $x,y\in S^{n}$.
Proof. It is observed that for any $x,y\in S$, $d_{H}(x,y^{c})\geq 1$. This
implies $d_{H}(x,y^{c})=\sum_{i=1}^{n}d_{H}(x_{i},y^{c}_{i})\geq n$. $\square$
Lemma 4. For a $(3n,M,d_{H})$ DNA code $C$ over $S$, if $d_{H}\leq n$ then
$C\cup C^{c}$ is a $(3n,2M,d_{H})$ DNA code where $C^{c}=\\{x^{c}:x\in C\\}$.
Proof. From the definition of complement of DNA sequence the results on the
size and length follows. For any DNA code $C_{DNA}$ over $S$,let $x,y\in
C_{DNA}$ be two DNA sequences. Then $d_{H}(x^{c},y^{c})=d_{H}(x,y)\geq d_{H}$
and from Lemma 3 $d_{H}(x^{c},y^{c})=d_{H}(x,y)\geq n$. So, for $C_{DNA}\cup
C_{DNA}^{c}$, the minimum Hamming distance is $\mathrm{min}{d_{H},n}=d_{H}$.
Hence,the result on distance follow. $\square$
Lemma 5. For any $(n,M,d)$ code $C\subset\mathbb{Z}_{11}^{n}$, $\phi(C)$
exists and if $d\leq n$ then it satisfies the reverse complement constraint.
Proof. If $x,y\in S^{n}$, $d_{H}(x,y^{rc})\geq n\geq d$ and thus the proof
follows from Proposition 2. $\square$

###  3.2 Homopolymers Deletion Map

Define a non-surjective map $f:S^{n}\to S_{\mathrm{DNA}}^{3n}$, such that for
a sequence $y\in S^{n}$, there exists a subsequence with consecutive repeated
nucleotides of length more than four, then we flip the nucleotide present in
doubly even positions of $y$ to $T$.

For $f(y)=y_{1}y_{2}y_{3}\cdots y_{3n}$ if $y_{i+1}\cdots y_{i+l}$ are of same
nucleotide with $l\geq 4$, then flip $y_{i+j}$ to $T$ if $j\mod 4=0$. For
example, $f(ACCACCCCCCCAAAAAAA)=ACCACCCTCCCTAAATAAA$. It does not contain any
homopolymers of run length more than four.
Lemma 6. For any DNA sequence $x\in S^{n}$, $f(x)$ cannot have a secondary
structure with a stem length more than two.
Proof. For any DNA sequence $x\in S^{n}$, we observe that in $f(x)$ the
flipped nucleotides varies at least by four. Thus, from Lemma 2, the stem
length of a secondary structure cannot be more than two. $\square$
Theorem 2. For every code $C$ over $\mathbb{Z}_{11}$ with parameters
$(n,M,d)$, there exists a reverse-complement DNA code $f(\phi(C))$ with
parameters $(3n,M,d_{H})$ such that each DNA sequence in $f(\phi(C))$ is free
from homopolymers of run length more than four and from secondary structure of
stem length more than two, where $\left\lceil\frac{3d}{4}\right\rceil\leq
d_{H}\leq\left\lceil\frac{3n+3d}{4}\right\rceil$.
Proof. If there exist $m$ consecutive nucleotides, then at most $\left\lfloor
m/4\right\rfloor$ nucleotides are flipped to $T$. Thus for any $x,y\in S^{n}$
$d_{H}(x,y)-\left\lfloor m/4\right\rfloor\leq d_{H}(f(x),f(y))\leq
d_{H}(x,y)+\left\lfloor m/4\right\rfloor$. The upper and lower bounds follow
from the extreme cases, i.e., $m=3n-d_{H}$ and $m=d_{H}$. $\square$

##  4 Families of new constrained DNA codes

### Family 1:

For $q=11$, consider the family of codes $C_{k}$ of length $4^{k-1}$ and
dimension ${k}$ with $2\leq k\leq 5$ with generator matrix $G_{k}$. The matrix

$G_{2}=\left(\begin{matrix}1&1&1&1\\\ 1&5&9&\text{\@slowromancap
x@}\end{matrix}\right)$

and

$G_{i+1}=\left(\begin{matrix}1_{4^{i-1}}&2_{4^{i-1}}&3_{4^{i-1}}&4_{4^{i-1}}\\\
G_{i}&G_{i}&G_{i}&G_{i}\end{matrix}\right),\text{ for}\ \ i=2,3,4.$

where $i_{j}$ is all the $i$ vectors of length $j$ for $i=2,3,4,5$. The code
meets the Griesmer bound:
$n=\sum_{i=0}^{k-1}\left\lceil\frac{d}{q^{i}}\right\rceil$.

Theorem 3. There exists a $(2^{2k-1},5^{k},3\cdot 4^{k-2})$ DNA code
$f(\phi(C_{k}))$ with $d_{H}^{r}=2^{2k-3}$.
Proof. The distance $d(0_{4},4190)=3$, where $4190=2(1_{4}+159$x@$)$ is in the
linear span of $G_{2}$. Thus $d(0_{4^{k-1}},(4190)^{k-1})=3\cdot 4^{k-2}$ for
any positive integer k. From symmetry, the minimum distance for the code
$C_{k}$ is $d(0_{4^{k-1}},(4190)^{k-1})=3\cdot 4^{k-2}$. The size and length
follow from Theorem 1. $\square$

### Hamming Codes:

Consider a q-ary Hamming code. For an integer r$(\geq 2)$, the Hamming code is
a linear code with parameters
$\left[\frac{q^{r}-1}{q-1},\frac{q^{r}-1}{q-1}-r,3\right]$ over
$\mathbb{F}_{q}$. For $q=11$ we have the following results:
Theorem 4. There exists a
$\left(\frac{3(11^{r}-1)}{10},11^{\frac{11^{r}-1-10r}{10}},3\right)$ DNA code
$\phi(H_{r})$ for Hamming code $H_{r}$ over $\mathbb{Z}_{11}$.
Proof. The Hamming code over $\mathbb{Z}_{11}$ of degree $r(\geq 2)$ is a
$\left[\frac{11^{r}-1}{10},\frac{11^{r}-1}{10}-r,3\right]$ linear single error
correcting code. The size and length of the code follow from the parameters of
$H_{r}$ and from Theorem 1. For some $x=0_{\frac{11^{r}-1}{10}}$ and
$y=0_{\frac{11^{r}-31}{10}}191$ are the codewords in $H_{r}$ such that
$d(x,y)=3$, where $0_{i}$ represents all zero vector of length i. As
$3=d_{H}^{*}\leq d$, it follows the result. $\square$
Lemma 8. For the code $H_{r}$ over $\mathbb{Z}_{11}$, there exists a
$\left(\frac{3(11^{r}-1)}{10},11^{\frac{11^{r}-1-10r}{10}},d_{H}^{*}\right)$
DNA code $f(\phi(H_{r}))$ for $r=2$, $d_{H}^{*}=3$.
Proof. The proof follows from Theorem 2 and Theorem 4. $\square$

### Reed Solomon Codes:

A q-ary Reed Solomon code is a q-ary Bose, Chaudhari, and Hocquenghem (BCH)
code of length $q-1$ generated by

$g(x)=(x-\alpha^{a+1})(x-\alpha^{a+2})\cdots(x-\alpha^{a+\delta-1}),$

where $a\geq 0$, $2\leq\delta\leq q-1$ and $\alpha$ is a primitive element of
$q$-ary field. Reed-Solomon codes are Maximum Distance Separable (MDS) codes
with parameters $[q-1,q-\delta,\delta]$ over $F_{q}$, for any $2\leq\delta\leq
q-1$. As Reed Solomon Codes have high reliability and increase in code rate
with increase in alphabet size, they are used widely for Data Storage and long
distance communication purposes. So for $\mathbb{Z}_{11}$, RS codes have the
following properties:
Theorem 5. There exists a $\left(30,11-\delta,\delta\right)$ DNA code
$\phi(RS)$ for Reed Solomon Code $RS$ over $\mathbb{Z}_{11}$.
Proof. The Reed Solomon code over $\mathbb{Z}_{11}$ is a
$\left(10,11-\delta,\delta\right)$ linear MDS code. The size and length of the
code follow from the parameters of $H_{r}$ and Theorem 1. $\square$
Lemma 9. For the family of Reed Solomon code over $\mathbb{Z}_{11}$, there
exists a single error correcting code of parameter $\left(30,8,3\right).$
Proof. The size and length of code follow from Theorem 2 and Theorem 5 for
$\delta=3$. $0020010001$ is a $RS(11)$ codeword and $d(0_{10},0020010001)=3$.
$\square$

##  5 Discussion of the results

It is observed that all DNA codes constructed in Section IV are reverse-
complement DNA codes which can also be concluded from Lemma 6 and Theorem 2.
In Theorem 3 and Theorem 4, the DNA codes are free from the secondary
structure with stem length starting from one. Similarly, the DNA codes in
Lemma 8 and Lemma 9 are free from homopolymers of run lengths more than four
and secondary structures of stem length more than two. Comparisons of
properties of single error-correcting DNA codes are made in Table 1 against
the properties, $P_{1}$ to $P_{3}$, are respectively the secondary structure
avoiding property, the homopolymers run length, and reverse complement
property, respectively. The DNA codes constructed from Reed-Solomon codes over
$\mathbb{Z}_{11}$ appear to show a comparatively better code rate than other
codes in the literature. While comparing with the codes presented in [1], for
some lengths of DNA sequences, our codes show a higher code rate. This also
opens the problem of finding appropriate algebraic structures to construct DNA
codes that can provide optimum code rates while obeying all the constraints of
DNA codes.

In this letter, we have found DNA codes of a certain length providing a higher
code rate than the DNA codes of similar error correcting capabilities provided
in the literature. For example, a single error Reed Solomon Code over our
construction of DNA codes provides a code rate of $0.46125$ as compared to the
previous construction in [1] with code rate $0.145$. Although the asymptotic
code rate DNA code from Hamming codes is a little less than from the
construction provided in [1], our construction provides a better code rate for
DNA codes of certain lengths. For the second-degree Hamming code, our
construction provides a comparatively better code rate than previous codes in
the literature. Furthermore, the map $\phi$ considered in the letter naturally
leads to increased distances over the DNA alphabet with some codewords; for
example, $0010060006$ and $0000000000$ are two $(10,8,3)$ Reed Solomon
codewords over $\mathbb{Z}_{11}$ with $d_{H}(0000000000,0010060006)=3$ but
$d_{H}(f(\phi(0000000000)),f(\phi(0010060006))=5$.
Remark: The DNA sequences constructed by the method provided in the letter
have the unique characteristic of preserving the property of homopolymers of
run length at most four and avoiding secondary structure of stem length more
than two with concatenation operation. This operation enables us to construct
families of larger lengths using concatenation operation, preserving the
stated properties. This preservation of properties under the concatenation
operation applies to the atomic families only and not to the families obtained
by including code and its complement, such as the code in the 9th row of the
table.

##  6 Conclusions

The methods discussed in the letter provide secondary structure free DNA codes
with homopolymer run length less than four. These codes have the code rates
$0.5765(\frac{log_{4}11}{3})$ times the code rate of the corresponding code
over $\mathbb{Z}_{11}$. For some specific lengths, they provide better code
rates and satisfy more constraints than the existing codes in the literature.
Although our method yields better performing codes with specific lengths, it
is an interesting open question to determine an appropriate algebraic
structure that leads to optimal codes.

$(n,M,d_{H})$ | Code Rate | $P_{1}$ | $P_{2}$ | $P_{3}$
---|---|---|---|---
DNA Codes | $log_{4}M/n$ |  |  |
Example 9 [9] | $0.14937$ | No | $>4$ | No
Example 2 [10] | $0.25850$ | Yes | $>4$ | No
Example 4 [10] | $0.40105$ | Yes | $>4$ | No
$(8,256,4)$ code | $0.50000$ | No | No | Yes
Table III [6] |  |  |  |
$(8,244,4)$ code | $0.48796$ | No | No | Yes
Table III [6] |  |  |  |
$f(\phi(H_{7}))$ | $0.58027$ | Yes | $<4$ | Yes
[1] |  |  |  |
$f(\phi(H_{5}))$ | $0.57639$ | Yes | $<4$ | Yes
$over\mathbb{Z}_{11}$ |  |  |  |
$C\cup C^{c}$ | $0.42865$ | Yes | $<4$ | Yes
$C=f(\phi(H_{2}))$ |  |  |  |
[1] |  |  |  |
$C\cup C^{c}$ | $0.494365$ | Yes | $<4$ | Yes
$C=f(\phi(H_{2}))$ |  |  |  |
$over\mathbb{Z}_{11}$ |  |  |  |
$f(\phi(H_{2}))$ | $0.42865$ | Yes | $<4$ | Yes
[1] |  |  |  |
$f(\phi(H_{2}))$ | $0.48047$ | Yes | $<4$ | Yes
$over\mathbb{Z}_{11}$ |  |  |  |
$C\cup C^{c}$ | $0.35274$ | Yes | $<4$ | Yes
$C=f(\phi(C_{2}))$ |  |  |  |
[1] |  |  |  |
$f(\phi(C_{2}))$ | $0.29024$ | Yes | $<4$ | Yes
[1] |  |  |  |
$f(\phi(C_{2}))$ | $0.28828$ | Yes | $<4$ | Yes
$over\mathbb{Z}_{11}$ |  |  |  |
$f(\phi((10,8,3)$ | $0.145120$ | Yes | $<4$ | Yes
$RS-code))$ |  |  |  |
[1] |  |  |  |
$f(\phi((10,8,3)$ | $0.461258$ | Yes | $<4$ | Yes
$RS-code))$ |  |  |  |

Table 1:  Comparisons of new codes with the codes in literature the
properties: $P_{1}$ is the secondary structure avoiding property, $P_{2}$ is
Homopolymer run length, $P_{3}$ is reverse complement constraint.

## References

  * [1] K. G. Benerjee and A. Banerjee, ”On DNA Codes with Multiple Constraints,” in _IEEE Communications Letters_ , doi: 10.1109/LCOMM.2020.3029071.
  * [2] G.M.Church, Y. Gao, and S. Kosuri, “Next-generation digital information storage in DNA,” _Science_ , vol. 337, no. 6102, pp. 1628–1628, Sept 2012\.
  * [3] N. Goldman, P. Bertone, S. Chen, C. Dessimoz, E. M. LeProust, B. Sipos, and E. Birney, “Towards practical, high-capacity, low maintenance information storage in synthesized DNA,” _Nature_ , 2013.
  * [4] S. M. H. T. Yazdi, H. M. Kiah, E. Garcia-Ruiz, J. Ma, H. Zhao and O. Milenkovic, ”DNA-Based Storage: Trends and Methods,” in IEEE Transactions on Molecular,_Biological and Multi-Scale Communications_ , vol. 1, no. 3, pp. 230-248, Sept. 2015, doi: 10.1109/TMBMC.2016.2537305.
  * [5] A. Marathe, A.E. Codon, and R. M. Corn, “On combinatorial DNA word design,” _Journal of Computational Biology_ , vol. 8, no. 3, pp. 201–219, July 2004.
  * [6] D.Limbachiya, K.G.Benerjee, B.Rao, and M. K. Gupta, “On DNA codes using the ring $Z_{4}+wZ_{4}$,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Vail, CO, USA, June 2018, pp. 2401–2405.
  * [7] V.V. Rykov, A.J. Macula, D. C. Torney, and P. S. White, “DNA sequences and quaternary cyclic codes,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Washington, DC, USA, USA, June 2001, pp. 248–248.
  * [8] International Human Genome Sequencing Consortium (February 2001). ”Initial sequencing and analysis of the human genome”. Nature. 409 (6822): 860–921.
  * [9] Y.S. Kim and S.H. Kim, ”New Construction of DNA codes with constant-GC contents from binary sequences with ideal correlation,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , St. Petersburg, Russia, July-Aug 2011, pp. 1569–1573.
  * [10] O.Milenkovic and N.Kashyap, ”On the design of codes for DNA computing,” in _Coding and Cryptography_ , Ytrehus, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, March 2006, pp. 100-119.
  * [11] M. Zuker, D. Sankoff, ”RNA secondary structures and their prediction”, _Bulletin of Mathematical Biology_ , Volume 46, Issue 4, 1984, Pages 591-621, ISSN 0092-8240, https://doi.org/10.1016/S0092-8240(84)80062-2.
  * [12] R. Nussinov and A.B. Jacobson, ”Fast algorithm for predicting the secondary structure of single-stranded RNA,” _National Academy of Sciences_ , vol. 77, no. 11, pp.6309-6313, Nov 1980.
  * [13] P. Clote and R. Backofen, _Computational molecular biology: An introduction._ Hoboken, New Jersey, US: Wiley Series in Mathematical and Computational Biology, Oct 2000.
  * [14] P. Mishra, C. Bhaya, A. K. Pal and A. K. Singh, ”Compressed DNA Coding Using Minimum Variance Huffman Tree,” in _IEEE Communications Letters_ , vol. 24, no. 8, pp. 1602-1606, Aug. 2020, doi: 10.1109/LCOMM.2020.2991461.
  * [15] D. Limbachiya, M. K. Gupta and V. Aggarwal, ”Family of Constrained Codes for Archival DNA Data Storage,” in _IEEE Communications Letters_ , vol. 22, no. 10, pp. 1972-1975, Oct. 2018, doi: 10.1109/LCOMM.2018.2861867.
  * [16] D. Huffman, “A method for the construction of minimum-redundancy codes,” Proc. IRE, vol. 40, no. 9, pp. 1098–1101, Sep. 1952.
  * [17] K. Sayood, Introduction to Data Compression. San Mateo, CA, USA: Morgan Kaufmann, 2017.

## Appendices

Proposition 1. For any DNA sequence in $S^{n}$, $E_{1,3n}\geq-4n$.
Proof of the above Proposition has been provided in the appendix.
Proof. According to NJ algorithm, the minimum free energy for a subsequence
$x_{i}x_{i+1}\cdots x_{j}$ of a DNA sequence $x_{1}x_{2}\cdots x_{n}$ is given
as

$E_{i,j}=min\\{E_{i+1,j-1}+\mu(x_{i},x_{j}),E_{i,k-1}+E_{k,j}:k=i+1,\cdots,j\\}$

with initial conditions $E_{l,l}=E_{l-1,l}=0$ for $l=1,2,\cdots,n$ [10].
The commonly used value of $\mu(x_{i},x_{j})$ are

$\mu(x_{i},x_{j})=\left\\{\begin{array}[]{ll}-5&if(x_{i},x_{j})\in\\{(C,G),(G,C)\\},\\\
-4&if(x_{i},x_{j})\in\\{(T,A),(A,T)\\},\\\
-1&if(x_{i},x_{j})\in\\{(T,G),(G,T)\\},\\\ \ \ 0&otherwise\\\
\end{array}\right.$

For sequences of length $3n$ over $S^{n}$, the minimum free energy is

$E_{1,3n}=min\\{E_{2,3n-1}+\mu(x_{1},x_{3}n),E_{1,k-1}+E_{k,3n}:k=2,\cdots,j\\}.$

As the above equation is a recurrence relation depended on the interaction
energy $\mu(x_{i},x_{j})$, for $1\leq i\leq j\leq 3n$ and initial values of
free energies are $0$. Free energy of any sequence is a function of
interaction energy. As the base alphabet set $S$ does not have any element
with nucleotide $G$, the interaction energy can only be released by the
interaction of nucleotide pairs $(A,T)$ and $(T,A)$. So,for any sequence $X$
of length $3n$,

$E_{1,3n}(X)=-4\times\text{number of (A,T) pairs present in the sequence }X$

. For n=1, $E_{1,3}(CCC)=0$, $E_{1,3}(CCA)=0$, $E_{1,3}(CAC)=0$,
$E_{1,3}(CAA)=0$, $E_{1,3}(ACC)=0$, $E_{1,3}(ACA)=0$, $E_{1,3}(AAC)=0$,
$E_{1,3}(AAA)=0$, $E_{1,3}(TCC)=0$, $E_{1,3}(CTC)=0$, $E_{1,3}(TCA)=-4$.
So, for any DNA sequence over $S$, $E_{1,3}\geq-4$.
For n=2, The sequence $TCATCA$ has only two pairs of (T, A) and
$E_{1,6}(TCATCA)=-8$. So, for any DNA sequence over $S^{2}$, $E_{1,6}\geq-8$.
Let it be true for a positive integer k. Then for any DNA sequences over
$S^{k}$, $E_{1,3k}\geq-4k$. On sequences over $S^{k}$, only the sequence
$TCA\cdots TCA$ has $k$ pairs of (T, A) on it and
$E_{1,3k}\underbrace{(TCA\cdots TCA)}_{\text{k times}}=-4k$.
For n=k+1, The sequence $TCA\cdots TCA$ has the highest number of (T, A) pairs
and
$E_{1,3(k+1)}\underbrace{(TCA\cdots TCA)}_{\text{k+1 times}}=-4(k+1)$. Hence
for any DNA sequences over $S^{k}$, $E_{1,3(k+1)}\geq-4(k+1)$.
So the proposition is true for $n=k+1$, and hence by the method of
mathematical induction, the proposition is true for any positive integer $n$.
$\square$