A fast exact sequential algorithm for the partial digest problem
<h3>Background</h3><p dir="ltr">Restriction site analysis involves determining the locations of restriction sites after the process of digestion by reconstructing their positions based on the lengths of the cut DNA. Using different reaction times with a single enzyme to c...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | |
| منشور في: |
2016
|
| الموضوعات: | |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513556481835008 |
|---|---|
| author | Mostafa M. Abbas (17058093) |
| author2 | Hazem M. Bahig (19730848) |
| author2_role | author |
| author_facet | Mostafa M. Abbas (17058093) Hazem M. Bahig (19730848) |
| author_role | author |
| dc.creator.none.fl_str_mv | Mostafa M. Abbas (17058093) Hazem M. Bahig (19730848) |
| dc.date.none.fl_str_mv | 2016-12-22T03:00:00Z |
| dc.identifier.none.fl_str_mv | 10.1186/s12859-016-1365-2 |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/A_fast_exact_sequential_algorithm_for_the_partial_digest_problem/27094639 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Biological sciences Bioinformatics and computational biology Restriction site analysis Digestion process Partial digest problem DNA Bioinformatics algorithm Breadth first search |
| dc.title.none.fl_str_mv | A fast exact sequential algorithm for the partial digest problem |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <h3>Background</h3><p dir="ltr">Restriction site analysis involves determining the locations of restriction sites after the process of digestion by reconstructing their positions based on the lengths of the cut DNA. Using different reaction times with a single enzyme to cut DNA is a technique known as a partial digestion. Determining the exact locations of restriction sites following a partial digestion is challenging due to the computational time required even with the best known practical algorithm.</p><h3>Results</h3><p dir="ltr">In this paper, we introduce an efficient algorithm to find the exact solution for the partial digest problem. The algorithm is able to find all possible solutions for the input and works by traversing the solution tree with a breadth-first search in two stages and deleting all repeated subproblems. Two types of simulated data, random and Zhang, are used to measure the efficiency of the algorithm. We also apply the algorithm to real data for the Luciferase gene and the <i>E. coli</i> K12 genome.</p><h3>Conclusion</h3><p dir="ltr">Our algorithm is a fast tool to find the exact solution for the partial digest problem. The percentage of improvement is more than 75% over the best known practical algorithm for the worst case. For large numbers of inputs, our algorithm is able to solve the problem in a suitable time, while the best known practical algorithm is unable.</p><h2>Other Information</h2><p dir="ltr">Published in: BMC Bioinformatics<br>License: <a href="https://creativecommons.org/licenses/by/4.0/deed.en" rel="noreferrer noopener" target="_blank">https://creativecommons.org/licenses/by/4.0/</a> <br>See article on publisher's website: <a href="https://dx.doi.org/10.1186/s12859-016-1365-2" target="_blank">https://dx.doi.org/10.1186/s12859-016-1365-2</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_d3a564d7c10a5a9c460f7fd9b5caea8d |
| identifier_str_mv | 10.1186/s12859-016-1365-2 |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/27094639 |
| publishDate | 2016 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | A fast exact sequential algorithm for the partial digest problemMostafa M. Abbas (17058093)Hazem M. Bahig (19730848)Biological sciencesBioinformatics and computational biologyRestriction site analysisDigestion processPartial digest problemDNABioinformatics algorithmBreadth first search<h3>Background</h3><p dir="ltr">Restriction site analysis involves determining the locations of restriction sites after the process of digestion by reconstructing their positions based on the lengths of the cut DNA. Using different reaction times with a single enzyme to cut DNA is a technique known as a partial digestion. Determining the exact locations of restriction sites following a partial digestion is challenging due to the computational time required even with the best known practical algorithm.</p><h3>Results</h3><p dir="ltr">In this paper, we introduce an efficient algorithm to find the exact solution for the partial digest problem. The algorithm is able to find all possible solutions for the input and works by traversing the solution tree with a breadth-first search in two stages and deleting all repeated subproblems. Two types of simulated data, random and Zhang, are used to measure the efficiency of the algorithm. We also apply the algorithm to real data for the Luciferase gene and the <i>E. coli</i> K12 genome.</p><h3>Conclusion</h3><p dir="ltr">Our algorithm is a fast tool to find the exact solution for the partial digest problem. The percentage of improvement is more than 75% over the best known practical algorithm for the worst case. For large numbers of inputs, our algorithm is able to solve the problem in a suitable time, while the best known practical algorithm is unable.</p><h2>Other Information</h2><p dir="ltr">Published in: BMC Bioinformatics<br>License: <a href="https://creativecommons.org/licenses/by/4.0/deed.en" rel="noreferrer noopener" target="_blank">https://creativecommons.org/licenses/by/4.0/</a> <br>See article on publisher's website: <a href="https://dx.doi.org/10.1186/s12859-016-1365-2" target="_blank">https://dx.doi.org/10.1186/s12859-016-1365-2</a></p>2016-12-22T03:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.1186/s12859-016-1365-2https://figshare.com/articles/journal_contribution/A_fast_exact_sequential_algorithm_for_the_partial_digest_problem/27094639CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/270946392016-12-22T03:00:00Z |
| spellingShingle | A fast exact sequential algorithm for the partial digest problem Mostafa M. Abbas (17058093) Biological sciences Bioinformatics and computational biology Restriction site analysis Digestion process Partial digest problem DNA Bioinformatics algorithm Breadth first search |
| status_str | publishedVersion |
| title | A fast exact sequential algorithm for the partial digest problem |
| title_full | A fast exact sequential algorithm for the partial digest problem |
| title_fullStr | A fast exact sequential algorithm for the partial digest problem |
| title_full_unstemmed | A fast exact sequential algorithm for the partial digest problem |
| title_short | A fast exact sequential algorithm for the partial digest problem |
| title_sort | A fast exact sequential algorithm for the partial digest problem |
| topic | Biological sciences Bioinformatics and computational biology Restriction site analysis Digestion process Partial digest problem DNA Bioinformatics algorithm Breadth first search |