Skip to content

Files

Latest commit

94e0644 · Mar 20, 2024

History

History
196 lines (134 loc) · 13 KB

anonymous-format.md

File metadata and controls

196 lines (134 loc) · 13 KB
  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

علیرضا همیشه علاقه زیادی به بیوانفورماتیک (+) داشت. او دوست داشت با داده‌های ژنتیکی کار کند و الگوریتم‌های پیچیده و متنوعی را برای تحلیل آنها طراحی کند. وقتی او فارغ‌التحصیل شد، توانست در یک شرکت معتبر بیوانفورماتیک شغلی پیدا کند. این شرکت به ساخت درخت‌های فیلوژنتیک (+) برای مقایسه گونه‌های مختلف موجودات مشغول بود.

علیرضا روز اول کارش را با اشتیاق رفت. او مدیر پروژه‌اش را ملاقات کرد و مدیرش به او گفت که وظیفه‌اش چیست: علیرضا باید توالی‌های مربوط به گونه‌های مختلف را از پایگاه داده NCBI (+) دانلود کرده و آنها را با نرم‌افزار مخصوص شرکت تحلیل می‌کرد. علیرضا تصور می‌کرد که این کار ساده است. او قبلاً با NCBI کار کرده بود و می‌دانست که توالی‌های گونه‌ها را می‌توان به فرمت FASTA دانلود کرد. FASTA یک فرمت استاندارد برای نمایش توالی‌های دی‌ان‌ای (+) یا پروتئین (+) است.

اما وقتی علیرضا نرم‌افزار را باز کرد، چشمانش از تعجب گرد شد! نرم‌افزار به‌جای FASTA فقط فرمت PHYLIP را قبول می‌کرد. PHYLIP یک فرمت دیگر برای نمایش توالی‌های دی‌ان‌ای یا پروتئین است، اما با ساختاری متفاوت. علیرضا هیچ‌گاه با PHYLIP کار نکرده بود و نمی‌دانست چگونه باید FASTA را به PHYLIP تبدیل کند.

او ابتدا سعی کرد در اینترنت جست‌وجو کند. چندین سایت و وبلاگ را پیدا کرد، اما هیچ‌کدام جواب مناسبی به او ندادند. بعضی از آنها نصب نرم‌افزارهای جانبی را پیشنهاد می‌کردند، که علیرضا اجازه نصب آنها را نداشت. بعضی دیگر کدهایی به زبان‌های پایتون یا پرل را نشان می‌دادند، که شرکت اجازه استفاده از آنها را نمی‌داد. علیرضا فقط می‌توانست با C++ برنامه‌نویسی کند.

علیرضا ناامید شد. او فکر کرد که شاید بهتر است از مدیر پروژه‌اش کمک بخواهد. اما نمی‌خواست روز اول کارش ناتوان به‌نظر برسد. او خودش می‌خواست مشکل را حل کند. او یادش افتاد که یک دوست قدیمی به نام حمیدرضا دارد. حمیدرضا با علیرضا در دانشگاه آشنا شده بود. علیرضا تصمیم گرفت به او پیام بدهد و بخواهد برایش یک برنامه C++ بنویسد که FASTA را به PHYLIP تبدیل کند.

علیرضا پیام خود را فرستاد و منتظر جواب دوستش ماند. او امیدوار بود که حمیدرضا بتواند به او کمک کند و شغل جدیدش را نجات دهد.

پاسخ حمیدرضا خیلی زود آمد:

«سلام علیرضا، چطوری؟ من خبر نداشتم که شغل جدیدی پیدا کرده‌ای. تبریک می‌گم. اما چرا از من کمک می‌خوای؟ تو خودت بیوانفورماتیک رو خوب بلدی. من اصلاً نمی‌دونم FASTA و PHYLIP چی هستن؟ اینا چه ربطی به C++ دارن؟»

علیرضا سعی کرد به ساده‌ترین شکل ممکن به حمیدرضا پاسخ دهد:

