پویش: الگوریتمی جدید برای یافتن موتیف در شبکه های زیستی

اخیراً توجه زیادی بر روی موتیف ها به منظور درک بهتر ساختار شبکه های پیچیده، جلب شده است. موتیف ها، زیرشبکه های کوچک همبندی هستند که در شبکه مورد بررسی با فراوانی بالاتری نسبت به شبکه های تصادفی مشاهده می شوند. روش های موجود تشخیص موتیف های شبکه برافزایش کارایی محاسباتی تمرکز دارد. بااین حال، تشخیص موتیف های شبکه چالش های بزرگی را ازنظر پیچیدگی فضایی و محاسباتی نشان می دهد. در این مقاله، روشی جدید برای کاوش موتیف های یک شبکه ارائه شده است. در ابتدا همه زیرگراف ها را می توان با اضافه کردن تدریجی یال ها و گره ها و با استفاده از روش عقب گرد و بر اساس ماتریس متناظر شمارش کرد. سپس ماتریس متناظر استانداردشده و زیرگراف همریخت به طور یکتا و در ترکیب با سه تایی متقارن (1-, 0, 1) که می تواند عناصر را در ماتریس متناظر شبیه سازی کند، مشخص می شود. روش پیشنهادی پیچیدگی شمارش زیرگراف ها را کاهش می دهد و راه حلی کاراتر را برای کاوش موتیف ارائه می کند. نتایج به دست آمده نشان می دهد که روش پیشنهادی سرعت بالاتر و قابلیت های بیشتری نسبت به روش های مشابه دارد.

Keywords:

موتیف , شبکه های زیستی , همریختی , تکنیک عقب گرد , زیرگراف