تبدیل باروز-ویلر: تفاوت میان نسخهها
کاربرد در بیو |
|||
خط ۱۰۲: | خط ۱۰۲: | ||
==کاربردها== |
==کاربردها== |
||
همان طور که پیش از این نیز ذکر شد، الگوریتم BWT در فشرده سازی کاربرد زیادی دارد. اما می توان در کاربردهای دیگری هم از آن استفاده کرد که یکی از آن ها [[تطبیق الگو]] می باشد. BWT یک روش سریع برای پیدا کردن الگوها در متن می باشد. از کاربردهای دیگر آن می توان به [[خوشه بندی]] اشاره کرد که در حوزه [[بینایی رایانهای]] و [[ترجمه ماشینی]] استفاده می شود. <ref>{{cite book |author=Adjeroh |title=The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching |url=https://doi.org/10.1007/978-0-387-78909-5_8 |location=Boston, MA |publisher= Springer US|page=265--303 |date=2008 |isbn=978-0-387-78909-5}}</ref> |
همان طور که پیش از این نیز ذکر شد، الگوریتم BWT در فشرده سازی کاربرد زیادی دارد. اما می توان در کاربردهای دیگری هم از آن استفاده کرد که یکی از آن ها [[تطبیق الگو]] می باشد. BWT یک روش سریع برای پیدا کردن الگوها در متن می باشد. از کاربردهای دیگر آن می توان به [[خوشه بندی]] اشاره کرد که در حوزه [[بینایی رایانهای]] و [[ترجمه ماشینی]] استفاده می شود. <ref>{{cite book |author=Adjeroh |title=The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching |url=https://doi.org/10.1007/978-0-387-78909-5_8 |location=Boston, MA |publisher= Springer US|page=265--303 |date=2008 |isbn=978-0-387-78909-5}}</ref> |
||
==BWT در بیوانفورماتیک== |
|||
ظهور [[تعیین توالی دیانای]] در اواخر سال ۲۰۰۰ میلادی، باعث شد که کاربرد دیگری از BWT نمایان شود. در تعیین توالی دیانای، [[دیانای]] به قطعات کوچک تری تقسیم می شود که به هر کدام یک خوانده(به انگلیسی:read) می گویند. در بسیاری از آزمایش ها نیاز است که این خوانده ها به [[ژنوم]] مرجعی تطبیق داده شوند. در راستای کاهش حافظه ی مورد نیاز برای [[همترازسازی توالی]]، الگوریتم های متنوعی استفاده شده اند(مانند [[Bowtie (sequence analysis)|Bowtie]],<ref name="Langmead2009">{{cite journal |vauthors=Langmead B, Trapnell C, Pop M, Salzberg SL |title=Ultrafast and memory-efficient alignment of short DNA sequences to the human genome |journal=Genome Biology |year=2009 |volume=10 |issue=3 |page=R25 |pmid=19261174 |doi=10.1186/gb-2009-10-3-r25 |pmc=2690996}}</ref> BWA,<ref name="Li, H2009">{{cite journal |vauthors=Li H, Durbin R |title=Fast and accurate short read alignment with Burrows–Wheeler Transform |journal=Bioinformatics |year=2009 |pmid=19451168 |volume=25 |issue=14 |pages=1754–1760 |doi=10.1093/bioinformatics/btp324 |pmc=2705234}}</ref> and SOAP2<ref name="Li, R2009">{{cite journal |author=Li R |title=SOAP2: an improved ultrafast tool for short read alignment |journal=Bioinformatics |year=2009 |pmid=19497933 |volume=25 |issue=15 |pages=1966–1967 |doi=10.1093/bioinformatics/btp336|display-authors=etal}}</ref>) که از BWT استفاده می کنند. |
|||
{{روشهای فشردهسازی}} |
{{روشهای فشردهسازی}} |
نسخهٔ ۲۴ ژوئیهٔ ۲۰۱۹، ساعت ۱۳:۴۱
این مقاله به هیچ منبع و مرجعی استناد نمیکند. |
تبدیل باروز-ویلر (به انگلیسی: Burrows–Wheeler transform or BWT) یک الگوریتم است که چیدمان حروف در کلمات را تغییر می دهد. ان روش برای فشردهسازی دادهها بسیار مناسب است. اگر متنی که می خواهیم آن را فشرده کنیم شامل حروف تکراری ترجیحاً پشت سر هم باشد می توان از روش های دیگر فشرده سازی نظیر کدبندی طول اجرا (به انگلیسی: Run-length encoding) استفاده کرد. اما در حالات دیگر روش BWT بسیار مناسب می باشد مخصوصاً اینکه BWT الگوریتمی برگشتپذیر است. یعنی میتوان متن فشرده سازی شده را به متن اولیه تبدیل کرد. در حقیقت این کار روشی است که فارغ از هر الگوریتم فشرده سازی که در آن استفاده می شود، با کمی محاسبات بیشتر میزان فشرده سازی را افزایش دهد. BWT توسط مایکل باروز و دیوید ویلر در سال ۱۹۹۴ معرفی شد، زمانی که باروز در یک شرکت به نام DEC Systems Research Center مشغول به کار بود.
الگوریتم بدست آوردن BWT
روش به دست آوردن BWT برای کلمهٔ EXAMPLE در شکل زیر نشان داده شده است. در ابتدا یک علامت مانند $ در انتهای آن قرار می دهیم تا بتوانیم کلمه را شیفت دورانی دهیم. خروجی های مربوط به شیفت در ستون سمت چپ آورده شده است. سپس در ستون سمت راست کلمات به دست آمده را به ترتیب حروف الفبا (به انگلیسی: Lexicographical order) مرتب می کنیم. ستون آخر که در شکل زیر به رنگ قرمز نمایش داده شده است، یعنی EXL$PAME همان (BWT(EXAMPLE می باشد.
شبه کد مربوط به این الگوریتم به شکل زیر می باشد:
function BWT (string s)
create a table, rows are all possible rotations of s
sort rows alphabetically
return (last column of the table)
الگوریتم BWT معکوس
تا قبل از این روشی که گفته شد برای فشرده سازی استفاده می شود. حال اگر BWT یک کلمه را داشته باشیم چگونه باید بفهمیم اصل آنچه بوده است؟ برای این کار ابتدا حروف را شماره گذاره میکنیم. چون ممکن است در متن حروف تکراری داشته باشیم. مثلاً در مثال خودمان خواهیم داشت: E1-X1-A1-M1-P1-L1-E2 و ۱$. برای بدست آوردن ماتریس مرتب شدهٔ اولیه ستوان آخر را که از نتیجهٔ فشرده سازی داریم. ستوان اول هم با مرتب کردن ستوان آخر بر اساس حروف الفبا به دست می آید. در ادامه به سطر اول نگاه می کنیم که ۱$ است. باید بفهمیم در کلمه اصلی بعد از این حرف چه حرفی قرار می گرفته است. با توجه به اینکه ما ماتریس را از طریق شیفت دورانی ساخته ایم پس اگر حرف ۱$ را در ستون آخر پیدا کرده و ببینیم در مقابل آن در سطر اول چه حرفی قرار دارد آن حرف، حرف بعدی ما در کلمه نهایی خواهد بود. همین کار را مدام انجام می دهیم تا کلمهٔ کامل به دست آید.[۱] برای درک بهتر به مثال زیر توجه کنید: همانطور که در بالا توضیح داده شد حرف بعد از ۱$ که X1 است را به دست آوردیم. حال به طریق مشابه می بینیم که X1 در کجای ستون آخر آمده است و حرف نظیر آن در ستون اول چیست؛ بنابراین می بینیم که مقابل آن A1 قرار دارد.
سپس A1 را در ستون آخر پیدا میکنیم و حرف نظیر آن در ستون اول را به عنوان حرف بعدی انتخاب می کنیم:
همینطور پیش می رویم تا سطر اول کامل شود:
سپس اعداد را حذف می کنیم و سطر اول را شیفت دورانی می دهیم تا $ در انتهای کلمه قرار بگیرد. اینگونه ما به کلمهٔ اولیه رسیده ایم:$EXAMPLE
شبه کد مربوط به این الگوریتم به شکل زیر است:
function inverseBWT (string s)
create empty table
'''repeat''' length(s) '''times'''
// first insert creates first column
insert s as a column of table before first column of the table
sort rows of the table alphabetically
return (row that ends with the 'EOF' character)
بهینه سازی
روش هایی برای پیاده ساز بهتر خود الگوریتم وجود دارد تا حافظه ی کمتری را اشغال کند. یا مثلا ما نیازی نداریم حرف EOF را به کلمه ورودی اضافه می کنیم بلکه می توانیم برای آن یک اشاره گر نگه داریم. توضیحات بیشتر این الگوریتم را می توان در [۲] مطالعه کرد.
نمونه پیادهسازی
کد مربوط به ساخت BWT به زبان پایتون در زیر آورده شده است:(برای درک بیشتر ۰۰۲\ , ۰۰۳\ به اسکی (استاندارد) مراجعه کنید. این دو کاراکتر مشخص کننده انتها و ابتدای کلمه هستند)
def bwt(s):
"""Apply Burrows-Wheeler transform to input string."""
assert "\002" not in s and "\003" not in s, "Input string cannot contain STX and ETX characters"
s = "\002" + s + "\003" # Add start and end of text marker
table = sorted(s[i:] + s[:i] for i in range(len(s))) # Table of rotations of string
last_column = [row[-1:] for row in table] # Last characters of each row
return "".join(last_column) # Convert list of characters into string
برنامهٔ مربوط به معکوس BWT هم به شکل زیر می باشد:
def ibwt(r):
"""Apply inverse Burrows-Wheeler transform."""
table = [""] * len(r) # Make empty table
for i in range(len(r)):
table = sorted(r[i] + table[i] for i in range(len(r))) # Add a column of r
s = [row for row in table if row.endswith("\003")][0] # Find the correct row (ending in ETX)
return s.rstrip("\003").strip("\002") # Get rid of start and end markers
روش زیر یک روش بهینه برای پیاده سازی BWT می باشد:
def bwt(s):
"""Apply Burrows-Wheeler transform to input string. Not indicated by a unique byte but use index list"""
# Table of rotations of string
table = [s[i:] + s[:i] for i in range(len(s))]
# Sorted table
table_sorted = table[:]
table_sorted.sort()
# Get index list of ((every string in sorted table)'s next string in unsorted table)'s index in sorted table
indexlist = []
for t in table_sorted:
index1 = table.index(t)
index1 = index1+1 if index1 < len(s)-1 else 0
index2 = table_sorted.index(table[index1])
indexlist.append(index2)
# Join last characters of each row into string
r = ''.join([row[-1] for row in table_sorted])
return r, indexlist
def ibwt(r,indexlist):
"""Inverse Burrows-Wheeler transform. Not indicated by a unique byte but use index list"""
s = ''
x = indexlist[0]
for _ in r:
s = s + r[x]
x = indexlist[x]
return s
چگونگی فشرده سازی
برای درک اینکه این الگوریتم چگونه به کمتر کردن حجم کمک میکند، متنی را در نظر بگیرید که در آن یک لغت خاص زیاد تکرار شده باشد مثلاً کلمه بیا، بعد از اجرا این تبدیل تمامی موارد تکرار شدن این کلمه در کنار هم مرتب میشوند و قرار میگیرند مثلاً به صورت «اب» که در این صورت میدانیم «ی» مربوط به این زیر رشته در آخر جمله است. پس تعداد زیادی ی پشت سر هم در آخر رشته تکرار میشود که این امر، کار فشردهسازی را برای بعضی الگوریتمهای فشردهسازی متدوال سادهتر میکند.
کاربردها
همان طور که پیش از این نیز ذکر شد، الگوریتم BWT در فشرده سازی کاربرد زیادی دارد. اما می توان در کاربردهای دیگری هم از آن استفاده کرد که یکی از آن ها تطبیق الگو می باشد. BWT یک روش سریع برای پیدا کردن الگوها در متن می باشد. از کاربردهای دیگر آن می توان به خوشه بندی اشاره کرد که در حوزه بینایی رایانهای و ترجمه ماشینی استفاده می شود. [۳]
BWT در بیوانفورماتیک
ظهور تعیین توالی دیانای در اواخر سال ۲۰۰۰ میلادی، باعث شد که کاربرد دیگری از BWT نمایان شود. در تعیین توالی دیانای، دیانای به قطعات کوچک تری تقسیم می شود که به هر کدام یک خوانده(به انگلیسی:read) می گویند. در بسیاری از آزمایش ها نیاز است که این خوانده ها به ژنوم مرجعی تطبیق داده شوند. در راستای کاهش حافظه ی مورد نیاز برای همترازسازی توالی، الگوریتم های متنوعی استفاده شده اند(مانند Bowtie,[۴] BWA,[۵] and SOAP2[۶]) که از BWT استفاده می کنند.
منابع
- ↑ Pavel Pevzner, Neil Jones (2004). An Introduction to Bioinformatics Algorithms. The MIT Press.
- ↑ Kutylowski, Miroslaw; Pacholski, Leszek (1999-08-18). Mathematical Foundations of Computer Science 1999: 24th International Symposium, MFCS'99 Szklarska Poreba, Poland, September 6-10, 1999 Proceedings (به انگلیسی). Springer Science & Business Media. ISBN 9783540664086.
- ↑ Adjeroh (2008). The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching. Boston, MA: Springer US. p. 265--303. ISBN 978-0-387-78909-5.
- ↑ Langmead B, Trapnell C, Pop M, Salzberg SL (2009). "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome". Genome Biology. 10 (3): R25. doi:10.1186/gb-2009-10-3-r25. PMC 2690996. PMID 19261174.
- ↑ Li H, Durbin R (2009). "Fast and accurate short read alignment with Burrows–Wheeler Transform". Bioinformatics. 25 (14): 1754–1760. doi:10.1093/bioinformatics/btp324. PMC 2705234. PMID 19451168.
- ↑ Li R; et al. (2009). "SOAP2: an improved ultrafast tool for short read alignment". Bioinformatics. 25 (15): 1966–1967. doi:10.1093/bioinformatics/btp336. PMID 19497933.
- مشارکتکنندگان ویکیپدیا. «Burrows–Wheeler transform». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۲۴ ژوئیه ۲۰۱۹.