«سلام حمیدرضا، ممنون. من از تو کمک می‌خوام چون تو C++ رو خیلی خوب بلدی. FASTA و PHYLIP دو فرمت برای نمایش توالی‌های دی‌ان‌ای یا پروتئین هستن. دی‌ان‌ای و پروتئین مولکول‌هایی هستن که حامل اطلاعات ژنتیکی هستند. توالی یعنی ترتیب نوکلئوتیدها (+) در دی‌ان‌ای یا آمینواسیدها (+) در پروتئین. نوکلئوتیدها و آمینواسیدها با حروف الفبای لاتین نشان داده می‌شوند. برای مثال، توالی (+) یک دی‌ان‌ای ممکن است به شکل ATCGGCTA باشد و توالی یک پروتئین ممکن است به شکل MGLWKR باشد.

فرمت FASTA این‌طور است که در آن نام و اطلاعات اضافی مربوط به توالی با علامت > شروع می‌شود. نام توالی با مشاهده اولین کاراکتر فاصله پایان می‌یابد. بعد از آن، محتوای توالی در چند خط زیر آن می‌آید. برای مثال، فایل FASTA شامل دو توالی دی‌ان‌ای ممکن است به شکل زیر باشد:

>Human insulin gene
ATGCCCTGTGGATGCGCCTCCTGCCCCTGC
TGGCGCTGCTGGCCCTCTGGGGACCTGAAC
GACTACTAGCCTCATCAATACGACTAGATA
GAGATCCGTACAGAGAG

>Rat insulin gene
ATGCCAGTGTGGATGCACCACCATGCCATC
AAGCAGGTCAAGGCCAACGACCCCTTGCAC
ACGATTTATATATACCCCAGATACCCGTGG
AGCGACTCCCCCCCACA

فرمت PHYLIP این‌طور است که اول یک خط شامل تعداد توالی‌ها و طول محتوای هر توالی می‌آید. بعد از آن، هر خط شامل نام و ۵۰ کاراکتر اول یک توالی است. نام توالی باید حداکثر ۱۰ کاراکتر باشد و سمت راست آن با فضای خالی پر شود. چنانچه نام توالی بیشتر از ۱۰ کاراکتر بود فقط ۱۰ کاراکتر اولش به‌عنوان نام آن در نظر گرفته می‌شود. سپس یک فاصله می‌آید و بعد ۵۰ کاراکتر اول محتوای توالی در بسته‌های ۱۰ کاراکتری پس از آن می‌آید. برای مثال، فایل PHYLIP متناظر با فایل FASTA بالا به شکل زیر است:

 2 107
Human      ATGCCCTGTG GATGCGCCTC CTGCCCCTGC TGGCGCTGCT GGCCCTCTGG 
Rat        ATGCCAGTGT GGATGCACCA CCATGCCATC AAGCAGGTCA AGGCCAACGA 

           GGACCTGAAC GACTACTAGC CTCATCAATA CGACTAGATA GAGATCCGTA 
           CAGAGAG 

           CCCCTTGCAC ACGATTTATA TATACCCCAG ATACCCGTGG AGCGACTCCC 
           CCCCACA 

در ضمن همون‌طور که توی مثال بالا می‌بینی اگر توالی‌ها تعداد بیشتری کاراکتر داشتن متناظر هر توالی و به همون شکل و ترتیب در خطوط بعدی نوشته می‌شن.

حالا من می‌خوام یک برنامه C++ بنویسم که فایل FASTA را به PHYLIP تبدیل کنه. تو می‌تونی به من کمک کنی؟»

حمیدرضا گفت:

«آره، فکر کنم. دقیقاً بگو برنامه باید چکار بکنه؟»

علیرضا گفت:

«خیلی ممنون. خب، اول باید فایل FASTA ورودی رو باز کنی و تعداد و طول توالی‌ها رو پیدا کنی. بعد باید نام و محتوای هر توالی رو جداسازی و در متغیرهای مناسب ذخیره کنی. در نهایت باید نام و محتوای هر توالی رو با قالب مناسبی که در پیام قبل توضیح دادم در فایل PHYLIP خروجی بنویسی. آدرس فایل FASTA و آدرس فایل PHYLIP به‌ترتیب در خط اول و دوم ورودی به برنامه داده می‌شن.»

حمیدرضا که سرش شلوغ بود دوست نداشت دوستش را تنها بگذارد. او پاسخ داد:

