ECS124-L9

📗 -> 02/06/25: ECS124-L9

---

🎤 Vocab

❗ Unit and Larger Context

Lecture was help over Zoom

✒️ -> Scratch Notes

Local Alignment Operation:

• O()
  • Length of the Text times length of the Pattern

Suffix Tree Data Structure

• Allows us to search within text in time proportional to length of pattern

Suffix Tree for:

• T=babababa$

Suffix:	Text
1	babababa$
2	abababa$
3	bababa$
4	ababa$
5	baba$
6	aba$
7	ba$
8	a$
9

Transclude of ECS124-L9-2025-02-06-18.23.08.excalidraw

• on paper for creation
• using Divide and Conquer Approach (ECS 122b)

2. De Novo Algorithm

If … known, construct from scratch

CS Concept: Graph Algorithms

• Hamiltonian Circuit Problem
• Eulerian Circuit Problem

Graphs are Data Structure

• G: (set V, set E)
• set V = set of Nodes
• set E
• Graphs can be directed or undirected
  • Undirected:
  • Directed: No such implication, and edge (a,b) means that node a is connected b, but not necessarily vice versa

Hamiltonian Circuit: Path that visits each node only once and returns to the start
Eulerian Circuit: Path such that each edge used exactly once and return to the start and visit each node

Ex:

Bruin Graphs??
a) Imagine a circular genome, that can be in any order:

• AATGGCGTGCA or AAATGGCGTGC or …
  b) Input:
• ATGGCGT
  • GGCGTGC
    • CGTGCAA
      • TGCAATG
        • CAAGGC
          • ATGGCGT
            n1 -> n2
• Suffix(n1) prefix(n2) >= 5
• • De Bruin Graph, based on 3char strives

What is the point?
Genome assembly comes in 2 types:

1. Potential genome suffix action?
2. De Novo assembly

On quiz:
Run BLAST on paper

• Can you create step 1 of BLAST? (3 letter sequences)
  Given HSP has the following:
• 
  What are seeds to BLAST search?
• Seeds: Set A & {att}

🧪 -> Refresh the Info

Did you generally find the overall content understandable or compelling or relevant or not, and why, or which aspects of the reading were most novel or challenging for you and which aspects were most familiar or straightforward?)

Did a specific aspect of the reading raise questions for you or relate to other ideas and findings you’ve encountered, or are there other related issues you wish had been covered?)

🔗 -> Links

Resources

• Put useful links here

Connections

• Link all related words