dynamic programming
در نشریات گروه پزشکی-
Biolmpacts, Volume:11 Issue: 4, Jul 2021, PP 271 -279Introduction
Similarity analysis of protein structure is considered as a fundamental step to give insight into the relationships between proteins. The primary step in structural alignment is looking for the optimal correspondence between residues of two structures to optimize the scoring function. An exhaustive search for finding such a correspondence between two structures is intractable.
MethodsIn this paper, a hybrid method is proposed, namely GADP-align, for pairwise protein structure alignment. The proposed method looks for an optimal alignment using a hybrid method based on a genetic algorithm and an iterative dynamic programming technique. To this end, the method first creates an initial map of correspondence between secondary structure elements (SSEs) of two proteins. Then, a genetic algorithm combined with an iterative dynamic programming algorithm is employed to optimize the alignment.
ResultsThe GADP-align algorithm was employed to align 10 ‘difficult to align’ protein pairs in order to evaluate its performance. The experimental study shows that the proposed hybrid method produces highly accurate alignments in comparison with the methods using exactly the dynamic programming technique. Furthermore, the proposed method prevents the local optimal traps caused by the unsuitable initial guess of the corresponding residues.
ConclusionThe findings of this paper demonstrate that employing the genetic algorithm along with the dynamic programming technique yields highly accurate alignments between a protein pair by exploring the global alignment and avoiding trapping in local alignments.
Keywords: Bioinformatics, Protein structure alignment, Genetic algorithm, Dynamic programming -
مقدمهشبکیه، داخلی ترین بافت چشم است و به کمک عصب بینایی اطلاعات تصویری را به مغز ارسال می نماید. این بخش از چشم، ساختار لایه ای دارد و طراحی روشی که بتواند بدون تاثیر گرفتن از نوع اختلال تصویر و میزان آن و همچنین پایین بودن کنتراست تصویر، مرزهای لایه ها را به درستی مشخص نماید، از اهمیت فراوانی برخوردار می باشد. در این مطالعه، روش تلفیقی از دو روش تجزیه و تحلیل ریخت شناسی (MCA یا Morphological component analysis) و برنامه نویسی پویا (DP یا Dynamic programming) برای بخش بندی اتوماتیک شش لایه ی زیرین شبکیه به کار گرفته شد.روش هاپایگاه داده شامل 55 نمونه ی اخذ شده از افراد طبیعی با استفاده از دستگاه TOPCON-OCT-1000 بود. این مطالعه، در دو مرحله صورت گرفت. برای تجزیه و تحلیل ریخت شناسی، دیکشنری هر تصویر با استفاده از خوشه بندی برداری به کمک مقادیر ویژه (K-SVD) محاسبه گردید و سپس روش MCA، روی دیکشنری های حاصل شده اعمال گردید و بخش های کارتون و بافت تصویر با انتخاب پایه های مناسب تفکیک شد. بخش بندی به روش DP در تصویر کارتون اجرا گردید و سطوح Retinal pigment epithelium (RPE)، Verhoeff''s memberane (VM)، Outer segment layer (OSL)، Inner collagenous layer (ICL)، Inner synaptic layer (ISL) و Outer limiting membrane (OLM) مشخص شدند.یافته هابا مقایسه ی نتایج به دست آمده با استانداردهای موجود، مشاهده شد که کمترین خطا، مربوط به سطح OSL با مقدار خطای 167/0 ± 030/0 بود. میزان خطای سطوح RPE، VM، ICL، ISL و OLM به ترتیب 33/0 ± 66/0-، 31/0 ± 59/0-، 49/0 ± 00/1-، 61/0 ± 72/1- و 51/0 ± 05/1- بود.نتیجه گیریتجزیه و تحلیل ریخت شناسی به کمک روش DP، می تواند به صورت یک روش اتوماتیک در بخش بندی شش لایه ی زیرین شبکیه عمل کند و بدون نیاز به انجام پیش پردازش، از صحت قابل قبولی در نتایج بخش بندی برخوردار است.کلید واژگان: بخش بندی، برنامه نویسی پویا، تجزیه و تحلیل ریخت شناسیBackgroundRetina is the innermost tissue in human eye which sends visual information to the brain by means of optic nerve. Designing an intra-retinal layer segmentation method which can detect the retina surfaces properly in the presence of noise and lack of contrast is an important step in ophthalmology. In this study the combination of morphological component analysis (MCA) and dynamic programming (DP) is used automatically for segmentation of optical coherence tomography (OCT) images.MethodsData set for this study was 55 samples which were taken from normal people by Topcon OCT-1000. This study had two phases. In MCA phase the image dictionary was created by clustering with eigenvalues (k-SVD), and then the image was decomposed to cartoon and texture parts by selecting proper bases. In the second phase segmentation was done by the dynamic programming (DP) method on cartoon part and the retinal pigment epithelium (RPE), Verhoeff's memberane (VM), outer segment layer (OSL), inner collagenous layer (ICL), inner synaptic layer (ISL), and outer limiting membrane (OLM) layers were detected.
Findings: Comparing the obtained results with gold standard (manual segmentation) shows that minimum error belongs to OSL surface and its error in the form of mean ± SD (standard derivation) is 0.030 ± 0.167. For other surfaces the error is calculated in this way from left to right for RPE, VM, ICL, ISL, OLM: 0.66 ± 0.33, -0.59 ± 0.31, -1.00 ± 0.49, -1.72 ± 0.61, -1.05 ± 0.51.ConclusionMCA in combination with DP can work as an automatic method for six lower intra retina layer's segmentation with acceptable accuracy. One of the main advantages of this method is omitting preprocessing phase for segmentation.Keywords: Segmentation, Dynamic programming, Morphological component analysis -
مقدمه
از Enhanced depth imaging optical coherence tomography (EDI-OCT) برای تصویرگیری دقیق از لایه ی کروئید، که شامل بالاترین میزان جریان خون در چشم است و در بیماری های متعددی مانند پولیپ کروئیدی، تومور کروئیدی و تغییرات آرترو اسکلروتیک مویرگی تحت تاثیر قرار می گیرد، استفاده می گردد. از آن جایی که حجم زیادی از اطلاعات در چنین تصاویری نهفته است، تحلیل غیر اتوماتیک این داده ها برای چشم پزشک در حد ناممکن می باشد. هدف اصلی برای بخش بندی اتوماتیک این تصاویر، کمک به چشم پزشکان در تشخیص بیماری های وابسته به چشم بود.
روش هاداده های این طرح شامل داده های اخذ شده از دستگاه Heidelberg 3D OCT-HRA2-KT بود. برای بررسی الگوریتم از 50 داده استفاده شد. سپس، با استفاده از الگوریتم تشخیص مرزی، به عنوان برنامه نویسی پویا، مرز لایه ی اپیتلیوم رنگدانه ای شبکیه (RPE یا Retinal pigmented epithelium) و با پیدا کردن بیشینه ی گرادیان در پایین این لایه، مرز BM (Bruch’s membrane) استخراج شد. در مرحله ی بعد، با به کار گیری مجدد الگوریتم برنامه نویسی پویا مرز کروئید استخراج گردید.
یافته هاالگوریتم پیشنهادی در مقایسه با تفکیک دستی برای استخراج BM دارای خطای بدون علامت برابر با 91/0 ± 71/1 پیکسل و برای استخراج کروئید دارای خطایی برابر 11/4 ± 48/10 پیکسل بود. برای ارزیابی، روش پیشنهادی با الگوریتم k متوسط مقایسه شد که با میزان P بسیار کوچکتر از 001/0 بهبود چشمگیری را نشان داد.
نتیجه گیریتا کنون آنالیزهای اتوماتیک زیادی در زمینه ی تفکیک کروئید ارائه نشده است و روش های انجام شده به طور عمده بر روی تفکیک دستی متمرکز شده اند. در صورتی که در این مطالعه، از یک روش سریع و اتوماتیک برای تفکیک ناحیه ی کروئید استفاده شد.
کلید واژگان: EDI، OCT، کروئید، برنامه نویسی پویاBackgroundEnhanced depth imaging optical coherence tomography images (EDI-OCT) is used for detailed imaging of the choroid layer that contains the highest amount of blood flow in the eye and is affected in several diseases such as choroidal polyps, age-related degeneration and central serous chorioretinopathy. Choroidal segmentation is really important, but the manual segmentation is time consuming and encounters difficulties when large numbers of data is available. Since a large amount of information is available in the images, non-automated and visual analysis of data is almost impossible for the ophthalmologist. The main goal of automatic segmentation was to help the ophthalmologists in the diagnosis and monitoring diseases related to the eye.
MethodsThe data used in this project was obtained from the Heidelberg OCT-HRA2-KT instrument. Fifty 2 dimensional data were used to evaluate the algorithm. In this study, the retinal pigment epithelium (RPE) and choroid was segmented using a boundary detection algorithm named dynamic programming.
FindingsThe proposed algorithm was compared with the manual segmentation and the results showed an unsigned error of 1.71 ± 0.93 pixels for retinal pigmented epithelium (RPE) extraction and 10.48 ± 4.11 pixels for choroid detection. It showed significant improvements over other approaches like k-means method.
ConclusionA few automated methods are applied in the choroid segmentation and most of the studies were mainly focused on the manual separation. In this study, a fast and automated method was provided for the segmentation of choroid area.
Keywords: Enhanced depth imaging optical coherence tomography images (EDI, OCT), Choroid, Dynamic programming
- نتایج بر اساس تاریخ انتشار مرتب شدهاند.
- کلیدواژه مورد نظر شما تنها در فیلد کلیدواژگان مقالات جستجو شدهاست. به منظور حذف نتایج غیر مرتبط، جستجو تنها در مقالات مجلاتی انجام شده که با مجله ماخذ هم موضوع هستند.
- در صورتی که میخواهید جستجو را در همه موضوعات و با شرایط دیگر تکرار کنید به صفحه جستجوی پیشرفته مجلات مراجعه کنید.