«خب، سخت به‌نظر نمی‌رسه. چند نمونه فایل FASTA و فایل PHYLIP برای من بفرست و من شروع می‌کنم.»

علیرضا با اشتیاق و به‌سرعت فایل‌های نمونه را برای حمیدرضا فرستاد و منتظر ماند.

حالا ساعتی می‌گذرد که حمیدرضا شروع به نوشتن برنامه کرده است اما باگ‌های مختلف او را کلافه کرده است و دیگر فرصتی برای اتلاف وقت ندارد. از شما به‌عنوان یکی از دوستان خوب و ماهرش می‌خواهد این برنامه را بنویسید تا برای دوستش بفرستد و شغل او را نجات دهد. با توجه به اینکه تا همین لحظه سه نفر درگیر این کد نه‌چندان دشوار شده‌اند از شما می‌خواهیم خودتان این کد را بنویسید و آن را این‌قدر دست به دست نکنید!

ورودی

در خط اول ورودی آدرس فایل FASTA (شامل پسوند آن) و در خط دوم ورودی آدرس فایل PHYLIP (شامل پسوند آن) می‌آید. این امکان وجود دارد که آدرس‌ها شامل کاراکتر فاصله باشند. همچنین فایل FASTA ورودی ممکن است موجود نباشد اما تضمین می‌شود که همه پوشه‌های پدر فایل PHYLIP موجود هستند.

خروجی

تنها خروجی برنامه شما فایل PHYLIP است که باید در آدرسی که در ورودی داده شده است ذخیره شود.

با این حال در صورتی که هر کدام از خطاهای زیر رخ داد با استفاده از دستور cerr پیام مربوط به آن را در خروجی ترمینال چاپ کنید و اجرای برنامه را به پایان برسانید.

اولویت دلیل خطا پیام خطا
۱ فایل FASTA ورودی وجود ندارد. FASTA file does not exist!
۲ طول توالی‌ها یکسان نیست. The sequences are not the same length!

مثال

جهت ساده‌سازی، مثال‌ها و نیز نمونه‌هایی که برای داوری استفاده می‌شوند به‌صورت مصنوعی تولید شده‌اند و یا به‌طور وسواس‌گونه‌ای از بین میلیون‌ها توالی انتخاب شده‌اند. پردازش توالی‌های بسیار طولانی و فایل‌های حجیم خارج از اهداف این سؤال است.

ورودی نمونه ۱

tests/in/1.fasta
tests/out/1.phy

که در آن فایل tests/in/1.fasta به شکل زیر است:

>Snake Serpentes
agctatcgacgccctagcgcctt
agactcttccaaa
gttaaacaaccgttt
gatg

>Fish Vertebrata
gcctcaaacc
gatctttgactagctccaaatgcccatgc
ttatactggcgtgact

خروجی نمونه ۱

تنها خروجی برنامه فایل tests/out/1.fasta است که به شکل زیر می‌باشد:

 2 55
Snake      agctatcgac gccctagcgc cttagactct tccaaagtta aacaaccgtt 
Fish       gcctcaaacc gatctttgac tagctccaaa tgcccatgct tatactggcg 

           tgatg 

           tgact 

ورودی نمونه ۲

organisms.fasta
organisms.phy

که در آن فایل organisms.fasta محتویات زیر را دارد:

>Milesia
MSPQRDRINAFYKDNPHPKGSRIVINREHLMIDRP
DKLRMESKRSRAVV

>Parastratiosphecomyia
DQYCADVAAEELMNALVNSTLLETRTTNQFLAVSS
NLSVEH

خروجی نمونه ۲

با توجه اینکه طول توالی‌های موجود در فایل ورودی یکسان نیست خطای ۲ در خروجی ترمینال چاپ می‌شود:

The sequences are not the same length!

ورودی نمونه ۳

db/viruses.fasta
db/viruses.phy

که در آن فایلی با آدرس db/viruses.fasta وجود ندارد.

خروجی نمونه ۳

با توجه به اینکه فایل ورودی موجود نیست خطای ۱ در خروجی ترمینال چاپ می‌شود:

FASTA file does not exist!