Overlap Graphs

A Brief Introduction to Graph Theory

Networks arise everywhere in the practical world, especially in biology. Networks are prevalent in popular applications such as modeling the spread of disease, but the extent of network applications spreads far beyond popular science. Our first question asks how to computationally model a network without actually needing to render a picture of the network.
First, some terminology: graph is the technical term for a network; a graph is made up of hubs called nodes (or vertices), pairs of which are connected via segments/curves called edges. If an edge connects nodes vv and ww, then it is denoted by v,wv,w (or equivalently w,v).

• an edge v,w is incident to nodes vv and ww; we say that v and w are adjacent to each other;
• the degree of vv is the number of edges incident to it;
• a walk is an ordered collection of edges for which the ending node of one edge is the starting node of the next (e.g., {v1,v2}, {v2,v3}, {v3,v4}, etc.);
• a path is a walk in which every node appears in at most two edges;
• path length is the number of edges in the path;
• a cycle is a path whose final node is equal to its first node (so that every node is incident to exactly two edges in the cycle); and
• the distance between two vertices is the length of the shortest path connecting them.

Graph theory is the abstract mathematical study of graphs and their properties.

Problem

A graph whose nodes have all been labeled can be represented by an adjacency list, in which each row of the list contains the two node labels corresponding to a unique edge.
A directed graph (or digraph) is a graph containing directed edges, each of which has an orientation. That is, a directed edge is represented by an arrow instead of a line segment; the starting and ending nodes of an edge form its tail and head, respectively. The directed edge with tail v and head ww is represented by (v,w) (but not by (w,v)). A directed loop is a directed edge of the form (v,v).
For a collection of strings and a positive integer k, the overlap graph for the strings is a directed graph in which each string is represented by a node, and string s is connected to string t with a directed edge when there is a length k suffix of s that matches a length k prefix of t, as long as s≠t; we demand s≠t to prevent directed loops in the overlap graph (although directed cycles may be present).
Given: A collection of DNA strings in FASTA format having total length at most 10 kbp.
Return: The adjacency list corresponding to . You may return edges in any order.

Sample Dataset

Rosalind_0498
AAATAAA
>Rosalind_2391
AAATTTT
>Rosalind_2323
TTTTCCC
>Rosalind_0442
AAATCCC
>Rosalind_5013
GGGTGGG

Sample Output

Rosalind_0498 Rosalind_2391
Rosalind_0498 Rosalind_0442
Rosalind_2391 Rosalind_2323

Note on Visualizing Graphs

If you are looking for a way to actually visualize graphs as you are working through the Rosalind site, then you may like to consider Graphviz (link here), a cross-platform application for rendering graphs.

Solution

本题建图的要求是长度为 k = 3 的后缀为有向图的起点，长度为 k = 3 的前缀为有向图的终点，且不允许自连（也就是两个节点字符串不能相同，如下图中 AAA T AAA 不能自连）
Overlap Graphs.drawio
其实本例就是考察如何建图，我们直接使用两个哈希表，一个表示长度为 k 的后缀构成有向图起点，另一个表示长度为 k 的前缀构成有向图的终点。 ```python from typing import List, Tuple, Dict import re

class Solution: def overlapGraph(self, seqs: Dict[str, str], k: int) -> List[Tuple[str]]: “””返回邻接表””” from collections import defaultdict parent, child = defaultdict(list), defaultdict(list) for key, seq in seqs.items(): parent[seq[-k:]].append(key) child[seq[:k]].append(key)

    # 2. 从 parent 出发，遍历所有子节点
    res = []
    for src in parent:
        for u in parent[src]:
            for v in child[src]:
                if u != v:  # 不准自连
                    res.append((u, v))
    return res

fasta = “””

Rosalind_0498 AAATAAA Rosalind_2391 AAATTTT Rosalind_2323 TTTTCCC Rosalind_0442 AAATCCC Rosalind_5013 GGGTGGG “””

seqs = {} for seq in re.split(r’>’, fasta): seq = seq.strip() if seq: seqID, bases = seq.split(maxsplit=1) seqs[seqID] = bases.replace(‘\n’, ‘’)

print(seqs) for u, v in Solution().overlapGraph(seqs, 3): print(u, v) ```