\chapter{مقدمه} 

%\[
%f(\theta)=E[Y(\theta)] 
%\Rightarrow
% \widehat{f}(\theta)=\sum_{i=1}^{n}{\frac{y_i}{n}} 
% \]
% 
% \[
%  \stackrel{\oplus \quad}{K_{n-1}^c}
%\]

\section{یب یب اس }
\marginpar{
\centering
{\vspace{-1.3cm}\[ \quad \] }
\includegraphics[scale=0.008]{pic1}
}
در طول سالیان اخیر، ذهن دانشمندان و به ‌خصوص زیست‌شناسان بر روی مطالعهٔ سلول‌های بنیادی
و ساختار ژنوم موجودات زنده متمرکز شده‌ است. همان‌طور ‌که می‌دانیم، اطلاعات ژنتیکی یک موجود زنده توسط کروموزوم‌ها که حاوی رشته‌های
بسیار پیچیدهٔ {\lr{DNA}} هستند، از یک نسل به نسل بعد انتقال می‌یابد.
از نظر بیوشیمیایی، یک ژن به صورت قطعه‌ای از رشتهٔ {\lr{DNA}} تعریف می‌شود که حامل دستورالعمل‌های لازم برای ساختن یک محصول دارای فعالیت بیولوژیکی -مانند پروتئین‌ها- است. این محصولات به ‌نوبهٔ ‌خود، فعالیت‌های سلول و اعمال مختلف بدن را تعیین می‌کنند و به‌ این ترتیب، در بروز صفات گوناگون وراثتی نقش مهمی دارند.

\subsection{یب یب اس }
اکنون

\hspace*{-5cm}\begin{minipage}[b]{4cm}
به ‌خصوص زیست‌شناسان بر روی مطالعهٔ سلول‌های بنیادی
و ساختار ژنوم موجودات زنده متمرکز شده‌ است.
\end{minipage}\vspace{-2.1cm}

جدا‌شدن تکه‌های ژن از بین رشتهٔ {\lr{DNA}} و قرارگرفتن آن‌ها با یک ترتیب خاص که منجر به فعال‌شدن رشتهٔ ژنی و در نتیجه تولید پروتئین می‌شود را فرایند  می‌نامند. 
با این شیوه، ‌دانشمندان می‌توانند کنترل اتم به اتم مولکول‌های بدن موجودات زنده را در دست داشته باشند و با تغییر در کد ژنتیکی آن‌ها، ویژگی‌های جدیدی را که بدان نیاز دارند، در طیف گسترده‌ای از حیوانات و جانداران خلق نمایند.

این فرایند یکی از پیچیده‌ترین و پیشرفته‌ترین پردازش‌هایی است که بر روی ساختار {\lr{DNA} \index{\lr{DNA}}} موجودات زنده انجام می‌شود.
به همین دلیل برای مطالعه این فرایند، لازم است موجود زنده‌ای را بیابیم که تا حد ممکن دارای ساختار ژنتیکی ساده‌ای
باشد. 
\begin{itemize}
\item 
ث ثقف ثقف 
\item
ثق ثقف ثصف ثقف ثصقف ثصقف ثقفثقص قفثف 
\item 
ثقصف ثقف
	\begin{enumerate}[a.]
	\item
ث فثصف ثصقف 
	\item
	ثقف ثصقف ثصف
	\end{enumerate}
\end{itemize}
یک گروه بسیار کهن از موجودات زندهٔ تک‌سلولی هستند که انواع مختلفی داشته و
قدمت آن‌ها در حدود دو میلیارد سال تخمین زده شده است. {}ها، نمونهٔ بسیار
جالبی از مژک‌داران هستند که دارای دو هسته می‌باشد.
\begin{changemargin}{-5cm}{0cm}
\noindent
که در مراحل تولیدمثل مورد استفاده قرار می‌گیرد
و  که رویش جانور و فعالیت‌هایی
مانند تنفس، سنتز پروتئین و هضم غذا را تحت کنترل دارد.
که در مراحل تولیدمثل مورد استفاده قرار می‌گیرد
و  که رویش جانور و فعالیت‌هایی
مانند تنفس، سنتز پروتئین و هضم غذا را تحت کنترل دارد.
که در مراحل تولیدمثل مورد استفاده قرار می‌گیرد
و  که رویش جانور و فعالیت‌هایی
مانند تنفس، سنتز پروتئین و هضم غذا را تحت کنترل دارد.
\end{changemargin}
در شکل زیر ساختار سلولی گونه‌ای از مژک‌داران نشان داده شده است.

\begin{figure}[h!]
\centering
%\includegraphics[width=1.5\linewidth]{bla.png}

\label{fig: Ciliate Cell}
\caption{گونه‌ای از مژک‌داران}
\end{figure}


%\newgeometry{ } %default
%\newgeometry{left=1cm,bottom=0.1cm}
تکه‌های ژن که در هستهٔ کوچک قرار دارند و از این به بعد آن‌ها
را {\lr{MDS} \index{\lr{MDS}}}{\LTRfootnote{Macronuclear Destined Segments}} می‌نامیم، در میان تکه‌هایی
به نام {\lr{IES} \index{\lr{IES}}}{\LTRfootnote{Internal Eliminated Segments}} قرار گرفته‌اند
و به طور معمول، فعال نبوده و نقش چندانی در فعالیت‌های زیستی ندارند.
در طی فرایند تولید‌مثل، هستهٔ بزرگ از روی هستهٔ کوچک توسعه پیدا می‌کند.
صدها هزار تکه‌ٔ {\lr{MDS}} که در میان {\lr{IES}}ها قرار گرفته‌اند، از یکدیگر جدا شده و با یک ترتیب خاص،
به صورت یک لیست پیوندی در کنار هم قرار گرفته و
در اصطلاح {\textit{مونتاژ}} می‌شوند.

