Skip to content

DNA palindrome may have significant role in DNA replication that are found frequently in human cancer cells. Data Structures - Suffix Array, Longest Common prefix Array.

Notifications You must be signed in to change notification settings

bhaskar6f1/Pallindromic-Sequence-in-Nucleic-Acid

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Pallindromic-Sequence-in-Nucleic-Acid (Linear Time Algorithm)

  1. inv.c - This file generates the string complement pair of a given input string.

Command - a.) make inv b.) ./inv -input <input_file_name> -output <output_file_name>

  1. seqFinder.c - This file points out all the indices of the pattern, along with the indices of the gap, present in a string.

Command - a.) make seqFinder b.) ./SeqFinder -srt <srt_file_name_with_path> -lcp <lcp_file_name_with_path> -output <output_file_name_with_path>

Output Example:

Initial Final Count InitialGap FinalGap String

12308 12315 8 0 0 AAAATTTT

2099 2124 20 2109 2114 GTCCAAAGAGGAACAGCTCTTTGGAC

Time Complexity:

For constant "allowed gap value" and "number of total such sequences" the time complexity is O(n).

Explanation: It is O(stringLength * AllowedGap * size). However, the gap value is constant (default value is 10) and also the "number of total such sequences" is very less compared to the size of the string "n". That is why, we can ignore those values as they are negligible compared to the size of the string and thus, the time complexity becomes linear.

Acknowledgment: I would like to thank Dr.M.Ganapathiraju for her guidance in completing the project.

References:

  1. https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-12-12
  2. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3602881/
  3. https://www.ncbi.nlm.nih.gov/pubmed/15693744

About

DNA palindrome may have significant role in DNA replication that are found frequently in human cancer cells. Data Structures - Suffix Array, Longest Common prefix Array.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages