Data Structure

Data Structure & Algorithms

The goal of this project is to explore an advanced theoretical topic in Dynamic programming algorithm design related to the DNA Sequence matching. Read several materials related to the topic and summarize concepts, find three typical algorithms, choose one of the algorithms and implement with C++ code.

1) Project Report: use attached template

1. Project title & Author information

2. Abstract (150 words)

. A brief summary of the proposal

3. Introduction (1 pages)

. Identify what works is to be done

4. Typical Algorithms (4~5 pages)

. Background information to educate the reader

. Relevance of importance of problem

5. Detailed Algorithm analysis (1 ~2 pages)

6. Experimental Results (1~2 pages)

7. Conclusions (1 Pages)

Reference: MLA citation

2) Final Project Demonstration:

Powerpoint slides about the project:

Each group or individual must prepare a 12 ~ 20 Minutes presentation that summarize the result of their project.

3) Project Implementation:

In this stage, you should provide your source code (C++) that you have proposed and state time complexity of your algorithm.

Sample Data

Download the DNA from this wbsite:

https://hpc.csiro.au/users/317836/KELLY/BASE_Albany/reveg_16S/picrust/97_otus.fasta

>OTU_1111883

GCTGGCGGCGTGCCTAACACATGTAAGTCGAACGGGACTGGGGGCAACTCCAGTTCAGTGGCAGACGGGTGCGTAACACGTGAGCAACTTGTCCGACGGCGGGGGATAGCCGGCCCAACGGCCGGGTAATACCGCGTACGCTCGTTTAGGGACATCCCTGAATGAGGAAAGCCGTAAGGCACCGACGGAGAGGCTCGCGGCCTATCAGCTAGTTGGCGGGGTAACGGCCCACCAAGGCGACGACGGGTAGCTGGTCTGAGAGGATGGCCAGCCACATTGGGACTGAGACACGGCCCAGACTCCTACGGGAGGCAGCAGTGGGGAATCTTGCGCAATGGCCGCAAGGCTGACGCAGCGACGCCGCGTGTGGGATGACGGCCTTCGGGTTGTAAACCACTGTCGGGAGGAACGAATACTCGGCTAGTCCGAGGGTGACGGTACCTCCAAAGGAAGCACCGGCTAACTCCGTGCCAGCAGCCGCGGTAATACGGAGGGTGCGAGCGTTGTCCGGAATCACTGGGCGTAAAGGGCGCGTAGGTGGCCCGTTAAGTGGCTGGTGAAATCCCGGGGCTCAACTCCGGGGCTGCCGGTCAGACTGGCGAGCTAGAGCACGGTAGGGGCAGATGGAATTCCCGGTGTAGCGGTGGAATGCGTAGATATCGGGAAGAATACCAGTGGCGAAGGCGTTCTGCTGGGCCGTTGCTGACACTGAGGCGCGACAGCGTGGGGAGCAAACAGGATTAGATACCCTGGTAGTCCACGCCGTAAACGATGGACACTAGACGTCGGGGGGAGCGACCCTCCCGGTGTCGTCGCTAACGCAGTAAGTGTCCCGCCTGGGGAGTACGGCCGCAAGGCTGAAACTCAAAGGAATTGACGGGGGCCCGCACAAGCGGTGGAGCATGTGGTTTAATTCGAAGCAACGCGAAGAACCTTACCTGGGCTTGACATGCTGGTGCAAGCCGGTGGAAACATCGGCCCCTCTTCGGAGCGCCAGCACAGGTGCTGCATGGCTGTCGTCAGCTCGTGTCGTGAGATGTTGGGTTAAGTCCCGCAACGAGCGCAACTCTCGCTCCCAGTTGCCAGCGGTTCGGCCGGGGACTCTGGGGGGACTGCCGGCGTTAAGCCGGAGGAAGGTGGGGACGACGTCAAGTCATCATGGCCCTTACGTCCAGGGCGACACACGTGCTACAATGCCTGGTACAGCGCGTCGCGAACTCGCAAGAGGGAGCCAATCGCCAAAAGCCGGGCTAAGTTCGGATTGTCGTCTGCAACTCGACGGCATGAAGCCGGAATCGCTAGTAATCGCGGATCAGCCACGCCGCGGTGAATACGTTCCCGGGCCTTGTACACACCGCCCGTCACGCCATGGAAGCCGGAGGGACCCGAAACCGGTGGGCCAACCGCAAGGGGGCAGCCGTCTAAGGT

>OTU_1111882