%\restoregeometry


\marginpar{
\centering
{\vspace{-1.1cm}\[ \quad \] }
\begin{wrapfigure}{r}{5cm}
  \vspace{-20pt}
  \begin{center}
    \includegraphics[scale=0.008]{pic1}
  \end{center}
  \vspace{-20pt}
  \caption{یبلس ی لس س لسیبل سل سیل سیلب }
	\vspace{-10pt}
\end{wrapfigure}
}

با مطالعه بر روی این موجودات، در سال 2001، {\cite{EhrenfeuchtPetre2002}} یک مدل مولکولی بر پایهٔ سه
عملگر 
%توسط {\lr{Ehrenfeucht}}، {\lr{Prescott}} و {\lr{Rozenberg}}
برای فرایند مونتاژ ژن
پیشنهاد شد.
در این مقاله ثابت ‌شده ‌است که هر رشتهٔ ژنی می‌تواند توسط این سه عملگر مولکولی،
به هر شکل دلخواه مونتاژ گردد.
 
پس از توصیف مختصری درباره مقدمات بیولوژیکی و ساختار {\lr{DNA}} و ژن،
در فصل {\eqref{chp: StringBased}} بعد از شرح مقدماتی دربارهٔ رشته‌ها و معرفی عملگر‌های مولکولی مذکور،
می‌خواهیم نشان ‌دهیم که چگونه با کمک رشته‌های مجاز، مسألهٔ مونتاژ ژن برای ما مدل‌سازی می‌شود.
علاقه‌مندان برای آگاهی بیشتر در مورد مفاهیم زیست‌شناسی {\lr{MDS}} و {\lr{IES}} چگونگی
مونتاژ آن‌ها توسط این سه عملگر مولکولی،
می‌توانند مراجع {\cite{Ehrenfeucht2002}} و {\cite{bEhHaPePrRo04a}} را مطالعه فرمایند.

\begin{figure}[h!]
\centering

\label{fig: Ciliate Gene Assembly}
\caption{فرایند مونتاژ ژن در مژک‌داران}
\end{figure}

در بخش {\eqref{chp: GraphReduction}}، از روی این مدل و با استفاده از گراف‌های علامت‌دار، مدل دیگری ارائه خواهیم داد. در این مدل، عملگر‌های مولکولی به قواعد کاهش قابل‌اجرا بر روی گراف‌های علامت‌دار نظیر شده و مسأله مونتاژ ژن نیز به یک استراتژی کاهش موفّق برای این گراف‌ها تبدیل می‌شود. در بخش {\eqref{ssec: Me- Uniform R. S.}} نیز مطالب جدیدی دربارهٔ استراتژی کاهش یکدست آورده‌ایم.

پس از آن در فصل {\eqref{chp: Parallelism}}، به دنبال جستجوی استراتژی‌های کاهشی برای کاهش گراف‌های علامت‌دار هستیم که قواعد کاهش در آن، با هر ترتیبی قابل‌اجرا باشند. به چنین استراتژی‌هایی، استراتژی کاهش \textit{موازی} می‌گوییم.
در این فصل، نشان خواهیم داد که همیشه یک استراتژی کاهش موفّق را می‌توان به دسته‌هایی از
قواعد کاهش موازی -که اصطلاحاً آن‌ها را {\textit{گام}} می‌نامیم- افراز نمود.
مسأله بعدی که از اهمیّت ویژه‌ای برخوردار است، یافتن یک استراتژی کاهش موفّق با تعداد گام‌های کمینه، برای یک گراف علامت‌دار است.
تعداد گام‌های چنین استراتژی کاهشی را \textit{پیچیدگی موازی} آن گراف علامت‌دار می‌نامیم.
در بخش {\eqref{sec: UpperBound C}} کران بالایی برای پیچیدگی موازی گراف‌های علامت‌دار ارائه خواهیم داد و
در بخش {\eqref{sec: Cmplxty for special graphs}} نیز به بررسی پیچیدگی موازی برخی گراف‌های علامت‌دار خاص می‌پردازیم.
ما در این بخش، تعمیمی از لم {\eqref{lmm: (7.2) (1)}} را در گزارهٔ {\eqref{pro: Me-iif lmm(7.2)(1)}} ارائه نموده
و همچنین حدس‌هایی{\footnote{حدس {\eqref{conj: Me-no Alt-cycle Parallelism}}
و {\eqref{conj: Me-two Alt-cycle Parallelism}} و {\eqref{conj: Me-even Alt-cycle Parallelism}}}} در مورد
شرایط توازی قواعد دوتایی مطرح می‌نماییم.


در انتها، نگاهی کوتاه به رویکرد جبری نظریهٔ گراف در مورد مسأله مونتاژ ژن می‌اندازیم
و به حل دو مسألهٔ باز در این خصوص اشاره می‌نماییم.

برای آشنایی با اصطلاحات و مفاهیم نظریهٔ گراف که در این پروژه به‌کار‌گرفته شده است،
می‌توانید به کتاب‌های {\cite{Graph.Theory.Bondy.Murty2008fa}} و {\cite{Graph.Theory.Bondy.Murty2008}} 
و {\cite{west_introduction_2000}}، و برای
واژه‌ها به {\cite{glossary2}} و {\cite{glossary1}} مراجعه فرمایید.