AGAGTTTGATCATGGCTCAGGATGAACGCTAGCGGCAGGCCTAACACATGCAAGTCGAGGGGTAGAGGCTTTCGGGCCTTGAGACCGGCGCACGGGTGCGTAACGCGTATGCAATCTGCCTTGTACTAAGGGATAGCCCAGAGAAATTTGGATTAATACCTTATAGTATATAGATGTGGCATCACATTTCTATTAAAGATTTATCGGTACAAGATGAGCATGCGTCCCATTAGCTAGTTGGTATGGTAACGGCATACCAAGGCAATGATGGGTAGGGGTCCTGAGAGGGAGATCCCCCACACTGGTACTGAGACACGGACCAGACTCCTACGGGAGGCAGCAGTGAGGAATATTGGTCAATGGGCGCAAGCCTGAACCAGCCATGCCGCGTGCAGGATGACGGTCCTATGGATTGTAAACTGCTTTTGTACGGGAAGAAACACTCCTACGTGTAGGGGCTTGACGGTACCGTAAGAATAAGGATCGGCTAACTCCGTGCCAGCAGCCGCGGTAATACGGAGGATCCAAGCGTTATCCGGAATCATTGGGTTTAAAGGGTCCGTAGGCGGTTTTATAAGTCAGTGGTGAAATCCGGCAGCTCAACTGTCGAACTGCCATTGATACTGTAGAACTTGAATTACTGTGAAGTAACTAGAATATGTAGTGTAGCGGTGAAATGCTTAGATATTACATGGAATACCAATTGCGAAGGCAGGTTACTAACAGTATATTGACGCTGATGGACGAAAGCGTGGGGAGCGAACAGGATTAGATACCCTGGTAGTCCACGCCGTAAACGATGGATACTAGCTGTTTGGCAGCAATGCTGAGTGGCTAAGCGAAAGTGTTAAGTATCCCACCTGGGGAGTACGAACGCAAGTTTGAAACTCAAAGGAATTGACGGGGGCCCGCACAAGCGGTGGAGCATGTGGTTTAATTCGATGATACGCGAGGAACCTTACCAGGGCTTAAATGTAGAGTGACAGGACTGGAAACAGTTTTTTCTTCGGACACTTTACAAGGTGCTGCATGGTTGTCGTCAGCTCGTGCCGTGAGGTGTCAGGTTAAGTCCTATAACGAGCGCAACCCCTGTTGTTAGTTGCCAGCGAGTAATGTCGGGAACTCTAACAAGACTGCCGGTGCAAACCGTGAGGAAGGTGGGGATGACGTCAAATCATCACGGCCCTTACGTCCTGGGCTACACACGTGCTACAATGGCCGGTACAGAGAGCAGCCACCTCGCGAGGGGGAGCGAATCTATAAAGCCGGTCACAGTTCGGATTGGAGTCTGCAACCCGACTCCATGAAGCTGGAATCGCTAGTAATCGGATATCAGCCATGATCCGGTGAATACGTTCCCGGGCCTTGTACACACCGCCCGTCAAGCCATGGAAGCTGGGGGTACCTGAAGTCGGTGACCGCAAGGAGCTGCCTAGGGTAAAACTGGTAACTGGGGCTAAGTCGTACAAGGTAGCCGTA

10/22/2018                                                                    MCIS 6214 – Data Structure & Algorithms 

10/22

/

20

18

                                                                    

MCIS 6214 

–

 

Data Structure & Algorithms 

 

Data Structure & 

Algorithms

 

 

The goal of t

his project is to 

explore an advanced theoretical topic in

 

Dynamic programming

 

algorithm 

design related to the 

DNA Seq

uence matching. 

Read

 

several materials related to the topic

 

and summarize

 

concepts, find three

 

typical algorithms

, 

choose one of 

the algorithms and implement

 

with C++

 

code

.

 

1)

 

Project Report

: 

 

use attached template 

 

1.

 

Project title & Author information

 

2.

 

Abstract (150 words)

 

. A 

brief summary of the proposal

 

3.

 

Introduction (1 pages)

 

. Identify what works is to be done

 

4.

 

Typical 

Algorithms

 

(

4

~

5

 

pages

)

 

. Background information to educate the reader

 

. Relevance of importance of problem

 

5.

 

Detailed Algorithm analysis 

(1 ~2 pages)

 

6.

 

Experimenta

l Results 

(1~2 pages)

 

7.

 

Conclusions 

(1 Pages)

 

       

Ref

erence

: MLA citation 

 

2)

 

Final Project Demonstration:

 

Powerpoint slides about the project:

 

Each 

group or 

ind

ividual must prepare a 12

 

~ 20 M

inutes presentation that summarize the result 

of their project. 

 

3)

 

Project 

Implementation:

 

 

In this stage,

 

you should provide your 

source 

code

 

(C++)

 

that you have proposed and state time 

complexity of your algorithm. 

 

Sample Data

 

Download the 

DNA from this wbsite:

 

https://hpc.csiro.au/users/317836/KELLY/BASE_Albany/reveg_16S/picrust/97_o

tus.fasta

 

 

>OTU_1111883

 

GCTGGCGGCGTGCCTAACACATGTAAGTCGAACGGGACTGGGGGCAACTCCAGTTCAGTGGCAGACGGGTGCGTAACACGTGAGCAACTTGTCCGAC

GGCGGGGGATAGCCGGCCCAACGGCCGGGTAATACCGCGTACGCTCGTTTAGGGACATCCCTGAATGAGGAAAGCCGTAAGGCACCGACGGAGAGGC

TCGCGGCCTATCAGCTAGTTGGCGGGGTAACGGCCCAC

CAAGGCGACGACGGGTAGCTGGTCTGAGAGGATGGCCAGCCACATTGGGACTGAGACAC

GGCCCAGACTCCTACGGGAGGCAGCAGTGGGGAATCTTGCGCAATGGCCGCAAGGCTGACGCAGCGACGCCGCGTGTGGGATGACGGCCTTCGGGTT

GTAAACCACTGTCGGGAGGAACGAATACTCGGCTAGTCCGAGGGTGACGGTACCTCCAAAGGAAGCACCGGCTAACTCCGTGCCAGCAGCCGCGGTA

ATA

CGGAGGGTGCGAGCGTTGTCCGGAATCACTGGGCGTAAAGGGCGCGTAGGTGGCCCGTTAAGTGGCTGGTGAAATCCCGGGGCTCAACTCCGGG

GCTGCCGGTCAGACTGGCGAGCTAGAGCACGGTAGGGGCAGATGGAATTCCCGGTGTAGCGGTGGAATGCGTAGATATCGGGAAGAATACCAGTGGC

10/22/2018                                                                    MCIS 6214 – Data Structure & Algorithms  
Data Structure & Algorithms 
 
The goal of this project is to explore an advanced theoretical topic in Dynamic programming algorithm 
design related to the DNA Sequence matching. Read several materials related to the topic and summarize 
concepts, find three typical algorithms, choose one of the algorithms and implement with C++ code. 
1) Project Report:  use attached template  
1. Project title & Author information 
2. Abstract (150 words) 
. A brief summary of the proposal 
3. Introduction (1 pages) 
. Identify what works is to be done 
4. Typical Algorithms (4~5 pages) 
. Background information to educate the reader 
. Relevance of importance of problem 
5. Detailed Algorithm analysis (1 ~2 pages) 
6. Experimental Results (1~2 pages) 
7. Conclusions (1 Pages) 
       Reference: MLA citation  
2) Final Project Demonstration: 
Powerpoint slides about the project: 
Each group or individual must prepare a 12 ~ 20 Minutes presentation that summarize the result 
of their project.  
3) Project Implementation:  
In this stage, you should provide your source code (C++) that you have proposed and state time 
complexity of your algorithm.  
Sample Data 
Download the DNA from this wbsite: 
https://hpc.csiro.au/users/317836/KELLY/BASE_Albany/reveg_16S/picrust/97_otus.fasta  
>OTU_1111883 
GCTGGCGGCGTGCCTAACACATGTAAGTCGAACGGGACTGGGGGCAACTCCAGTTCAGTGGCAGACGGGTGCGTAACACGTGAGCAACTTGTCCGAC
GGCGGGGGATAGCCGGCCCAACGGCCGGGTAATACCGCGTACGCTCGTTTAGGGACATCCCTGAATGAGGAAAGCCGTAAGGCACCGACGGAGAGGC
TCGCGGCCTATCAGCTAGTTGGCGGGGTAACGGCCCACCAAGGCGACGACGGGTAGCTGGTCTGAGAGGATGGCCAGCCACATTGGGACTGAGACAC
GGCCCAGACTCCTACGGGAGGCAGCAGTGGGGAATCTTGCGCAATGGCCGCAAGGCTGACGCAGCGACGCCGCGTGTGGGATGACGGCCTTCGGGTT
GTAAACCACTGTCGGGAGGAACGAATACTCGGCTAGTCCGAGGGTGACGGTACCTCCAAAGGAAGCACCGGCTAACTCCGTGCCAGCAGCCGCGGTA
ATACGGAGGGTGCGAGCGTTGTCCGGAATCACTGGGCGTAAAGGGCGCGTAGGTGGCCCGTTAAGTGGCTGGTGAAATCCCGGGGCTCAACTCCGGG
GCTGCCGGTCAGACTGGCGAGCTAGAGCACGGTAGGGGCAGATGGAATTCCCGGTGTAGCGGTGGAATGCGTAGATATCGGGAAGAATACCAGTGGC